A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
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 clau...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Published: |
Nature Publishing Group
2016
|
| _version_ | 1797099284513947648 |
|---|---|
| author | Chancellor, N Zohren, S Warburton, P Benjamin, S Roberts, S |
| author_facet | Chancellor, N Zohren, S Warburton, P Benjamin, S Roberts, S |
| author_sort | Chancellor, N |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T05:21:35Z |
| format | Journal article |
| id | oxford-uuid:df1bf92a-c0a9-4200-b327-ff99076f4b40 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:21:35Z |
| publishDate | 2016 |
| publisher | Nature Publishing Group |
| record_format | dspace |
| spelling | oxford-uuid:df1bf92a-c0a9-4200-b327-ff99076f4b402022-03-27T09:37:01ZA Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera GraphJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:df1bf92a-c0a9-4200-b327-ff99076f4b40Symplectic Elements at OxfordNature Publishing Group2016Chancellor, NZohren, SWarburton, PBenjamin, SRoberts, SWe 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. |
| spellingShingle | Chancellor, N Zohren, S Warburton, P Benjamin, S Roberts, S A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph |
| title | A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera
Graph |
| title_full | A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera
Graph |
| title_fullStr | A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera
Graph |
| title_full_unstemmed | A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera
Graph |
| title_short | A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera
Graph |
| title_sort | direct mapping of max k sat and high order parity checks to a chimera graph |
| work_keys_str_mv | AT chancellorn adirectmappingofmaxksatandhighorderparitycheckstoachimeragraph AT zohrens adirectmappingofmaxksatandhighorderparitycheckstoachimeragraph AT warburtonp adirectmappingofmaxksatandhighorderparitycheckstoachimeragraph AT benjamins adirectmappingofmaxksatandhighorderparitycheckstoachimeragraph AT robertss adirectmappingofmaxksatandhighorderparitycheckstoachimeragraph AT chancellorn directmappingofmaxksatandhighorderparitycheckstoachimeragraph AT zohrens directmappingofmaxksatandhighorderparitycheckstoachimeragraph AT warburtonp directmappingofmaxksatandhighorderparitycheckstoachimeragraph AT benjamins directmappingofmaxksatandhighorderparitycheckstoachimeragraph AT robertss directmappingofmaxksatandhighorderparitycheckstoachimeragraph |