Document Open Access Logo

Circuit Extraction for ZX-Diagrams Can Be #P-Hard

Authors Niel de Beaudrap , Aleks Kissinger , John van de Wetering

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.119.pdf
  • Filesize: 0.88 MB
  • 19 pages

Document Identifiers

Author Details

Niel de Beaudrap
  • University of Sussex, UK
Aleks Kissinger
  • University of Oxford, UK
John van de Wetering
  • Radboud University Nijmegen, The Netherlands
  • University of Oxford, UK

Funding

  • Kissinger, Aleks: Acknowledges support from AFOSR grant FA2386-18-1-4028.
  • van de Wetering, John: Acknowledges support from an NWO Rubicon Personal Grant.

Acknowledgements

The authors wish to thank the anonymous reviewers for their valuable suggestions regarding the presentation of this paper.

Cite AsGet BibTex

Niel de Beaudrap, Aleks Kissinger, and John van de Wetering. Circuit Extraction for ZX-Diagrams Can Be #P-Hard. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 119:1-119:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.119

Abstract

The ZX-calculus is a graphical language for reasoning about quantum computation using ZX-diagrams, a certain flexible generalisation of quantum circuits that can be used to represent linear maps from m to n qubits for any m,n ≥ 0. Some applications for the ZX-calculus, such as quantum circuit optimisation and synthesis, rely on being able to efficiently translate a ZX-diagram back into a quantum circuit of comparable size. While several sufficient conditions are known for describing families of ZX-diagrams that can be efficiently transformed back into circuits, it has previously been conjectured that the general problem of circuit extraction is hard. That is, that it should not be possible to efficiently convert an arbitrary ZX-diagram describing a unitary linear map into an equivalent quantum circuit. In this paper we prove this conjecture by showing that the circuit extraction problem is #P-hard, and so is itself at least as hard as strong simulation of quantum circuits. In addition to our main hardness result, which relies specifically on the circuit representation, we give a representation-agnostic hardness result. Namely, we show that any oracle that takes as input a ZX-diagram description of a unitary and produces samples of the output of the associated quantum computation enables efficient probabilistic solutions to NP-complete problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • ZX-calculus
  • circuit extraction
  • quantum circuits
  • #P

Metrics

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

Related Versions

References

  1. Scott Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 461(2063):3473-3482, 2005. URL: https://doi.org/10.1098/rspa.2005.1546.
  2. Leornard M. Adleman, Jonathan DeMarrais, and Ming-Deh A. Huang. Quantum computability. SIAM Journal on Computing, 26:1524-1540, 1997. URL: https://doi.org/10.1137/S0097539795293639.
  3. Miriam Backens and Aleks Kissinger. ZH: A complete graphical calculus for quantum computations involving classical non-linearity. In Peter Selinger and Giulio Chiribella, editors, Proceedings of the 15th International Conference on Quantum Physics and Logic, Halifax, Canada, 3-7th June 2018, volume 287 of Electronic Proceedings in Theoretical Computer Science, pages 18-34. Open Publishing Association, 2019. URL: https://doi.org/10.4204/EPTCS.287.2.
  4. 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, March 2021. URL: https://doi.org/10.22331/q-2021-03-25-421.
  5. Adam Bouland and Tudor Giurgica-Tiron. Efficient universal quantum compilation: An inverse-free Solovay-Kitaev algorithm. arXiv preprint, 2021. URL: http://arxiv.org/abs/2112.02040.
  6. Daniel E. Browne, Elham Kashefi, Mehdi Mhalla, and Simon Perdrix. Generalized flow and determinism in measurement-based quantum computation. New Journal of Physics, 9(8):250, 2007. URL: https://doi.org/10.1088/1367-2630/9/8/250.
  7. David Buchfuhrer and Christopher Umans. The complexity of Boolean formula minimization. Journal of Computer and System Sciences, 77(1):142-153, 2011. Celebrating Karp’s Kyoto Prize. URL: https://doi.org/10.1016/j.jcss.2010.06.011.
  8. Titouan Carette. Wielding the ZX-calculus, Flexsymmetry, Mixed States, and Scalable Notations. PhD thesis, Loria, Université de Lorraine, 2021. URL: https://hal.archives-ouvertes.fr/tel-03468027/document.
  9. 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, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 108:1-108:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.108.
  10. Bob Coecke, Giovanni de Felice, Konstantinos Meichanetzidis, and Alexis Toumi. Foundations for Near-Term Quantum Natural Language Processing. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.03755.
  11. Bob Coecke and Ross Duncan. Interacting quantum observables. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, 2008. URL: https://doi.org/10.1007/978-3-540-70583-3_25.
  12. Bob Coecke and Ross Duncan. Interacting quantum observables: categorical algebra and diagrammatics. New Journal of Physics, 13:043016, 2011. URL: https://doi.org/10.1088/1367-2630/13/4/043016.
  13. Bob Coecke and Aleks Kissinger. Picturing Quantum Processes. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781316219317.
  14. Richard D. P. East, John van de Wetering, Nicholas Chancellor, and Adolfo G. Grushin. AKLT-states as ZX-diagrams: diagrammatic reasoning for quantum states. PRX Quantum, 3:010302, January 2022. URL: https://doi.org/10.1103/PRXQuantum.3.010302.
  15. Carsten Damm, Markus Holzer, and Pierre McKenzie. The complexity of tensor calculus. Computational Complexity, 11(1):54-89, 2002. URL: https://doi.org/10.1007/s00037-000-0170-4.
  16. Christopher M. Dawson and Michael A. Nielsen. The solovay-kitaev algorithm. arXiv preprint, 2005. URL: http://arxiv.org/abs/0505030.
  17. Niel de Beaudrap. Well-tempered ZX and ZH Calculi. In Benoît Valiron, Shane Mansfield, Pablo Arrighi, and Prakash Panangaden, editors, Proceedings 17th International Conference on Quantum Physics and Logic, Paris, France, June 2 - 6, 2020, volume 340 of Electronic Proceedings in Theoretical Computer Science, pages 13-45. Open Publishing Association, 2021. URL: https://doi.org/10.4204/EPTCS.340.2.
  18. Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang. Techniques to Reduce π/4-Parity-Phase Circuits, Motivated by the ZX Calculus. In Bob Coecke and Matthew Leifer, editors, Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10-14 June 2019, volume 318 of Electronic Proceedings in Theoretical Computer Science, pages 131-149. Open Publishing Association, 2020. URL: https://doi.org/10.4204/EPTCS.318.9.
  19. Niel de Beaudrap, Ross Duncan, Dominic Horsman, and Simon Perdrix. Pauli Fusion: a Computational Model to Realise Quantum Transformations from ZX Terms. In Bob Coecke and Matthew Leifer, editors, Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10-14 June 2019, volume 318 of Electronic Proceedings in Theoretical Computer Science, pages 85-105. Open Publishing Association, 2020. URL: https://doi.org/10.4204/EPTCS.318.6.
  20. Niel de Beaudrap and Dominic Horsman. The ZX calculus is a language for surface code lattice surgery. Quantum, 4, 2020. URL: https://doi.org/10.22331/q-2020-01-09-218.
  21. Niel de Beaudrap, Aleks Kissinger, and Konstantinos Meichanetzidis. Tensor Network Rewriting Strategies for Satisfiability and Counting. In Benoît Valiron, Shane Mansfield, Pablo Arrighi, and Prakash Panangaden, editors, Proceedings 17th International Conference on Quantum Physics and Logic, Paris, France, June 2 - 6, 2020, volume 340 of Electronic Proceedings in Theoretical Computer Science, pages 46-59. Open Publishing Association, 2021. URL: https://doi.org/10.4204/EPTCS.340.3.
  22. Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus. Quantum, 4:279, June 2020. URL: https://doi.org/10.22331/q-2020-06-04-279.
  23. Ross Duncan and Simon Perdrix. Rewriting Measurement-Based Quantum Computations with Generalised Flow. In Proceedings of ICALP, Lecture Notes in Computer Science, pages 285-296. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-14162-1_24.
  24. Richard D. P. East, Pierre Martin-Dussaud, and John van de Wetering. Spin-networks in the ZX-calculus. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.03114.
  25. Michael R Garey and David S Johnson. Computers and intractability, volume 174. freeman San Francisco, 1979. Google Scholar
  26. Craig Gidney and Austin G. Fowler. Efficient magic state factories with a catalyzed |CCZ⟩ to 2|T⟩ transformation. Quantum, 3:135, April 2019. URL: https://doi.org/10.22331/q-2019-04-30-135.
  27. Craig Gidney and Austin G. Fowler. Flexible layout of surface code computations using AutoCCZ states. arXiv preprint, 2019. URL: http://arxiv.org/abs/1905.08916.
  28. Amar Hadzihasanovic. A diagrammatic axiomatisation for qubit entanglement. In 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 573-584. IEEE, 2015. URL: https://doi.org/10.1109/LICS.2015.59.
  29. Michael Hanks, Marta P. Estarellas, William J. Munro, and Kae Nemoto. Effective Compression of Quantum Braided Circuits Aided by ZX-Calculus. Physical Review X, 10:041030, 2020. URL: https://doi.org/10.1103/PhysRevX.10.041030.
  30. C. Horsman. Quantum picturalism for topological cluster-state computing. New Journal of Physics, 13(9):095011, 2011. URL: https://doi.org/10.1088/1367-2630/13/9/095011.
  31. C. Horsman, Austin G. Fowler, Simon Devitt, and Rodney Van Meter. Surface code quantum computing by lattice surgery. New Journal of Physics, 14:123011, 2012. URL: https://doi.org/10.1088/1367-2630/14/12/123011.
  32. Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries. J. ACM, 51(4):671-697, July 2004. URL: https://doi.org/10.1145/1008731.1008738.
  33. Aleks Kissinger and Arianne Meijer-van de Griend. CNOT circuit extraction for topologically-constrained quantum memories. Quantum Information and Computation, 20:581-596, 2020. URL: https://doi.org/10.26421/QIC20.7-8.
  34. Aleks Kissinger and John van de Wetering. Reducing the number of non-Clifford gates in quantum circuits. Physical Review A, 102:022406, August 2020. URL: https://doi.org/10.1103/PhysRevA.102.022406.
  35. Aleks Kissinger and John van de Wetering. Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions. Quantum Science and Technology, 2022. URL: https://doi.org/10.1088/2058-9565/ac5d20.
  36. Alexei Y. Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191-1249, 1997. Google Scholar
  37. Kang Feng Ng and Quanlong Wang. A universal completion of the ZX-calculus. Preprint, 2017. URL: http://arxiv.org/abs/1706.09877.
  38. M. A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge university press, 2010. URL: https://doi.org/10.1119/1.1463744.
  39. Roger Penrose. Applications of negative dimensional tensors. In Combinatorial Mathematics and its Applications, pages 221-244. Academic Press, 1971. Google Scholar
  40. Robert Raussendorf and Hans J. Briegel. A One-Way Quantum Computer. Physical Review Letters, 86:5188-5191, May 2001. URL: https://doi.org/10.1103/PhysRevLett.86.5188.
  41. Will Simmons. Relating Measurement Patterns to Circuits via Pauli Flow. In Chris Heunen and Miriam Backens, editors, Proceedings 18th International Conference on Quantum Physics and Logic, Gdansk, Poland, and online, 7-11 June 2021, volume 343 of Electronic Proceedings in Theoretical Computer Science, pages 50-101. Open Publishing Association, 2021. URL: https://doi.org/10.4204/EPTCS.343.4.
  42. Larry J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3:1-22, 1977. URL: https://doi.org/10.1016/0304-3975(76)90061-X.
  43. Seinosuke Toda. PP is as hard as the Polynomial-Time Hierarchy. SIAM Journal on Computing, pages 865-877, October 1991. URL: https://doi.org/10.1137/0220053.
  44. Alex Townsend-Teague and Konstantinos Meichanetzidis. Classifying Complexity with the ZX-Calculus: Jones Polynomials and Potts Partition Functions. arXiv preprint, 2021. URL: http://arxiv.org/abs/2103.06914.
  45. L G Valiant and V V Vazirani. NP is as Easy as Detecting Unique Solutions. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC '85, pages 458-463, New York, NY, USA, 1985. Association for Computing Machinery. URL: https://doi.org/10.1145/22145.22196.
  46. Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410-421, 1979. URL: https://doi.org/10.1137/0208032.
  47. John van de Wetering. ZX-calculus for the working quantum computer scientist. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.13966.
  48. Maarten Van Den Nest. Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond. Quantum Information & Computation, 10(3):258-271, 2010. URL: https://doi.org/10.5555/2011350.2011356.
  49. Renaud Vilmart. A Near-Minimal Axiomatisation of ZX-Calculus for Pure Qubit Quantum Mechanics. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-10, 2019. URL: https://doi.org/10.1109/LICS.2019.8785765.
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 Imprint Privacy Contact