UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph

Chancellor, N; Zohren, S; Warburton, PA; Benjamin, SC; Roberts, S; (2016) A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph. Scientific Reports , 6 , Article 37107. 10.1038/srep37107. Green open access

[thumbnail of Warburton_srep37107.pdf] Text
Warburton_srep37107.pdf

Download (958kB)

Abstract

We demonstrate a direct mapping of max k-SAT problems (and weighted max k-SAT) to a Chimera graph, which is the non-planar hardware graph of the devices built by D-Wave Systems Inc. We further show that this mapping can be used to map a similar class of maximum satisfiability problems where the clauses are replaced by parity checks over potentially large numbers of bits. The latter is of specific interest for applications in decoding for communication. We discuss an example in which the decoding of a turbo code, which has been demonstrated to perform near the Shannon limit, can be mapped to a Chimera graph. The weighted max k-SAT problem is the most general class of satisfiability problems, so our result effectively demonstrates how any satisfiability problem may be directly mapped to a Chimera graph. Our methods faithfully reproduce the low energy spectrum of the target problems, so therefore may also be used for maximum entropy inference.

Type: Article
Title: A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
Open access status: An open access version is available from UCL Discovery
DOI: 10.1038/srep37107
Publisher version: http://dx.doi.org/10.1038/srep37107
Language: English
Additional information: This work is licensed under a Creative Commons Attribution 4.0 International License. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in the credit line; if the material is not included under the Creative Commons license, users will need to obtain permission from the license holder to reproduce the material. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/
Keywords: Science & Technology, Multidisciplinary Sciences, Science & Technology - Other Topics, QUANTUM COMPUTATION, MODEL, Quantum information, Theoretical physics
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > London Centre for Nanotechnology
URI: https://discovery.ucl.ac.uk/id/eprint/1527474
Downloads since deposit
85Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item