On efficiently solvable cases of Quantum k-SAT
The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA_1-complete problems (for k >= 3), respectively, where QMA_1 is a quantum generalization of NP with one-sided error. Whereas k-SAT has been well-studied for special tractable cases, as well...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl
2018
|
| _version_ | 1826268846576631808 |
|---|---|
| author | Aldi, M De Beaudrap, J Gharibian, S Saeedi, S |
| author_facet | Aldi, M De Beaudrap, J Gharibian, S Saeedi, S |
| author_sort | Aldi, M |
| collection | OXFORD |
| description | The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA_1-complete problems (for k >= 3), respectively, where QMA_1 is a quantum generalization of NP with one-sided error. Whereas k-SAT has been well-studied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a "matching" or "dimer covering"; this is an NP problem whose decision variant is trivial, but whose search complexity remains open. Our results fall into three directions, all of which relate to the "matching" setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases by reducing the problem to solving for a single root of a single univariate polynomial. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a "matching". We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry; we hope these prove useful elsewhere. |
| first_indexed | 2024-03-06T21:15:51Z |
| format | Conference item |
| id | oxford-uuid:3fc50ba3-4945-4163-9923-5d66d22fb5e6 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T21:15:51Z |
| publishDate | 2018 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:3fc50ba3-4945-4163-9923-5d66d22fb5e62022-03-26T14:34:00ZOn efficiently solvable cases of Quantum k-SATConference itemhttp://purl.org/coar/resource_type/c_5794uuid:3fc50ba3-4945-4163-9923-5d66d22fb5e6Symplectic Elements at OxfordSchloss Dagstuhl2018Aldi, MDe Beaudrap, JGharibian, SSaeedi, SThe constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA_1-complete problems (for k >= 3), respectively, where QMA_1 is a quantum generalization of NP with one-sided error. Whereas k-SAT has been well-studied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a "matching" or "dimer covering"; this is an NP problem whose decision variant is trivial, but whose search complexity remains open. Our results fall into three directions, all of which relate to the "matching" setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases by reducing the problem to solving for a single root of a single univariate polynomial. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a "matching". We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry; we hope these prove useful elsewhere. |
| spellingShingle | Aldi, M De Beaudrap, J Gharibian, S Saeedi, S On efficiently solvable cases of Quantum k-SAT |
| title | On efficiently solvable cases of Quantum k-SAT |
| title_full | On efficiently solvable cases of Quantum k-SAT |
| title_fullStr | On efficiently solvable cases of Quantum k-SAT |
| title_full_unstemmed | On efficiently solvable cases of Quantum k-SAT |
| title_short | On efficiently solvable cases of Quantum k-SAT |
| title_sort | on efficiently solvable cases of quantum k sat |
| work_keys_str_mv | AT aldim onefficientlysolvablecasesofquantumksat AT debeaudrapj onefficientlysolvablecasesofquantumksat AT gharibians onefficientlysolvablecasesofquantumksat AT saeedis onefficientlysolvablecasesofquantumksat |