Quantum-accelerated constraint programming

Kyle E. C. Booth1,2, Bryan O'Gorman1,3, Jeffrey Marshall1,2, Stuart Hadfield1,2, and Eleanor Rieffel1

1Quantum Artificial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA 94035, USA
2USRA Research Institute for Advanced Computer Science (RIACS), Mountain View, CA 94043, USA
3Berkeley Quantum Information and Computation Center, University of California, Berkeley, CA 94720, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


Constraint programming (CP) is a paradigm used to model and solve constraint satisfaction and combinatorial optimization problems. In CP, problems are modeled with constraints that describe acceptable solutions and solved with backtracking tree search augmented with logical inference. In this paper, we show how quantum algorithms can accelerate CP, at both the levels of inference and search. Leveraging existing quantum algorithms, we introduce a quantum-accelerated filtering algorithm for the $\texttt{alldifferent}$ global constraint and discuss its applicability to a broader family of global constraints with similar structure. We propose frameworks for the integration of quantum filtering algorithms within both classical and quantum backtracking search schemes, including a novel hybrid classical-quantum backtracking search method. This work suggests that CP is a promising candidate application for early fault-tolerant quantum computers and beyond.

► BibTeX data

► References

[1] Francesca Rossi, Peter Van Beek, and Toby Walsh. Handbook of constraint programming. Elsevier, 2006. ISBN 9780080463803.

[2] Philippe Baptiste, Claude Le Pape, and Wim Nuijten. Constraint-based scheduling: applying constraint programming to scheduling problems, volume 39. Springer Science & Business Media, 2001. 10.1007/​978-1-4615-1479-4.

[3] Philippe Laborie, Jérôme Rogerie, Paul Shaw, and Petr Vilím. IBM ILOG CP optimizer for scheduling. Constraints, 23 (2): 210–250, 2018. 10.1007/​s10601-018-9281-x.

[4] Peter Van Beek. Backtracking search algorithms. In Foundations of artificial intelligence, volume 2, pages 85–134. Elsevier, 2006. 10.1016/​S1574-6526(06)80008-8.

[5] Pascal Van Hentenryck and Laurent Michel. Constraint-based local search. MIT Press, 2009. ISBN 026251348X.

[6] Gustav Björdal, Jean-Noël Monette, Pierre Flener, and Justin Pearson. A constraint-based local search backend for MiniZinc. Constraints, 20 (3): 325–345, 2015. 10.1007/​s10601-015-9184-z.

[7] Armin Biere, Marijn Heule, and Hans van Maaren. Handbook of satisfiability, volume 185. IOS press, 2009. ISBN 1586039296.

[8] Laurence A Wolsey. Integer programming, volume 52. John Wiley & Sons, 1998. ISBN 0471283665.

[9] Jean-Charles Régin. A filtering algorithm for constraints of difference in CSPs. In Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI-1994), pages 362–367. AAAI Press, 1994. URL https:/​/​www.aaai.org/​Papers/​AAAI/​1994/​AAAI94-055.pdf.

[10] Radosław Cymer. Dulmage-Mendelsohn canonical decomposition as a generic pruning technique. Constraints, 17 (3): 234–272, 2012. 10.1007/​s10601-012-9120-4.

[11] Claude-Guy Quimper, Alejandro López-Ortiz, Peter Van Beek, and Alexander Golynski. Improved algorithms for the global cardinality constraint. In Principles and Practice of Constraint Programming (CP-2004), pages 542–556. Springer, 2004. 10.1007/​978-3-540-30201-8_40.

[12] Nicolas Beldiceanu, Mats Carlsson, Sophie Demassey, and Thierry Petit. Global constraint catalogue: Past, present and future. Constraints, 12 (1): 21–62, 2007. 10.1007/​s10601-006-9010-8.

[13] Sebastian Dörn. Quantum algorithms for matching problems. Theory of Computing Systems, 45 (3): 613–628, 2009. 10.1007/​s00224-008-9118-x.

[14] Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC-1996), pages 212–219. Association for Computing Machinery, 1996. 10.1145/​237814.237866.

[15] Ashley Montanaro. Quantum-walk speedup of backtracking algorithms. Theory of Computing, 14 (15): 1–24, 2018. 10.4086/​toc.2018.v014a015.

[16] Michael Jarret and Kianna Wan. Improved quantum backtracking algorithms using effective resistance estimates. Phys. Rev. A, 97: 022337, February 2018. 10.1103/​PhysRevA.97.022337.

[17] Kyle E. C. Booth, Minh Do, J Christopher Beck, Eleanor Rieffel, Davide Venturelli, and Jeremy Frank. Comparing and integrating constraint programming and temporal planning for quantum circuit compilation. In Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS-2018), pages 366–374. AAAI Press, 2018. URL https:/​/​arxiv.org/​abs/​1803.06775.

[18] Kyle E. C. Booth, Bryan O'Gorman, Jeffrey Marshall, Stuart Hadfield, and Eleanor Rieffel. Quantum-accelerated global constraint filtering. In Principles and Practice of Constraint Programming (CP-2020), pages 72–89. Springer, 2020. 10.1007/​978-3-030-58475-7_5.

[19] Willem-Jan van Hoeve and Irit Katriel. Global constraints. In Foundations of Artificial Intelligence, volume 2, pages 169–208. Elsevier, 2006. 10.1016/​S1574-6526(06)80010-6.

[20] Laurent Perron. Operations research and constraint programming at Google. In Principles and Practice of Constraint Programming (CP-2011), pages 2–2. Springer, 2011. 10.1007/​978-3-642-23786-7_2.

[21] Nicholas Nethercote, Peter J Stuckey, Ralph Becket, Sebastian Brand, Gregory J Duck, and Guido Tack. MiniZinc: Towards a standard CP modelling language. In Principles and Practice of Constraint Programming (CP-2007), pages 529–543. Springer, 2007. 10.1007/​978-3-540-74970-7_38.

[22] Christian Schulte, Mikael Lagerkvist, and Guido Tack. Gecode: A generic constraint development environment, 2019. URL https:/​/​www.gecode.org.

[23] Geoffrey Chu, Peter J. Stuckey, Andreas Schutt, Thorsten Ehlers, Graeme Gange, and Kathryn Francis. Chuffed, a lazy clause generation solver, 2019. URL https:/​/​www.github.com/​chuffed/​chuffed.

[24] Danial Davarnia and John N Hooker. Consistency for 0–1 programming. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR-2019), pages 225–240. Springer, 2019. 10.1007/​978-3-030-19212-9_15.

[25] Alan K Mackworth. Consistency in networks of relations. Artificial Intelligence, 8 (1): 99–118, 1977. 10.1016/​0004-3702(77)90007-8.

[26] Willem-Jan Van Hoeve. The alldifferent constraint: A survey. arXiv:cs/​0105015, 2001. URL https:/​/​arxiv.org/​abs/​cs/​0105015.

[27] Luc Mercier and Pascal Van Hentenryck. Edge finding for cumulative scheduling. INFORMS Journal on Computing, 20 (1): 143–153, 2008. 10.1287/​ijoc.1070.0226.

[28] Petr Vilím. Edge finding filtering algorithm for discrete cumulative resources in $\mathcal{O}(kn \log n)$. In Principles and Practice of Constraint Programming (CP-2009), pages 802–816. Springer, 2009. 10.1007/​978-3-642-04244-7_62.

[29] Helmut Simonis. Sudoku as a constraint problem. In CP Workshop on Modelling and Reformulating Constraint Satisfaction Problems, volume 12, pages 13–27, 2005.

[30] Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Trans. Fundamentals, 86 (5): 1052–1060, 2003.

[31] Robert E Bixby. A brief history of linear and mixed-integer programming computation. Documenta Mathematica, Extra Volume: Optimization Stories: 107–121, 2012.

[32] Alessandra Di Pierro and Herbert Wiklicky. Quantum constraint programming. In Joint Conference on Declarative Programming (APPIA-GULP-PRODE-2001), pages 113–130, 2001.

[33] Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. Proc. R. Soc. Lond. A., 454 (1969): 339–354, 1998. 10.1098/​rspa.1998.0164.

[34] Aija Berzina, Andrej Dubrovsky, Rusins Freivalds, Lelde Lace, and Oksana Scegulnaja. Quantum query complexity for some graph problems. In Theory and Practice of Computer Science (SOFSEM-2004), pages 140–150. Springer, 2004. 10.1007/​978-3-540-24618-3_11.

[35] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35 (6): 1310–1328, 2006. 10.1137/​050644719.

[36] Bartholomew Furrow. A panoply of quantum algorithms. Quantum Information & Computation, 8 (8): 834–859, 2008. URL https:/​/​arxiv.org/​abs/​quant-ph/​0606127.

[37] Fuwei Cai, Satoshi Tayu, and Shuichi Ueno. On the quantum query complexity of all-pairs shortest paths. In Proceedings of the 2007 IEICE General Conference, 2007.

[38] Cedric Yen-Yu Lin and Han-Hsuan Lin. Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester. In 30th Conference on Computational Complexity (CCC-2015), Leibniz International Proceedings in Informatics (LIPIcs), pages 537–566. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. 10.4230/​LIPIcs.CCC.2015.537.

[39] Shengyu Zhang. On the power of Ambainis lower bounds. Theoretical Computer Science, 339 (2-3): 241–256, 2005. 10.1016/​j.tcs.2005.01.019.

[40] Andris Ambainis and Robert Špalek. Quantum algorithms for matching and network flows. In Annual Symposium on Theoretical Aspects of Computer Science (STACS-2006), pages 172–183. Springer, 2006. 10.1007/​11672142_13.

[41] Salman Beigi and Leila Taghavi. Quantum speedup based on classical decision trees. Quantum, 4: 241, 2020. 10.22331/​q-2020-03-02-241.

[42] Shelby Kimmel and R Teal Witter. A query-efficient quantum algorithm for maximum matching on general graphs. In Workshop on Algorithms and Data Structures (WADS-2021), pages 543–555. Springer, 2021. 10.1007/​978-3-030-83508-8_39.

[43] Fernando GSL Brandao and Krysta M Svore. Quantum speed-ups for solving semidefinite programs. In 58th Annual Symposium on Foundations of Computer Science (FOCS-2017), pages 415–426. IEEE, 2017. 10.1109/​FOCS.2017.45.

[44] Joran Van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. Quantum, 4: 230, 2020. 10.22331/​q-2020-02-14-230.

[45] Giacomo Nannicini. Fast quantum subroutines for the simplex method. In Integer Programming and Combinatorial Optimization (IPCO-2021), pages 311–325. Springer, 2021. 10.1007/​978-3-030-73879-2_22.

[46] Ashley Montanaro. Quantum speedup of branch-and-bound algorithms. Physical Review Research, 2 (1): 013056, 2020. 10.1103/​PhysRevResearch.2.013056.

[47] Andris Ambainis and Martins Kokainis. Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC-2017), pages 989–1002. Association for Computing Machinery, 2017. 10.1145/​3055399.3055444.

[48] S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. ISBN 9781139477369.

[49] Eleanor G Rieffel and Wolfgang H Polak. Quantum computing: A gentle introduction. MIT Press, 2011. ISBN 9780262015066.

[50] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical review letters, 100 (16): 160501, 2008. 10.1103/​PhysRevLett.100.160501.

[51] N Jiang, Y-F Pu, W Chang, C Li, S Zhang, and L-M Duan. Experimental realization of 105-qubit random access quantum memory. npj Quantum Information, 5 (1): 1–6, 2019. 10.1038/​s41534-019-0144-0.

[52] O. D. Matteo, V. Gheorghiu, and M. Mosca. Fault-tolerant resource estimation of quantum random-access memories. IEEE Transactions on Quantum Engineering, 1: 1–13, 2020. 10.1109/​TQE.2020.2965803.

[53] Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O’Connor, Michele Mosca, and Priyaa Varshinee Srinivasan. On the robustness of bucket brigade quantum ram. New Journal of Physics, 17 (12): 123010, 2015. 10.1088/​1367-2630/​17/​12/​123010.

[54] Ian P Gent, Ian Miguel, and Peter Nightingale. Generalised arc consistency for the alldifferent constraint: An empirical survey. Artificial Intelligence, 172 (18): 1973–2000, 2008. 10.1016/​j.artint.2008.10.006.

[55] Xizhe Zhang, Qian Li, and Weixiong Zhang. A fast algorithm for generalized arc consistency of the alldifferent constraint. In International Joint Conference on Artificial Intelligence (IJCAI-2018), pages 1398–1403, 2018. 10.24963/​ijcai.2018/​194.

[56] John E Hopcroft and Richard M Karp. An $n^{5/​2}$ algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2 (4): 225–231, 1973. 10.1137/​0202019.

[57] Silvio Micali and Vijay V Vazirani. An O($\sqrt{|V|}|E|$) algorithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science (FOCS-1980), pages 17–27. IEEE, 1980. 10.1109/​SFCS.1980.12.

[58] Vijay V Vazirani. A simplification of the MV matching algorithm and its proof. arXiv:1210.4594 [cs.DS], 2012. URL https:/​/​arxiv.org/​abs/​1210.4594.

[59] Marcin Mucha and Piotr Sankowski. Maximum matchings via Gaussian elimination. In 45th Annual Symposium on Foundations of Computer Science (FOCS-2004), pages 248–255. IEEE, 2004. 10.1109/​FOCS.2004.40.

[60] Oscar H Ibarra and Shlomo Moran. Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication. Information Processing Letters, 13 (1): 12–15, 1981. 10.1016/​0020-0190(81)90142-3.

[61] Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In ACM-SIAM Symposium on Discrete Algorithms (SODA-2021), pages 522–539. SIAM, 2021. 10.1137/​1.9781611976465.32.

[62] Helmut Alt, Norbert Blum, Kurt Mehlhorn, and Markus Paul. Computing a maximum cardinality matching in a bipartite graph in time $O(n^{1.5}m \log n)$. Information Processing Letters, 37 (4): 237–240, 1991. 10.1016/​0020-0190(91)90195-N.

[63] Jan van den Brand, Yin-Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on moderately dense graphs. In 61st Annual Symposium on Foundations of Computer Science (FOCS-2020), pages 919–930. IEEE, 2020. 10.1109/​FOCS46700.2020.00090.

[64] Robert Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1: 146–160, 1972. 10.1137/​0201010.

[65] Claude Berge. Graphs and hypergraphs. North-Holland, 1973. ISBN 9780444876034.

[66] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics, 46 (4-5): 493–505, 1998. 10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P.

[67] A. Ambainis. Quantum search algorithms. ACM SIGACT News, 35 (2): 22–35, 2004. 10.1145/​992287.992296.

[68] Radosław Cymer. Gallai-edmonds decomposition as a pruning technique. Central European Journal of Operations Research, 23 (1): 149–185, 2015. 10.1007/​s10100-013-0309-4.

[69] Andrew L Dulmage and Nathan S Mendelsohn. Coverings of bipartite graphs. Canadian Journal of Mathematics, 10: 517–534, 1958. 10.4153/​CJM-1958-052-0.

[70] Jack Edmonds. Paths, trees, and flowers. Canadian Journal of mathematics, 17: 449–467, 1965. 10.4153/​CJM-1965-045-4.

[71] J.A. Bondy and U.S.R. Murty. Graph Theory with Applications. Macmillan, 1977. ISBN 9780333226940.

[72] Aleksandrs Belovs. Quantum walks and electric networks. arXiv:1302.3143 [quant-ph], 2013. URL https:/​/​arxiv.org/​abs/​1302.3143.

[73] Earl Campbell, Ankur Khurana, and Ashley Montanaro. Applying quantum algorithms to constraint satisfaction problems. Quantum, 3: 167, 2019. 10.22331/​q-2019-07-18-167.

[74] Mathys Rennela, Alfons Laarman, and Vedran Dunjko. Hybrid divide-and-conquer approach for tree search algorithms. arXiv:2007.07040 [quant-ph], 2020. URL https:/​/​arxiv.org/​abs/​2007.07040.

[75] Martin Fürer. Solving NP-complete problems with quantum search. In Latin American Symposium on Theoretical Informatics (LATIN-2008), pages 784–792. Springer, 2008. 10.1007/​978-3-540-78773-0_67.

[76] Nicolas J. Cerf, Lov K. Grover, and Colin P. Williams. Nested quantum search and structured problems. Phys. Rev. A, 61: 032303, 2000. 10.1103/​PhysRevA.61.032303.

[77] Thomas G. Draper and Samuel A. Kutin. $\langle\mathsf{q}|\mathsf{pic}\rangle$: Quantum circuit diagrams in LaTeX, 2020. URL https:/​/​www.github.com/​qpic/​qpic.

[78] Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. arXiv:quant-ph/​9607014, 1996. URL https:/​/​arxiv.org/​abs/​quant-ph/​9607014.

[79] Pascal Benchimol, Willem-Jan Van Hoeve, Jean-Charles Régin, Louis-Martin Rousseau, and Michel Rueher. Improved filtering for weighted circuit constraints. Constraints, 17 (3): 205–233, 2012. 10.1007/​s10601-012-9119-x.

[80] Nicolas Beldiceanu, Irit Katriel, and Sven Thiel. Filtering algorithms for the same constraint. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR-2004), pages 65–79. Springer, 2004. 10.1007/​978-3-540-24664-0_5.

[81] Rong Qu and Fang He. A hybrid constraint programming approach for nurse rostering problems. In Applications and Innovations in Intelligent Systems (SGAI-2008), pages 211–224. Springer, 2008. 10.1007/​978-1-84882-215-3_16.

[82] Michael A Trick. Integer and constraint programming approaches for round-robin tournament scheduling. In Practice and Theory of Automated Timetabling (PATAT-2002), pages 63–77. Springer, 2002. 10.1007/​978-3-540-45157-0_4.

[83] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC-2019), page 193–204. Association for Computing Machinery, 2019. 10.1145/​3313276.3316366.

Cited by

[1] Lin Lin and Yu Tong, "Heisenberg-Limited Ground-State Energy Estimation for Early Fault-Tolerant Quantum Computers", PRX Quantum 3 1, 010318 (2022).

[2] Yulong Dong, Lin Lin, and Yu Tong, "Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices", arXiv:2204.05955.

The above citations are from SAO/NASA ADS (last updated successfully 2022-05-18 05:34:47). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2022-05-18 05:34:45).