1Chemical Physics Theory Group, Department of Chemistry, University of Toronto, Canada.
2Department of Computer Science, University of Toronto, Canada.
3Barcelona Supercomputing Center, Barcelona, Spain
4Vector Institute for Artificial Intelligence, Toronto, Canada.
5Max Planck Institute for the Science of Light (MPL), Erlangen, Germany
6Canadian Institute for Advanced Research (CIFAR) Lebovic Fellow, Toronto, Canada
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Logic Artificial Intelligence (AI) is a subfield of AI where variables can take two defined arguments, True or False, and are arranged in clauses that follow the rules of formal logic. Several problems that span from physical systems to mathematical conjectures can be encoded into these clauses and solved by checking their satisfiability (SAT). In contrast to machine learning approaches where the results can be approximations or local minima, Logic AI delivers formal and mathematically exact solutions to those problems. In this work, we propose the use of logic AI for the design of optical quantum experiments. We show how to map into a SAT problem the experimental preparation of an arbitrary quantum state and propose a logic-based algorithm, called Klaus, to find an interpretable representation of the photonic setup that generates it. We compare the performance of Klaus with the state-of-the-art algorithm for this purpose based on continuous optimization. We also combine both logic and numeric strategies to find that the use of logic AI significantly improves the resolution of this problem, paving the path to developing more formal-based approaches in the context of quantum physics experiments.
Featured image: Diagram of Klaus algorithm workflow.
Popular summary
Problems spanning physical systems to mathematical conjectures can be solved using Logic AI. This work represents the first application to the design of quantum experiments.
► BibTeX data
► References
[1] John McCarthy et al. “Programs with common sense”. RLE and MIT computation center. (1960).
[2] Nils J Nilsson. “Probabilistic logic revisited”. Artificial intelligence 59, 39–42 (1994).
https://doi.org/10.1016/0004-3702(93)90167-A
[3] Adnan Darwiche. “Three modern roles for logic in ai”. Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database SystemsPage 229–243 (2020).
https://doi.org/10.1145/3375395.3389131
[4] Johannes K Fichte, Markus Hecher, and Stefan Szeider. “A time leap challenge for sat-solving”. International Conference on Principles and Practice of Constraint ProgrammingPages 267–285 (2020).
https://doi.org/10.1007/978-3-030-58475-7_16
[5] Marijn JH Heule, Oliver Kullmann, and Victor W Marek. “Solving and verifying the boolean pythagorean triples problem via cube-and-conquer”. International Conference on Theory and Applications of Satisfiability TestingPages 228–245 (2016).
https://doi.org/10.1007/978-3-319-40970-2_15
[6] Joshua Brakensiek, Marijn Heule, John Mackey, and David Narváez. “The resolution of keller’s conjecture”. International Joint Conference on Automated ReasoningPages 48–65 (2020).
https://doi.org/10.1007/978-3-030-51074-9_4
[7] Aubrey DNJ de Grey. “The chromatic number of the plane is at least 5” (2018). arXiv:1804.02385.
arXiv:1804.02385
[8] Craig S Kaplan. “Heesch numbers of unmarked polyforms” (2021). arXiv:2105.09438.
arXiv:2105.09438
[9] Emre Yolcu, Scott Aaronson, and Marijn JH Heule. “An automated approach to the collatz conjecture” (2021). arXiv:2105.14697.
arXiv:2105.14697
[10] Evelyn Lamb. “Two-hundred-terabyte maths proof is largest ever”. Nature News 534, 17 (2016).
https://doi.org/10.1038/nature.2016.19990
[11] Robert Wille, Nils Przigoda, and Rolf Drechsler. “A compact and efficient sat encoding for quantum circuits”. 2013 AfriconPages 1–6 (2013).
https://doi.org/10.1109/AFRCON.2013.6757630
[12] Robert Wille, Lukas Burgholzer, and Alwin Zulehner. “Mapping quantum circuits to ibm qx architectures using the minimal number of swap and h operations”. 2019 56th ACM/IEEE Design Automation Conference (DAC)Pages 1–6 (2019). arXiv:1907.02026.
https://doi.org/10.48550/arXiv.1907.02026
arXiv:1907.02026
[13] Giulia Meuli, Mathias Soeken, and Giovanni De Micheli. “Sat-based ${$CNOT, T$}$ quantum circuit synthesis”. International Conference on Reversible ComputationPages 175–188 (2018).
https://doi.org/10.1007/978-3-319-99498-7_12
[14] Mingsheng Ying and Zhengfeng Ji. “Symbolic verification of quantum circuits” (2020). arXiv:2010.03032.
arXiv:2010.03032
[15] Mario Krenn, Jakob Kottmann, Nora Tischler, and Alan Aspuru-Guzik. “Conceptual understanding through efficient automated design of quantum optical experiments”. Physical Review X 11, 031044 (2021).
https://doi.org/10.1103/PhysRevX.11.031044
[16] Sara Bartolucci, Patrick Birchall, Hector Bombin, Hugo Cable, Chris Dawson, Mercedes Gimeno-Segovia, Eric Johnston, Konrad Kieling, Naomi Nickerson, Mihir Pant, et al. “Fusion-based quantum computation” (2021). arXiv:2101.09310.
arXiv:2101.09310
[17] Mario Krenn, Armin Hochrainer, Mayukh Lahiri, and Anton Zeilinger. “Entanglement by path identity”. Phys. Rev. Lett. 118, 080401 (2017).
https://doi.org/10.1103/PhysRevLett.118.080401
[18] Mario Krenn, Xuemei Gu, and Anton Zeilinger. “Quantum experiments and graphs: Multiparty states as coherent superpositions of perfect matchings”. Phys. Rev. Lett. 119, 240403 (2017).
https://doi.org/10.1103/PhysRevLett.119.240403
[19] Xuemei Gu, Manuel Erhard, Anton Zeilinger, and Mario Krenn. “Quantum experiments and graphs ii: Quantum interference, computation, and state generation”. Proceedings of the National Academy of Sciences 116, 4147–4155 (2019).
https://doi.org/10.1073/pnas.1815884116
[20] Xuemei Gu, Lijun Chen, Anton Zeilinger, and Mario Krenn. “Quantum experiments and graphs. iii. high-dimensional and multiparticle entanglement”. Phys. Rev. A 99, 032338 (2019).
https://doi.org/10.1103/PhysRevA.99.032338
[21] Mario Krenn, Manuel Erhard, and Anton Zeilinger. “Computer-inspired quantum experiments”. Nature Reviews Physics 2, 649–661 (2020).
https://doi.org/10.1038/s42254-020-0230-4
[22] Jian-Wei Pan, Zeng-Bing Chen, Chao-Yang Lu, Harald Weinfurter, Anton Zeilinger, and Marek Żukowski. “Multiphoton entanglement and interferometry”. Rev. Mod. Phys. 84, 777–838 (2012).
https://doi.org/10.1103/RevModPhys.84.777
[23] Dustin Mixon. “A graph coloring problem from quantum physics (with prizes!)”. https://bit.ly/3fPFK1U. Accessed: 2021-08-09.
https://bit.ly/3fPFK1U
[24] Mario Krenn, Xuemei Gu, and Daniel Soltész. “Questions on the structure of perfect matchings inspired by quantum physics”. Proceedings of the 2nd Croatian Combinatorial Days (2019).
https://doi.org/10.5592/CO/CCD.2018.05
[25] Ilya Bogdanov. “Solution to graphs with only disjoint perfect matchings”. https://bit.ly/3iAu6K1. Accessed: 2021-08-09.
https://bit.ly/3iAu6K1
[26] Mario Krenn. “Combinatorial equation system with exponentially many equations in quadratic many variables”. https://bit.ly/3lOUMJ9. Accessed: 2021-08-09.
https://bit.ly/3lOUMJ9
[27] Marcus Huber and Julio I. de Vicente. “Structure of multidimensional entanglement in multipartite systems”. Phys. Rev. Lett. 110, 030501 (2013).
https://doi.org/10.1103/PhysRevLett.110.030501
[28] Robert Raussendorf, Daniel E. Browne, and Hans J. Briegel. “Measurement-based quantum computation on cluster states”. Phys. Rev. A 68, 022312 (2003).
https://doi.org/10.1103/PhysRevA.68.022312
[29] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. “Prediction by linear regression on a quantum computer”. Phys. Rev. A 94, 022342 (2016).
https://doi.org/10.1103/PhysRevA.94.022342
[30] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. “Quantum algorithm for linear systems of equations”. Phys. Rev. Lett. 103, 150502 (2009).
https://doi.org/10.1103/PhysRevLett.103.150502
[31] Jianwei Wang, Stefano Paesani, Yunhong Ding, Raffaele Santagati, Paul Skrzypczyk, Alexia Salavrakos, Jordi Tura, Remigiusz Augusiak, Laura Mančinska, Davide Bacco, et al. “Multidimensional quantum entanglement with large-scale integrated optics”. Science 360, 285–291 (2018).
https://doi.org/10.1126/science.aar7053
[32] Stefano Paesani, Jacob F. F. Bulmer, Alex E. Jones, Raffaele Santagati, and Anthony Laing. “Scheme for universal high-dimensional quantum computation with linear optics”. Phys. Rev. Lett. 126, 230504 (2021).
https://doi.org/10.1103/PhysRevLett.126.230504
[33] Hui Wang, Jian Qin, Xing Ding, Ming-Cheng Chen, Si Chen, Xiang You, Yu-Ming He, Xiao Jiang, L. You, Z. Wang, C. Schneider, Jelmer J. Renema, Sven Höfling, Chao-Yang Lu, and Jian-Wei Pan. “Boson sampling with 20 input photons and a 60-mode interferometer in a $1{0}^{14}$-dimensional hilbert space”. Phys. Rev. Lett. 123, 250503 (2019).
https://doi.org/10.1103/PhysRevLett.123.250503
[34] Jianwei Wang, Fabio Sciarrino, Anthony Laing, and Mark G Thompson. “Integrated photonic quantum technologies”. Nature Photonics 14, 273–284 (2020).
https://doi.org/10.1038/s41566-019-0532-1
[35] Max Tillmann, Si-Hui Tan, Sarah E. Stoeckl, Barry C. Sanders, Hubert de Guise, René Heilmann, Stefan Nolte, Alexander Szameit, and Philip Walther. “Generalized multiphoton quantum interference”. Phys. Rev. X 5, 041015 (2015).
https://doi.org/10.1103/PhysRevX.5.041015
[36] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, et al. “Quantum computational advantage using photons”. Science 370, 1460–1463 (2020).
https://doi.org/10.1126/science.abe8770
[37] Demian A. Battaglia, Giuseppe E. Santoro, and Erio Tosatti. “Optimization by quantum annealing: Lessons from hard satisfiability problems”. Phys. Rev. E 71, 066707 (2005).
https://doi.org/10.1103/PhysRevE.71.066707
[38] Juexiao Su, Tianheng Tu, and Lei He. “A quantum annealing approach for boolean satisfiability problem”. 2016 53nd ACM/EDAC/IEEE Design Automation Conference (DAC)Pages 1–6 (2016).
https://doi.org/10.1145/2897937.2897973
[39] Alberto Leporati and Sara Felloni. “Three “quantum” algorithms to solve 3-sat”. Theoretical Computer Science 372, 218–241 (2007).
https://doi.org/10.1016/j.tcs.2006.11.026
[40] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. “A quantum approximate optimization algorithm” (2014). arXiv:1411.4028.
arXiv:1411.4028
[41] Artur García-Sáez and José I Latorre. “An exact tensor network for the 3sat problem”. Quantum Information & Computation 12, 283–292 (2012).
https://doi.org/10.5555/2230976.2230984
[42] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Broeck. “A semantic loss function for deep learning with symbolic knowledge”. International conference on machine learningPages 5502–5511 (2018). url: proceedings.mlr.press/v80/xu18h.
https://proceedings.mlr.press/v80/xu18h
[43] Grigori S Tseitin. “On the complexity of derivation in propositional calculus”. Automation of reasoningPages 466–483 (1983).
https://doi.org/10.1007/978-3-642-81955-1_28
[44] Martin Davis, George Logemann, and Donald Loveland. “A machine program for theorem-proving”. Communications of the ACM 5, 394–397 (1962).
https://doi.org/10.1145/368273.368557
[45] Niklas Eén and Niklas Sörensson. “An extensible SAT-solver”. International conference on theory and applications of satisfiability testingPages 502–518 (2003).
https://doi.org/10.1007/978-3-540-24605-3_37
[46] Niklas Eén and Niklas Sörensson. “The MiniSAT page”. http://minisat.se/Main.html (2021). Accessed: 2021-08-05.
http://minisat.se/Main.html
Cited by
[1] Anna Dawid, Julian Arnold, Borja Requena, Alexander Gresch, Marcin Płodzień, Kaelan Donatella, Kim A. Nicoli, Paolo Stornati, Rouven Koch, Miriam Büttner, Robert Okuła, Gorka Muñoz-Gil, Rodrigo A. Vargas-Hernández, Alba Cervera-Lierta, Juan Carrasquilla, Vedran Dunjko, Marylou Gabrié, Patrick Huembeli, Evert van Nieuwenburg, Filippo Vicentini, Lei Wang, Sebastian J. Wetzel, Giuseppe Carleo, Eliška Greplová, Roman Krems, Florian Marquardt, Michał Tomza, Maciej Lewenstein, and Alexandre Dauphin, “Modern applications of machine learning in quantum sciences”, arXiv:2204.04198.
[2] Mario Krenn, Jonas Landgraf, Thomas Foesel, and Florian Marquardt, “Artificial Intelligence and Machine Learning for Quantum Technologies”, arXiv:2208.03836.
[3] Moshe Y. Vardi and Zhiwei Zhang, “Quantum-Inspired Perfect Matching under Vertex-Color Constraints”, arXiv:2209.13063.
[4] L. Sunil Chandran and Rishikesh Gajjala, “Perfect Matchings and Quantum Physics: Progress on Krenn’s Conjecture”, arXiv:2202.05562.
The above citations are from SAO/NASA ADS (last updated successfully 2022-10-15 14:52:54). 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-10-15 14:52:52).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
