Document Open Access Logo

LO_v-Calculus: A Graphical Language for Linear Optical Quantum Circuits

Authors Alexandre Clément , Nicolas Heurtel , Shane Mansfield, Simon Perdrix , Benoît Valiron

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.35.pdf
  • Filesize: 0.85 MB
  • 16 pages

Document Identifiers

Author Details

Alexandre Clément
  • Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Nicolas Heurtel
  • Quandela, 7 Rue Léonard de Vinci, 91300 Massy, France
  • Université Paris-Saclay, CentraleSupélec, Inria, CNRS, ENS Paris-Saclay, Laboratoire Méthodes Formelles, 91190 Gif-sur-Yvette, France
Shane Mansfield
  • Quandela, 7 Rue Léonard de Vinci, 91300 Massy, France
Simon Perdrix
  • Inria Mocqua, LORIA, CNRS, Université de Lorraine, F-54000 Nancy, France
Benoît Valiron
  • Université Paris-Saclay, CentraleSupélec, Inria, CNRS, ENS Paris-Saclay, Laboratoire Méthodes Formelles, 91190 Gif-sur-Yvette, France

Funding

This work is funded by ANR-17-CE25-0009 SoftQPro, ANR-17-CE24-0035 VanQuTe, PIA-GDN/Quantex, and LUE / UOQ, the PEPR integrated project EPiQ ANR-22-PETQ-0007 part of Plan France 2030, and by "Investissements d'avenir" (ANR-15-IDEX-02) program of the French National Research Agency; the European Project NExt ApplicationS of Quantum Computing (NEASQC), funded by Horizon 2020 Program inside the call H2020-FETFLAG-2020-01(Grant Agreement 951821), and the HPCQS European High-Performance Computing Joint Undertaking (JU) under grant agreement No 101018180.

Cite As Get BibTex

Alexandre Clément, Nicolas Heurtel, Shane Mansfield, Simon Perdrix, and Benoît Valiron. LO_v-Calculus: A Graphical Language for Linear Optical Quantum Circuits. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.35

Abstract

We introduce the LO_v-calculus, a graphical language for reasoning about linear optical quantum circuits with so-called vacuum state auxiliary inputs. We present the axiomatics of the language and prove its soundness and completeness: two LO_v-circuits represent the same quantum process if and only if one can be transformed into the other with the rules of the LO_v-calculus. We give a confluent and terminating rewrite system to rewrite any polarisation-preserving LO_v-circuit into a unique triangular normal form, inspired by the universal decomposition of Reck et al. (1994) for linear optical quantum circuits.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
  • Theory of computation → Axiomatic semantics
  • Hardware → Quantum computation
  • Hardware → Quantum communication and cryptography
Keywords
  • Quantum Computing
  • Graphical Language
  • Linear Optical Circuits
  • Linear Optical Quantum Computing
  • Completeness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. Theory of Computing, 9(4):143-252, 2013. URL: https://doi.org/10.4086/toc.2013.v009a004.
  2. Scott Aaronson and Lijie Chen. Complexity-theoretic foundations of quantum supremacy experiments, 2016. URL: http://arxiv.org/abs/1612.05903.
  3. Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A. Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505-510, 2019. Google Scholar
  4. Miriam Backens and Aleks Kissinger. ZH: A complete graphical calculus for quantum computations involving classical non-linearity. Electronic Proceedings in Theoretical Computer Science, 287:23-42, 2019. Google Scholar
  5. Miriam Backens, Hector Miller-Bakewell, Giovanni de Felice, Leo Lobski, and John van de Wetering. There and back again: A circuit extraction tale. Quantum, 5:421, 2021. Google Scholar
  6. Sara Bartolucci, Patrick Birchall, Hector Bombin, Hugo Cable, Chris Dawson, Mercedes Gimeno-Segovia, Eric Johnston, Konrad Kieling, Naomi Nickerson, Mihir Pant, Fernando Pastawski, Terry Rudolph, and Chris Sparro. Fusion-based quantum computation, 2021. URL: http://arxiv.org/abs/2101.09310.
  7. Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. Theoretical Computer Science, 560:7-11, 2014. Theoretical Aspects of Quantum Cryptography - celebrating 30 years of BB84. URL: https://doi.org/10.1016/j.tcs.2014.05.025.
  8. Benjamin Bichsel, Maximilian Baader, Timon Gehr, and Martin T. Vechev. Silq: a high-level quantum language with safe uncomputation and intuitive semantics. In Alastair F. Donaldson and Emina Torlak, editors, Proceedings of the 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI'20, pages 286-300. ACM, 2020. URL: https://doi.org/10.1145/3385412.3386007.
  9. Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15(2):159-163, 2019. URL: https://doi.org/10.1038/s41567-018-0318-2.
  10. Cyril Branciard, Alexandre Clément, Mehdi Mhalla, and Simon Perdrix. Coherent control and distinguishability of quantum channels via PBS-diagrams. In Filippo Bonchi and Simon J. Puglisi, editors, Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, volume 202 of LIPIcs, pages 22:1-22:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.MFCS.2021.22.
  11. Titouan Carette, Dominic Horsman, and Simon Perdrix. SZX-calculus: Scalable graphical quantum reasoning. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, volume 138 of LIPIcs, pages 55:1-55:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.55.
  12. Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Completeness of graphical languages for mixed states quantum mechanics. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, volume 132 of LIPIcs, pages 108:1-108:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.108.
  13. Christophe Chareton, Sébastien Bardin, François Bobot, Valentin Perrelle, and Benoît Valiron. An automated deductive verification framework for circuit-building quantum programs. In Nobuko Yoshida, editor, Programming Languages and Systems, volume 12648 of Lecture Notes in Computer Science (LNCS), pages 148-177, Cham, 2021. Springer International Publishing. URL: https://doi.org/10.1007/978-3-030-72019-3_6.
  14. Alexandre Clément, Nicolas Heurtel, Shane Mansfield, Simon Perdrix, and Benoît Valiron. A complete equational theory for quantum circuits, 2022. URL: https://doi.org/10.48550/ARXIV.2206.10577.
  15. Alexandre Clément, Nicolas Heurtel, Shane Mansfield, Simon Perdrix, and Benoît Valiron. LOv-calculus: A graphical language for linear optical quantum circuits, 2022. URL: http://arxiv.org/abs/2204.11787.
  16. Alexandre Clément and Simon Perdrix. PBS-calculus: A graphical language for coherent control of quantum computations. In Javier Esparza and Daniel Kráľ, editors, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1-24:14, Dagstuhl, Germany, August 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.24.
  17. Alexandre Clément and Simon Perdrix. Minimising resources of coherently controlled quantum computations, 2022. Accepted at MFCS 2022. URL: http://arxiv.org/abs/2202.05260.
  18. William R. Clements, Peter C. Humphreys, Benjamin J. Metcalf, W. Steven Kolthammer, and Ian A. Walmsley. Optimal design for universal multiport interferometers. Optica, 3(12):1460-1465, December 2016. URL: https://doi.org/10.1364/OPTICA.3.001460.
  19. Robin Cockett and Cole Comfort. The category TOF. In Peter Selinger and Giulio Chiribella, editors, Proceedings 15th International Conference on Quantum Physics and Logic, QPL 2018, volume 287 of EPTCS, pages 67-84, 2019. Google Scholar
  20. Robin Cockett, Cole Comfort, and Priyaa Srinivasan. The category CNOT. In Peter Selinger and Giulio Chiribella, editors, Proceedings 15th International Conference on Quantum Physics and Logic, QPL 2018, volume 287 of EPTCS, pages 258-293, 2019. URL: https://doi.org/10.4204/EPTCS.266.18.
  21. Bob Coecke and Aleks Kissinger. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781316219317.
  22. Ugo Dal Lago, Claudia Faggian, Benoît Valiron, and Akira Yoshimizu. The geometry of parallelism: Classical, probabilistic, and quantum effects. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, pages 833-845, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3009837.3009859.
  23. Niel de Beaudrap and Dominic Horsman. The ZX calculus is a language for surface code lattice surgery. Quantum, 4:218, 2020. URL: http://arxiv.org/abs/1704.08670.
  24. Giovanni de Felice and Bob Coecke. Quantum linear optics via string diagrams, 2022. URL: http://arxiv.org/abs/2204.12985.
  25. Ross Duncan, Aleks Kissinger, Simon Perdrix, and John Van De Wetering. Graph-theoretic simplification of quantum circuits with the ZX-calculus. Quantum, 4:279, 2020. Google Scholar
  26. Ross Duncan and Maxime Lucas. Verifying the Steane code with Quantomatic. In Bob Coecke and Matty J. Hoban, editors, Proceedings of the 10th International Workshop on Quantum Physics and Logic, QPL 2013, volume 171 of EPTCS, pages 33-49, 2013. URL: https://doi.org/10.4204/EPTCS.171.4.
  27. Ross Duncan and Simon Perdrix. Rewriting measurement-based quantum computations with generalised flow. In International Colloquium on Automata, Languages, and Programming, pages 285-296. Springer, 2010. Google Scholar
  28. Artur K. Ekert. Quantum cryptography based on Bell’s theorem. Physical Review Letters, 67:661-663, August 1991. URL: https://doi.org/10.1103/PhysRevLett.67.661.
  29. Yuan Feng, Ernst Moritz Hahn, Andrea Turrini, and Lijun Zhang. QPMC: a model checker for quantum programs and protocols. In Nikolaj Bjørner and Frank S. de Boer, editors, Proceedings of the 20th International Symposium on Formal Methods (FM 2015), volume 9109 of Lecture Notes in Computer Science, pages 265-272. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-19249-9_17.
  30. Richard P. Feynman and Albert R. Hibbs. Quantum Mechanics and Path Integrals. McGraw-Hill Publishing Company, 1965. Google Scholar
  31. Liam Garvie and Ross Duncan. Verifying the smallest interesting colour code with quantomatic. Electronic Proceedings in Theoretical Computer Science, EPTCS, 266:147-163, 2018. Google Scholar
  32. Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger, and Benoît Valiron. Quipper: A scalable quantum programming language. In Hans-Juergen Boehm and Cormac Flanagan, editors, Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'13, pages 333-342. ACM, 2013. URL: https://doi.org/10.1145/2491956.2462177.
  33. 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 '96, pages 212-219, New York, NY, USA, 1996. Association for Computing Machinery. URL: https://doi.org/10.1145/237814.237866.
  34. Nicolas Heurtel, Andreas Fyrillas, Grégoire de Gliniasty, Raphaël Le Bihan, Sébastien Malherbe, Marceau Pailhas, Boris Bourdoncle, Pierre-Emmanuel Emeriau, Rawad Mezher, Luka Music, et al. Perceval: A software platform for discrete variable photonic quantum computing, 2022. URL: http://arxiv.org/abs/2204.00602.
  35. Anne Hillebrand. Quantum Protocols involving Multiparticle Entanglement and their Representations in the zx-calculus. PhD thesis, University of Oxford, 2011. Google Scholar
  36. Christian Hutslar, Jacques Carette, and Amr Sabry. A library of reversible circuit transformations (work in progress). In Jarkko Kari and Irek Ulidowski, editors, Proceedings of the 10th International Conference on Reversible Computation, RC 2018, volume 11106 of Lecture Notes in Computer Science, pages 339-345. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-99498-7_24.
  37. Ali Javadi-Abhari, Shruti Patil, Daniel Kudrow, Jeff Heckey, Alexey Lvov, Frederic T. Chong, and Margaret Martonosi. ScaffCC: Scalable compilation and analysis of quantum programs. Parallel Computing, 45:2-17, 2015. URL: https://doi.org/10.1016/j.parco.2014.12.001.
  38. Michio Jimbo. Introduction to the Yang-Baxter equation. International Journal of Modern Physics A, 4(15):3759-3777, 1989. Google Scholar
  39. Nathan Killoran, Josh Izaac, Nicolás Quesada, Ville Bergholm, Matthew Amy, and Christian Weedbrook. Strawberry fields: A software platform for photonic quantum computing. Quantum, 3:129, 2019. Google Scholar
  40. Emanuel Knill, Raymond Laflamme, and Gerald J. Milburn. A scheme for efficient quantum computation with linear optics. Nature, 409(6816):46-52, 2001. URL: https://doi.org/10.1038/35051009.
  41. Pieter Kok and Brendon W. Lovett. Introduction to Optical Quantum Information Processing. Cambridge University Press, 2010. Google Scholar
  42. Pieter Kok, William J. Munro, Kae Nemoto, Timothy C. Ralph, Jonathan P. Dowling, and Gerald J. Milburn. Linear optical quantum computing with photonic qubits. Reviews of Modern Physics, 79:135-174, January 2007. URL: https://doi.org/10.1103/RevModPhys.79.135.
  43. Gushu Li, Li Zhou, Nengkun Yu, Yufei Ding, Mingsheng Ying, and Yuan Xie. Projection-based runtime assertions for testing and debugging quantum programs. Proceedings of the ACM on Programming Languages, 4(OOPSLA):150:1-150:29, 2020. URL: https://doi.org/10.1145/3428218.
  44. Saunders MacLane. Categorical algebra. Bulletin of the American Mathematical Society, 71(1):40-106, 1965. URL: https://doi.org/bams/1183526392.
  45. Justin Makary, Neil J. Ross, and Peter Selinger. Generators and relations for real stabilizer operators. In Chris Heunen and Miriam Backens, editors, Proceedings of hte 18th International Conference on Quantum Physics and Logic, QPL 2021, volume 343 of EPTCS, pages 14-36, 2021. URL: https://doi.org/10.4204/EPTCS.343.2.
  46. Jennifer Paykin, Robert Rand, and Steve Zdancewic. QWIRE: a core language for quantum circuits. In Giuseppe Castagna and Andrew D. Gordon, editors, Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL'17, pages 846-858. ACM, 2017. URL: https://doi.org/10.1145/3009837.3009894.
  47. Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L O'brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5(1):1-7, 2014. Google Scholar
  48. Mathias Pont, Riccardo Albiero, Sarah E. Thomas, Nicolò Spagnolo, Francesco Ceccarelli, Giacomo Corrielli, Alexandre Brieussel, Niccolo Somaschi, Hêlio Huet, Abdelmounaim Harouri, Aristide Lemaître, Isabelle Sagnes, Nadia Belabas, Fabio Sciarrino, Roberto Osellame, Pascale Senellart, and Andrea Crespi. Quantifying n-photon indistinguishability with a cyclic integrated interferometer, 2022. URL: http://arxiv.org/abs/2201.13333.
  49. Michael Reck, Anton Zeilinger, Herbert J. Bernstein, and Philip Bertani. Experimental realization of any discrete unitary operator. Physical Review Letters, 73:58-61, July 1994. URL: https://doi.org/10.1103/PhysRevLett.73.58.
  50. Peter Selinger. Towards a quantum programming language. Mathematical Structures in Computer Science, 14(4):527-586, 2004. URL: https://doi.org/10.1017/S0960129504004256.
  51. Peter W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124-134, 1994. URL: https://doi.org/10.1109/SFCS.1994.365700.
  52. Terese. Term Rewriting Systems, volume 55 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2003. Google Scholar
  53. Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, et al. Strong quantum computational advantage using a superconducting quantum processor. Physical Review Letters, 127(18):180501, 2021. Google Scholar
  54. Han-Sen Zhong, Yu-Hao Deng, Jian Qin, Hui Wang, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Dian Wu, Si-Qiu Gong, Hao Su, et al. Phase-programmable Gaussian boson sampling using stimulated squeezed light. Physical Review Letters, 127(18):180502, 2021. Google Scholar
  55. 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(6523):1460-1463, 2020. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact