LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States

Lieuwe Vinkhuijzen1, Tim Coopmans1,2, David Elkouss2,3, Vedran Dunjko1, and Alfons Laarman1

1Leiden University, The Netherlands
2Delft University of Technology, The Netherlands
3Networked Quantum Devices Unit, Okinawa Institute of Science and Technology Graduate University, Okinawa, Japan

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


Efficient methods for the representation and simulation of quantum states and quantum operations are crucial for the optimization of quantum circuits. Decision diagrams (DDs), a well-studied data structure originally used to represent Boolean functions, have proven capable of capturing relevant aspects of quantum systems, but their limits are not well understood. In this work, we investigate and bridge the gap between existing DD-based structures and the stabilizer formalism, an important tool for simulating quantum circuits in the tractable regime. We first show that although DDs were suggested to succinctly represent important quantum states, they actually require exponential space for certain stabilizer states. To remedy this, we introduce a more powerful decision diagram variant, called Local Invertible Map-DD (LIMDD). We prove that the set of quantum states represented by poly-sized LIMDDs strictly contains the union of stabilizer states and other decision diagram variants. Finally, there exist circuits which LIMDDs can efficiently simulate, while their output states cannot be succinctly represented by two state-of-the-art simulation paradigms: the stabilizer decomposition techniques for Clifford + $T$ circuits and Matrix-Product States. By uniting two successful approaches, LIMDDs thus pave the way for fundamentally more powerful solutions for simulation and analysis of quantum computing.

Classical simulation of a quantum circuit is a computationally difficult task. In a straightforward approach, the memory requirements for storing a description of a quantum state grow as $2^n$ for an $n$-qubit circuit. Decision diagrams address this problem by providing a compressed representation of a quantum state. However, the limits of DD-based methods were not well understood. In this work, we investigate and bridge the gap between existing DD-based structures and the stabilizer formalism, another important tool for simulating quantum circuits. We first show that although DDs were suggested to succinctly represent important quantum states, they actually require exponential space for certain stabilizer states. To remedy this, we introduce a more powerful decision diagram variant, called Local Invertible Map-DD (LIMDD). We prove that there are quantum circuits which can be efficiently analyzed by LIMDDs, but not by existing DD-based methods, nor stabilizer decomposition techniques, nor matrix product states. By leveraging the strengths of both DD and the stabilizer formalism in a strictly more succinct data structure, LIMDDs thus pave the way for fundamentally more powerful simulation and analysis of quantum computing.

► BibTeX data

► References

[1] Alwin Zulehner and Robert Wille. ``One-pass design of reversible circuits: Combining embedding and synthesis for reversible logic''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 37, 996–1008 (2017).

[2] Lukas Burgholzer and Robert Wille. ``Improved DD-based equivalence checking of quantum circuits''. In 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC). Pages 127–132. IEEE (2020).

[3] Lukas Burgholzer, Richard Kueng, and Robert Wille. ``Random stimuli generation for the verification of quantum circuits''. In Proceedings of the 26th Asia and South Pacific Design Automation Conference. Pages 767–772. (2021).

[4] Lukas Burgholzer and Robert Wille. ``Advanced equivalence checking for quantum circuits''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 40, 1810–1824 (2020).

[5] John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2, 79 (2018).

[6] Daniel Gottesman. ``The Heisenberg representation of quantum computers'' (1998). url:​abs/​quant-ph/​9807006.

[7] Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Physical Review A 70 (2004).

[8] Daniel Gottesman. ``Stabilizer codes and quantum error correction''. PhD thesis. California Institute of Technology. (1997).

[9] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor. ``Local unitary versus local Clifford equivalence of stabilizer states''. Phys. Rev. A 71, 062323 (2005).

[10] Matthias Englbrecht and Barbara Kraus. ``Symmetries and entanglement of stabilizer states''. Phys. Rev. A 101, 062302 (2020).

[11] Robert Raussendorf and Hans J. Briegel. ``A one-way quantum computer''. Phys. Rev. Lett. 86, 5188–5191 (2001).

[12] Sergey Bravyi, Graeme Smith, and John A. Smolin. ``Trading classical and quantum computational resources''. Phys. Rev. X 6, 021043 (2016).

[13] Sergey Bravyi and David Gosset. ``Improved classical simulation of quantum circuits dominated by Clifford gates''. Phys. Rev. Lett. 116, 250501 (2016).

[14] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard. ``Simulation of quantum circuits by low-rank stabilizer decompositions''. Quantum 3, 181 (2019).

[15] Yifei Huang and Peter Love. ``Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits''. Phys. Rev. A 99, 052307 (2019).

[16] Lucas Kocia and Peter Love. ``Stationary phase method in discrete Wigner functions and classical simulation of quantum circuits''. Quantum 5, 494 (2021).

[17] Lucas Kocia and Mohan Sarovar. ``Classical simulation of quantum circuits using fewer gaussian eliminations''. Physical Review A 103, 022603 (2021).

[18] Sheldon B. Akers. ``Binary decision diagrams''. IEEE Computer Architecture Letters 27, 509–516 (1978).

[19] Randal E. Bryant. ``Graph-based algorithms for Boolean function manipulation''. IEEE Trans. Computers 35, 677–691 (1986).

[20] Randal E Bryant and Yirng-An Chen. ``Verification of arithmetic circuits with binary moment diagrams''. In 32nd Design Automation Conference. Pages 535–541. IEEE (1995).

[21] G.F. Viamontes, I.L. Markov, and J.P. Hayes. ``High-performance QuIDD-based simulation of quantum circuits''. In Proceedings Design, Automation and Test in Europe Conference and Exhibition. Volume 2, pages 1354–1355 Vol.2. (2004).

[22] R. I. Bahar, E. A. Frohm, C. M. Gaona, G. D. Hachtel, E. Macii, A. Pardo, and F. Somenzi. ``Algebraic decision diagrams and their applications''. In Proceedings of 1993 International Conference on Computer Aided Design (ICCAD). Pages 188–191. (1993).

[23] George F Viamontes, Igor L Markov, and John P Hayes. ``Improving gate-level simulation of quantum circuits''. Quantum Information Processing 2, 347–380 (2003).

[24] Masahiro Fujita, Patrick C. McGeer, and JC-Y Yang. ``Multi-terminal binary decision diagrams: An efficient data structure for matrix representation''. Formal methods in system design 10, 149–169 (1997).

[25] E. M. Clarke, K. L. McMillan, X Zhao, M. Fujita, and J. Yang. ``Spectral transforms for large boolean functions with applications to technology mapping''. In Proceedings of the 30th International Design Automation Conference. Pages 54–60. DAC '93New York, NY, USA (1993). Association for Computing Machinery.

[26] Scott Sanner and David McAllester. ``Affine algebraic decision diagrams (AADDs) and their application to structured probabilistic inference''. In Proceedings of the 19th International Joint Conference on Artificial Intelligence. Pages 1384–1390. IJCAI'05San Francisco, CA, USA (2005). Morgan Kaufmann Publishers Inc. url:​Proceedings/​05/​Papers/​1439.pdf.

[27] D Michael Miller and Mitchell A Thornton. ``QMDD: A decision diagram structure for reversible and quantum circuits''. In 36th International Symposium on Multiple-Valued Logic (ISMVL'06). Pages 30–30. IEEE (2006).

[28] Alwin Zulehner and Robert Wille. ``Advanced simulation of quantum computations''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 38, 848–859 (2018).

[29] Xin Hong, Xiangzhen Zhou, Sanjiang Li, Yuan Feng, and Mingsheng Ying. ``A tensor network based decision diagram for representation of quantum circuits''. ACM Trans. Des. Autom. Electron. Syst. 27 (2022).

[30] Stefan Hillmich, Richard Kueng, Igor L. Markov, and Robert Wille. ``As accurate as needed, as efficient as possible: Approximations in DD-based quantum circuit simulation''. In Design, Automation & Test in Europe Conference & Exhibition, DATE 2021, Grenoble, France, February 1-5, 2021. Pages 188–193. IEEE (2021).

[31] George F Viamontes, Igor L Markov, and John P Hayes. ``Quantum circuit simulation''. Springer Science & Business Media. (2009).

[32] Xin Hong, Mingsheng Ying, Yuan Feng, Xiangzhen Zhou, and Sanjiang Li. ``Approximate equivalence checking of noisy quantum circuits''. In 2021 58th ACM/​IEEE Design Automation Conference (DAC). Pages 637–642. (2021).

[33] Hans J. Briegel and Robert Raussendorf. ``Persistent entanglement in arrays of interacting particles''. Phys. Rev. Lett. 86, 910–913 (2001).

[34] Wolfgang Dür, Guifre Vidal, and J Ignacio Cirac. ``Three qubits can be entangled in two inequivalent ways''. Physical Review A 62, 062314 (2000).

[35] Eric Chitambar, Debbie Leung, Laura Mančinska, Maris Ozols, and Andreas Winter. ``Everything you always wanted to know about LOCC (but were afraid to ask)''. Communications in Mathematical Physics 328, 303–326 (2014).

[36] Steven R White. ``Density matrix formulation for quantum renormalization groups''. Physical review letters 69, 2863 (1992).

[37] D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac. ``Matrix product state representations''. Quantum Information & Computation 7, 401–430 (2007).

[38] Guifré Vidal. ``Efficient classical simulation of slightly entangled quantum computations''. Physical review letters 91, 147902 (2003).

[39] Adnan Darwiche and Pierre Marquis. ``A knowledge compilation map''. Journal of Artificial Intelligence Research 17, 229–264 (2002).

[40] Karl S Brace, Richard L Rudell, and Randal E Bryant. ``Efficient implementation of a BDD package''. In Proceedings of the 27th ACM/​IEEE design automation conference. Pages 40–45. (1991).

[41] Donald Ervin Knuth. ``The art of computer programming. volume 4, fascicle 1''. Addison-Wesley. (2005).

[42] Fabio Somenzi. ``Efficient manipulation of decision diagrams''. International Journal on Software Tools for Technology Transfer 3, 171–181 (2001).

[43] Koenraad M R Audenaert and Martin B Plenio. ``Entanglement on mixed stabilizer states: normal forms and reduction procedures''. New Journal of Physics 7, 170 (2005). url:.

[44] Marc Hein, Wolfgang Dür, Jens Eisert, Robert Raussendorf, M Nest, and H. J. Briegel. ``Entanglement in graph states and its applications''. In Proceedings of the International School of Physics "Enrico Fermi". Volume Volume 162: Quantum Computers, Algorithms and Chaos. IOS Press (2006).

[45] Scott Aaronson. ``Multilinear formulas and skepticism of quantum computing''. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing. Page 118–127. STOC '04New York, NY, USA (2004). Association for Computing Machinery.

[46] Sergey Bravyi and Alexei Kitaev. ``Universal quantum computation with ideal Clifford gates and noisy ancillas''. Phys. Rev. A 71, 022316 (2005).

[47] Charles H Bennett, Herbert J Bernstein, Sandu Popescu, and Benjamin Schumacher. ``Concentrating partial entanglement by local operations''. Physical Review A 53, 2046 (1996).

[48] David Y Feinstein and Mitchell A Thornton. ``On the skipped variables of quantum multiple-valued decision diagrams''. In 2011 41st IEEE International Symposium on Multiple-Valued Logic. Pages 164–169. IEEE (2011).

[49] Richard J Lipton, Donald J Rose, and Robert Endre Tarjan. ``Generalized nested dissection''. SIAM journal on numerical analysis 16, 346–358 (1979).

[50] M. Van den Nest, W. Dür, G. Vidal, and H. J. Briegel. ``Classical simulation versus universality in measurement-based quantum computation''. Phys. Rev. A 75, 012337 (2007).

[51] Vít Jelínek. ``The rank-width of the square grid''. Discrete Applied Mathematics 158, 841–850 (2010).

[52] Hélene Fargier, Pierre Marquis, Alexandre Niveau, and Nicolas Schmidt. ``A knowledge compilation map for ordered real-valued decision diagrams''. In Proceedings of the AAAI Conference on Artificial Intelligence. Volume 28. (2014).

[53] Robert W Floyd. ``Assigning meanings to programs''. In Program Verification. Pages 65–81. Springer (1993).

[54] JW De Bakker and Lambert G. L. T. Meertens. ``On the completeness of the inductive assertion method''. Journal of Computer and System Sciences 11, 323–357 (1975).

[55] Ingo Wegener. ``Branching programs and binary decision diagrams: theory and applications''. SIAM. (2000).

[56] James McClung. ``Constructions and applications of W-states''. PhD thesis. Worcester Polytechnic Institute. (2020).

[57] Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, and Bryan O'Gorman. ``The parameterized complexity of quantum verification'' (2022).

[58] Aleks Kissinger and John van de Wetering. ``Reducing T-count with the ZX-calculus'' (2019).

[59] Himanshu Thapliyal, Edgard Munoz-Coreas, TSS Varun, and Travis S Humble. ``Quantum circuit designs of integer division optimizing T-count and T-depth''. IEEE Transactions on Emerging Topics in Computing 9, 1045–1056 (2019).

[60] Wang Jian, Zhang Quan, and Tang Chao-Jing. ``Quantum secure communication scheme with W state''. Communications in Theoretical Physics 48, 637 (2007).

[61] Wen Liu, Yong-Bin Wang, and Zheng-Tao Jiang. ``An efficient protocol for the quantum private comparison of equality with W state''. Optics Communications 284, 3160–3163 (2011).

[62] Victoria Lipinska, Gláucia Murta, and Stephanie Wehner. ``Anonymous transmission in a noisy quantum network using the ${W}$ state''. Phys. Rev. A 98, 052320 (2018).

[63] Paul Tafertshofer and Massoud Pedram. ``Factored edge-valued binary decision diagrams''. Formal Methods in System Design 10, 243–270 (1997).

[64] Meghana Sistla, Swarat Chaudhuri, and Thomas Reps. ``CFLOBDDs: Context-free-language ordered binary decision diagrams'' (2023). arXiv:2211.06818.

[65] Meghana Sistla, Swarat Chaudhuri, and Thomas Reps. ``Symbolic quantum simulation with quasimodo''. In Constantin Enea and Akash Lal, editors, Computer Aided Verification. Pages 213–225. Cham (2023). Springer Nature Switzerland.

[66] Rajeev Alur and P. Madhusudan. ``Visibly pushdown languages''. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing. Pages 202–211. STOC '04New York, NY, USA (2004). Association for Computing Machinery.

[67] Meghana Sistla, Swarat Chaudhuri, and Thomas Reps. ``Weighted context-free-language ordered binary decision diagrams'' (2023). arXiv:2305.13610.

[68] Adnan Darwiche. ``SDD: a new canonical representation of propositional knowledge bases''. In Proceedings of the Twenty-Second international joint conference on Artificial Intelligence-Volume Volume Two. . AAAI Press (2011).

[69] Doga Kisa, Guy Van den Broeck, Arthur Choi, and Adnan Darwiche. ``Probabilistic sentential decision diagrams''. In Proceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning. Pages 558–567. KR'14. AAAI Press (2014). url:​ocs/​8005/​8005-36908-1-PB.pdf.

[70] Kengo Nakamura, Shuhei Denzumi, and Masaaki Nishino. ``Variable shift SDD: A more succinct sentential decision diagram''. In Simone Faro and Domenico Cantone, editors, 18th International Symposium on Experimental Algorithms (SEA 2020). Volume 160 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:13. Dagstuhl, Germany (2020). Schloss Dagstuhl–Leibniz-Zentrum für Informatik.

[71] Wolfgang Gunther and Rolf Drechsler. ``Minimization of bdds using linear transformations based on evolutionary techniques''. In 1999 IEEE International Symposium on Circuits and Systems (ISCAS). Volume 1, pages 387–390. IEEE (1999).

[72] Barbara M. Terhal and David P. DiVincenzo. ``Classical simulation of noninteracting-fermion quantum circuits''. Phys. Rev. A 65, 032325 (2002).

[73] Richard Jozsa and Akimasa Miyake. ``Matchgates and classical simulation of quantum circuits''. Proceedings: Mathematical, Physical and Engineering SciencesPages 3089–3106 (2008).

[74] Martin Hebenstreit, Richard Jozsa, Barbara Kraus, and Sergii Strelchuk. ``Computational power of matchgates with supplementary resources''. Physical Review A 102, 052604 (2020).

[75] Román Orús. ``A practical introduction to tensor networks: Matrix product states and projected entangled pair states''. Annals of Physics 349, 117–158 (2014).

[76] Bob Coecke and Ross Duncan. ``Interacting quantum observables: categorical algebra and diagrammatics''. New Journal of Physics 13, 043016 (2011).

[77] Renaud Vilmart. ``Quantum multiple-valued decision diagrams in graphical calculi'' (2021). arXiv:2107.01186.

[78] Richard Rudell. ``Dynamic variable ordering for ordered binary decision diagrams''. In Proceedings of 1993 International Conference on Computer Aided Design (ICCAD). Pages 42–47. IEEE (1993).

[79] Ewout van den Berg and Kristan Temme. ``Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters''. Quantum 4, 322 (2020).

[80] Eugene M Luks, Ferenc Rákóczi, and Charles RB Wright. ``Some algorithms for nilpotent permutation groups''. Journal of Symbolic Computation 23, 335–354 (1997).

[81] Pavol Ďuriš, Juraj Hromkovič, Stasys Jukna, Martin Sauerhoff, and Georg Schnitger. ``On multi-partition communication complexity''. Information and computation 194, 49–75 (2004).

[82] Hector J. Garcia, Igor L. Markov, and Andrew W. Cross. ``Efficient inner-product algorithm for stabilizer states'' (2012). arXiv:1210.6646.

[83] ``Stabranksearcher: code for finding (upper bounds to) the stabilizer rank of a quantum state''. https:/​/​​timcp/​StabRankSearcher (2021).

[84] Padraic Calpin. ``Exploring quantum computation through the lens of classical simulation''. PhD thesis. UCL (University College London). (2020).

Cited by

[1] Dimitrios Thanos, Tim Coopmans, and Alfons Laarman, Lecture Notes in Computer Science 14216, 199 (2023) ISBN:978-3-031-45331-1.

[2] Wang Fang and Mingsheng Ying, "Symbolic Execution for Quantum Error Correction Programs", Proceedings of the ACM on Programming Languages 8 PLDI, 1040 (2024).

[3] Nadish de Silva, Ming Yin, and Sergii Strelchuk, "Bases for optimising stabiliser decompositions of quantum states", arXiv:2311.17384, (2023).

[4] Dimitrios Thanos, Tim Coopmans, and Alfons Laarman, "Fast equivalence checking of quantum circuits of Clifford gates", arXiv:2308.01206, (2023).

[5] Wang Fang and Mingsheng Ying, "Symbolic Execution for Quantum Error Correction Programs", arXiv:2311.11313, (2023).

[6] Robert Wille, Stefan Hillmich, and Lukas Burgholzer, "Tools for Quantum Computing Based on Decision Diagrams", arXiv:2108.07027, (2021).

[7] Hoa T. Nguyen, Prabhakar Krishnan, Dilip Krishnaswamy, Muhammad Usman, and Rajkumar Buyya, "Quantum Cloud Computing: A Review, Open Problems, and Future Directions", arXiv:2404.11420, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2024-06-22 06:43:12) and SAO/NASA ADS (last updated successfully 2024-06-22 06:43:13). The list may be incomplete as not all publishers provide suitable and complete citation data.