Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems. (English) Zbl 1456.81147
Summary: We present an exact quantum algorithm for solving the Exact Satisfiability problem, which belongs to the important NP-complete complexity class. The algorithm is based on an intuitive approach that can be divided into two parts: the first step consists in the identification and efficient characterization of a restricted subspace that contains all the valid assignments of the Exact Satisfiability; while the second part performs a quantum search in such restricted subspace. The quantum algorithm can be used either to find a valid assignment (or to certify that no solution exists) or to count the total number of valid assignments. The query complexities for the worst-case are respectively bounded by \(O(\sqrt{2^{n-M'}})\) and \(O(2^{n-M'}\), where \(n\) is the number of variables and \(M'\) the number of linearly independent clauses. Remarkably, the proposed quantum algorithm results to be faster than any known exact classical algorithm to solve dense formulas of Exact Satisfiability. As a concrete application, we provide the worst-case complexity for the Hamiltonian cycle problem obtained after mapping it to a suitable Occupation problem. Specifically, we show that the time complexity for the proposed quantum algorithm is bounded by \(O(2^{n/4})\) for 3-regular undirected graphs, where \(n\) is the number of nodes. The same worst-case complexity holds for \((3,3)\)-regular bipartite graphs. As a reference, the current best classical algorithm has a (worst-case) running time bounded by \(O(2^{31n/96})\). Finally, when compared to heuristic techniques for Exact Satisfiability problems, the proposed quantum algorithm is faster than the classical WalkSAT and Adiabatic Quantum Optimization for random instances with a density of constraints close to the satisfiability threshold, the regime in which instances are typically the hardest to solve. The proposed quantum algorithm can be straightforwardly extended to the generalized version of the Exact Satisfiability known as Occupation problem. The general version of the algorithm is presented and analyzed.
References:
| [1] | Karp R M 1972 Reducibility Among Combinatorial Problems (New York: Springer) · Zbl 1467.68065 · doi:10.1007/978-1-4684-2001-2_9 |
| [2] | Schaefer T J 1978 Proceedings of the Tenth Annual ACM Symposium on Theory of Computing (New York: ACM) pp 216-26 · Zbl 1282.68143 |
| [3] | Cook S A 1971 Proceedings of the Third Annual ACM Symposium on Theory of Computing (New York: ACM) pp 151-8 · Zbl 0237.00024 |
| [4] | Shor P W 1997 Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer SIAM J. Comput.26 1484 · Zbl 1005.11065 · doi:10.1137/S0097539795293172 |
| [5] | Montanaro A 2014 Quantum pattern matching fast on average Algorithmica 1-24 · Zbl 1359.68093 · doi:10.1007/s00453-015-0060-4 |
| [6] | Harrow A W, Hassidim A and Lloyd S 2009 Quantum algorithm for linear systems of equations Phys. Rev. Lett.103 150502 · doi:10.1103/PhysRevLett.103.150502 |
| [7] | Ambainis A 2012 STACS’12 (29th Symposium on Theoretical Aspects of Computer Science) (LIPIcs)vol 14 pp 636-47 |
| [8] | Garey M R and Johnson D S 1979a Computers and Intractability: A Guide to the Theory of NP-Completeness · Zbl 0411.68039 |
| [9] | Young A P, Knysh S and Smelyanskiy V N 2008 Size dependence of the minimum excitation gap in the quantum adiabatic algorithm Phys. Rev. Lett.101 170503 · doi:10.1103/PhysRevLett.101.170503 |
| [10] | Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A and Preda D 2001 A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem Science292 472 · Zbl 1226.81046 · doi:10.1126/science.1057726 |
| [11] | Hen I and Young A 2011 Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems Phys. Rev. E 84 061152 · doi:10.1103/PhysRevE.84.061152 |
| [12] | Guidetti M and Young A 2011 Complexity of several constraint-satisfaction problems using the heuristic classical algorithm WalkSAT Phys. Rev. E 84 011102 · doi:10.1103/PhysRevE.84.011102 |
| [13] | Zdeborová L and Mézard M 2008a Constraint satisfaction problems with isolated solutions are hard J. Stat. Mech.: Theory and Experiment P12004 · doi:10.1088/1742-5468/2008/12/P12004 |
| [14] | Cheeseman P, Kanefsky B and Taylor W M 1991 IJCAI91 331-40 |
| [15] | Mézard M, Parisi G and Zecchina R 2002 Analytic and algorithmic solution of random satisfiability problems Science297 812 · doi:10.1126/science.1073287 |
| [16] | Krzakała F, Montanari A, Ricci-Tersenghi F, Semerjian G and Zdeborová L 2007 Gibbs states and the set of solutions of random constraint satisfaction problems Proc. Natl Acad. Sci. USA104 10318 · Zbl 1190.68031 · doi:10.1073/pnas.0703685104 |
| [17] | Schroeppel R and Shamir A 1981 A T = O(2̂n/2), S = O(2̂n/4) algorithm for certain NP-complete problems SIAM J. Comput.10 456 · Zbl 0462.68015 · doi:10.1137/0210033 |
| [18] | Monien B, Speckenmeyer E and Vornberger O 1981 Upper bounds for covering problems Methods Oper. Res.43 419 · Zbl 0508.90065 |
| [19] | Porschen S, Randerath B and Speckenmeyer E 2005 Exact 3-satisfiability is decidable in time O (20.16254 n) Ann. Math. Artif. Intell.43 173 · Zbl 1099.68042 · doi:10.1007/s10472-005-0428-2 |
| [20] | Kulikov A S 2002 An upper bound O(2̂0.16254n) for Exact 3-Satisfiability: a simpler proof Zapiski Nauchnykh Seminarov POMI293 118 · Zbl 1101.68609 |
| [21] | Byskov J M, Madsen B A and Skjernaa B 2005 New algorithms for exact satisfiability Theor. Comput. Sci.332 515 · Zbl 1070.68049 · doi:10.1016/j.tcs.2004.12.023 |
| [22] | Skjernaa B 2004 Ph D Thesis BRICS |
| [23] | Zhou J and Yin M 2012 The Worst-Case Upper Bound for Exact 3-Satisfiability with the Number of Clauses as the Parameter, in Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (New York: Springer) pp 212-23 · Zbl 1304.68085 · doi:10.1007/978-3-642-29700-7_20 |
| [24] | Davis M and Putnam H 1960 A computing procedure for quantification theory J. ACM7 201 · Zbl 0212.34203 · doi:10.1145/321033.321034 |
| [25] | Davis M, Logemann G and Loveland D 1962 A machine program for theorem-proving Commun. ACM5 394 · Zbl 0217.54002 · doi:10.1145/368273.368557 |
| [26] | Valiant L G 1979 The complexity of computing the permanent Theor. Comput. Sci.8 189 · Zbl 0415.68008 · doi:10.1016/0304-3975(79)90044-6 |
| [27] | Birnbaum E and Lozinskii E L 1999 The good old Davis-Putnam procedure helps counting models J. Artificial Intelligence Res.10 457-77 · Zbl 0918.68098 · doi:10.1613/jair.601 |
| [28] | Roth D 1996 On the hardness of approximate reasoning Artif. Intell.82 273 · Zbl 1506.68143 · doi:10.1016/0004-3702(94)00092-1 |
| [29] | Aaronson S and Arkhipov A 2011 Proc. Forty-Third Annual ACM Symposium on Theory of Computing (New York: ACM) pp 333-42 · Zbl 1288.68066 |
| [30] | Tillmann M, Tan S-H, Stoeckl S E, Sanders B C, de Guise H, Heilmann R, Nolte S, Szameit A and Walther P 2015 Generalized multiphoton quantum interference Phys. Rev. X 57 041015 · doi:10.1103/PhysRevX.5.041015 |
| [31] | Huh J, Guerreschi G G, Peropadre B, McClean J R and Aspuru-Guzik A 2015 Boson sampling for molecular Vibronic Spectra Nat. Photon.9 615 · doi:10.1038/nphoton.2015.153 |
| [32] | Zhou J, Su W, Wang J and Upper New Worst-Case 2014 Bound for counting exact satisfiability Int. J. Found. Comput. Sci.25 667 · Zbl 1304.68084 · doi:10.1142/S0129054114500270 |
| [33] | Dahllöf V, Jonsson P and Beigel R 2004 Algorithms for four variants of the exact satisfiability problem Theor. Comput. Sci.320 373 · Zbl 1068.68068 · doi:10.1016/j.tcs.2004.02.035 |
| [34] | Grover L K 1996 Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (New York: ACM) pp 212-219 · Zbl 0922.68044 |
| [35] | Farhi E and Gutmann S 1998 Analog analogue of a digital quantum computation Phys. Rev. A 57 2403 · doi:10.1103/PhysRevA.57.2403 |
| [36] | Roland J and Cerf N J 2002 Quantum search by local adiabatic evolution Phys. Rev. A 65 042308 · doi:10.1103/PhysRevA.65.042308 |
| [37] | Mandrà S, Guerreschi G G and Aspuru-Guzik A 2015 Adiabatic quantum optimization in the presence of discrete noise: reducing the problem dimensionality Phys. Rev. A 92 062320 · doi:10.1103/PhysRevA.92.062320 |
| [38] | Iwama K and Nakashima T 2007 Lecture Notes in Computer Science(COCOON vol 4598) ed G Lin (New York: Springer) pp 108-17 · Zbl 1206.68146 |
| [39] | Van Beek P 2006 Backtracking search algorithms Handbook of Constraint Programming vol 2 (Amsterdam: Elsevier) pp 83-132 |
| [40] | Montanaro A 2015 Quantum walk speedup of backtracking algorithms (arXiv:1509.02374) · Zbl 1417.68046 |
| [41] | Zdeborová L and Mézard M 2008 Locked constraint satisfaction problems Phys. Rev. Lett.101 078702 · doi:10.1103/PhysRevLett.101.078702 |
| [42] | Lidl R and Niederreiter H 1997 Finite Fields vol 20 |
| [43] | Kolchin V F 1999 Random Graphs vol 53 · Zbl 0918.05001 |
| [44] | Alamino R C and Saad D 2008 Typical kernel size and number of sparse random matrices over Galois fields: a statistical physics approach Phys. Rev. E 77 061123 · doi:10.1103/PhysRevE.77.061123 |
| [45] | Alamino R C and Saad D 2009 Properties of sparse random matrices over finite fields J. Stat. Mech.: Theory and Experiment2009 P04017 · Zbl 1456.82482 · doi:10.1088/1742-5468/2009/04/P04017 |
| [46] | Boyer M, Brassard G, Hoeyer P and Tapp A 1998 Tight Bounds on Quantum Searching Progress of Physics46 493 · doi:10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P |
| [47] | Brassard G, Høyer P and Tapp A 1998 Quantum Counting, in Automata, Languages and Programming (New York: Springer) pp 820-31 · doi:10.1007/BFb0055105 |
| [48] | Brassard G, Hoyer P, Mosca M and Tapp A 2002 Quantum amplitude amplification and estimation Contemporary Mathematics305 53 · Zbl 1063.81024 · doi:10.1090/conm/305/05215 |
| [49] | Hayashi M, Ishizaka S, Kawachi A, Kimura G and Ogawa T 2014 Introduction to Quantum Information Science (New York: Springer) |
| [50] | Garey M R and Johnson D S 1979b Computers and Intractability: a Guide to the Theory of NP-Completeness. 1979 (San Francisco, CA: Freeman) · Zbl 0411.68039 |
| [51] | Held M and Karp R M 1962 A dynamic programming approach to sequencing problems J. Soc. Industrial and Applied Mathematics10 196-210 · Zbl 0106.14103 · doi:10.1137/0110015 |
| [52] | Eppstein D 2007 The traveling salesman problem for cubic graphs J. Graph Algorithms Appl.11 61 · Zbl 1161.68662 · doi:10.7155/jgaa.00137 |
| [53] | Childs A M, Cleve R, Deotto E, Farhi E, Gutmann S and Spielman D A 2003 Proc. Thirty-Fifth Annual ACM Symposium on Theory of Computing (New York: ACM) pp 59-68 · Zbl 1192.81059 · doi:10.1145/780542.780552 |
| [54] | Ambainis A 2007 Quantum walk algorithm for element distinctness SIAM J. Comput.37 210 · Zbl 1134.81010 · doi:10.1137/S0097539705447311 |
| [55] | Szegedy M 2004 Proc. 45th Annual IEEE Symposium on Foundations of Computer Science 2004 pp 32-41 (Los Alamitos, CA: IEEE Computer Society) · doi:10.1109/FOCS.2004.53 |
| [56] | Magniez F, Nayak A, Roland J and Santha M 2011 Search via quantum walk SIAM J. Comput.40 142 · Zbl 1223.05289 · doi:10.1137/090745854 |
| [57] | Ambainis A 2004 Quantum search algorithms ACM SIGACT News35 22 · doi:10.1145/992287.992296 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
