Classical simulation of non-Gaussian fermionic circuits

Beatriz Dias and Robert Koenig

Department of Mathematics, School of Computation, Information and Technology, Technical University of Munich, Garching, Germany
Munich Center for Quantum Science and Technology, Munich, Germany

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


We propose efficient algorithms for classically simulating fermionic linear optics operations applied to non-Gaussian initial states. By gadget constructions, this provides algorithms for fermionic linear optics with non-Gaussian operations. We argue that this problem is analogous to that of simulating Clifford circuits with non-stabilizer initial states: Algorithms for the latter problem immediately translate to the fermionic setting. Our construction is based on an extension of the covariance matrix formalism which permits to efficiently track relative phases in superpositions of Gaussian states. It yields simulation algorithms with polynomial complexity in the number of fermions, the desired accuracy, and certain quantities capturing the degree of non-Gaussianity of the initial state. We study one such quantity, the fermionic Gaussian extent, and show that it is multiplicative on tensor products when the so-called fermionic Gaussian fidelity is. We establish this property for the tensor product of two arbitrary pure states of four fermions with positive parity.


QIP24 talk: Classical simulation of non Gaussian fermionic circuits by Beatriz Cardoso Dias

and Quanta magazine feature.

► BibTeX data

► References

[1] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43(9):4452–4505, 2002. https:/​/​​10.1063/​1.1499754.

[2] Ruben S. Andrist, H. Bombin, Helmut G. Katzgraber, and M. A. Martin-Delgado. Optimal error correction in topological subsystem codes. Physical Review A, 85:050302, 2012. https:/​/​​10.1103/​PhysRevA.85.050302.

[3] Sergey Bravyi and Robert König. Disorder-assisted error correction in Majorana chains. Communications in Mathematical Physics, 316(3):641–692, 2012. https:/​/​​10.1007/​s00220-012-1606-9.

[4] Andrew S. Darmawan and David Poulin. Tensor-network simulations of the surface code under realistic noise. Physical Review Letters, 119:040502, 2017. https:/​/​​10.1103/​PhysRevLett.119.040502.

[5] Sergey Bravyi, Matthias Englbrecht, Robert König, and Nolan Peard. Correcting coherent errors with surface codes. npj Quantum Information, 4(1):1–6, 2018. https:/​/​​10.1038/​s41534-018-0106-y.

[6] David K. Tuckett, Andrew S. Darmawan, Christopher T. Chubb, Sergey Bravyi, Stephen D. Bartlett, and Steven T. Flammia. Tailoring surface codes for highly biased noise. Physical Review X, 9:041031, 2019. https:/​/​​10.1103/​PhysRevX.9.041031.

[7] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5):052328, 2004. https:/​/​​10.1103/​PhysRevA.70.052328.

[8] Leslie G. Valiant. Quantum computers that can be simulated classically in polynomial time. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC '01, page 114–123, New York, USA, 2001. https:/​/​​10.1145/​380752.380785.

[9] Barbara M. Terhal and David P. DiVincenzo. Classical simulation of noninteracting-fermion quantum circuits. Physical Review A, 65:032325, 2002. https:/​/​​10.1103/​PhysRevA.65.032325.

[10] Emanuel Knill. Fermionic linear optics and matchgates. Technical Report LAUR-01-4472, Los Alamos National Laboratory, 2001.

[11] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A, 71:022316, 2005. https:/​/​​10.1103/​PhysRevA.71.022316.

[12] Sergey Bravyi. Universal quantum computation with the $\nu=5/​2$ fractional quantum Hall state. Physical Review A, 73:042313, 2006. https:/​/​​10.1103/​PhysRevA.73.042313.

[13] Martin Hebenstreit, Richard Jozsa, Barbara Kraus, Sergii Strelchuk, and Mithuna Yoganathan. All pure fermionic non-Gaussian states are magic states for matchgate computations. Physical Review Letters, 123:080503, 2019. https:/​/​​10.1103/​PhysRevLett.123.080503.

[14] Mark Howard and Earl Campbell. Application of a resource theory for magic states to fault-tolerant quantum computing. Physical Review Letters, 118:090501, 2017. https:/​/​​10.1103/​PhysRevLett.118.090501.

[15] Markus Heinrich and David Gross. Robustness of magic and symmetries of the stabiliser polytope. Quantum, 3:132, 2019. https:/​/​​10.22331/​q-2019-04-08-132.

[16] Sergey Bravyi, Graeme Smith, and John A. Smolin. Trading classical and quantum computational resources. Physical Review X, 6(2):021043, 2016. https:/​/​​10.1103/​PhysRevX.6.021043.

[17] Sergey Bravyi and David Gosset. Improved classical simulation of quantum circuits dominated by Clifford gates. Physical Review Letters, 116(25), 2016. https:/​/​​10.1103/​PhysRevLett.116.250501.

[18] 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. https:/​/​​10.22331/​q-2019-09-02-181.

[19] Arne Heimendahl, Felipe Montealegre-Mora, Frank Vallentin, and David Gross. Stabilizer extent is not multiplicative. Quantum, 5:400, 2021. https:/​/​​10.22331/​q-2021-02-24-400.

[20] Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov. Lower bounds on the non-Clifford resources for quantum computations. Quantum Science and Technology, 5(3):035009, 2020. https:/​/​​10.1088/​2058-9565/​ab8963.

[21] James R. Seddon, Bartosz Regula, Hakop Pashayan, Yingkai Ouyang, and Earl T. Campbell. Quantifying quantum speedups: Improved classical simulation from tighter magic monotones. PRX Quantum, 2:010345, 2021. https:/​/​​10.1103/​PRXQuantum.2.010345.

[22] Kaifeng Bu, Weichen Gu, and Arthur Jaffe. Stabilizer testing and magic entropy. arXiv:2306.09292, 2023.

[23] Joel A. Tropp. Greed is good: algorithmic results for sparse approximation. IEEE Transactions on Information Theory, 50(10):2231–2242, 2004. https:/​/​​10.1109/​TIT.2004.834793.

[24] Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders. Atomic decomposition by basis pursuit. SIAM Review, 43(1):129–159, 2001. https:/​/​​10.1137/​S003614450037906X.

[25] Jean-Jacques Fuchs. On sparse representations in arbitrary redundant bases. IEEE Transactions on Information Theory, 50(6):1341–1344, 2004. https:/​/​​10.1109/​TIT.2004.828141.

[26] Joel A. Tropp. Recovery of short, complex linear combinations via /​spl lscr/​/​sub 1/​ minimization. IEEE Transactions on Information Theory, 51(4):1568–1570, 2005. https:/​/​​10.1109/​TIT.2005.844057.

[27] Hakop Pashayan, Oliver Reardon-Smith, Kamil Korzekwa, and Stephen D. Bartlett. Fast estimation of outcome probabilities for quantum circuits. PRX Quantum, 3:020361, 2022. https:/​/​​10.1103/​PRXQuantum.3.020361.

[28] Farid Alizadeh and Donald Goldfarb. Second-order cone programming. Mathematical Programming, 95(1):3–51, 2003. https:/​/​​10.1007/​s10107-002-0339-5.

[29] Stephen P. Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. https:/​/​​10.1017/​CBO9780511804441.

[30] Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, and Alan S. Willsky. The Convex Geometry of Linear Inverse Problems. Foundations of Computational Mathematics, 12(6):805–849, 2012. https:/​/​​10.1007/​s10208-012-9135-7.

[31] Christophe Piveteau and David Sutter. Circuit knitting with classical communication. IEEE Transactions on Information Theory, 70(4):2734–2745, 2024. https:/​/​​10.1109/​TIT.2023.3310797.

[32] Fernando de Melo, Piotr Ć wikliński, and Barbara M. Terhal. The power of noisy fermionic quantum computation. New Journal of Physics, 15(1):013015, 2013. https:/​/​​10.1088/​1367-2630/​15/​1/​013015.

[33] Richard Jozsa and Akimasa Miyake. Matchgates and classical simulation of quantum circuits. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 464(2100):3089–3106, 2008. https:/​/​​10.1098/​rspa.2008.0189.

[34] Stephen D. Bartlett and Barry C. Sanders. Efficient classical simulation of optical quantum information circuits. Physical Review Letters, 89:207903, 2002. https:/​/​​10.1103/​PhysRevLett.89.207903.

[35] Stephen D. Bartlett, Barry C. Sanders, Samuel L. Braunstein, and Kae Nemoto. Efficient classical simulation of continuous variable quantum information processes. Physical Review Letters, 88:097904, 2002. https:/​/​​10.1103/​PhysRevLett.88.097904.

[36] Rolando Somma, Howard Barnum, Gerardo Ortiz, and Emanuel Knill. Efficient solvability of Hamiltonians and limits on the power of some quantum computational models. Physical Review Letters, 97:190501, 2006. https:/​/​​10.1103/​PhysRevLett.97.190501.

[37] Daniel Gottesman. Stabilizer Codes and Quantum Error Correction. PhD thesis, California Institute of Technology, 1997. https:/​/​​10.7907/​rzr7-dt72.

[38] Victor Veitch, Christopher Ferrie, David Gross, and Joseph Emerson. Negative quasi-probability as a resource for quantum computation. New Journal of Physics, 14(11):113011, 2012. https:/​/​​10.1088/​1367-2630/​14/​11/​113011.

[39] Andrea Mari and Jens Eisert. Positive wigner functions render classical simulation of quantum computation efficient. Physical Review Letters, 109:230503, 2012. https:/​/​​10.1103/​PhysRevLett.109.230503.

[40] Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett. Estimating outcome probabilities of quantum circuits using quasiprobabilities. Physical Review Letters, 115:070501, 2015. https:/​/​​10.1103/​PhysRevLett.115.070501.

[41] Robert Raussendorf, Juani Bermejo-Vega, Emily Tyhurst, Cihan Okay, and Michael Zurel. Phase-space-simulation method for quantum computation with magic states on qubits. Physical Review A, 101:012350, 2020. https:/​/​​10.1103/​PhysRevA.101.012350.

[42] Robert Raussendorf, Dan E. Browne, Nicolas Delfosse, Cihan Okay, and Juan Bermejo-Vega. Contextuality and wigner-function negativity in qubit quantum computation. Physical Review A, 95:052334, 2017. https:/​/​​10.1103/​PhysRevA.95.052334.

[43] Juan Bermejo-Vega, Nicolas Delfosse, Dan E. Browne, Cihan Okay, and Robert Raussendorf. Contextuality as a resource for models of quantum computation with qubits. Physical Review Letters, 119:120505, 2017. https:/​/​​10.1103/​PhysRevLett.119.120505.

[44] Markus Frembs, Sam Roberts, and Stephen D. Bartlett. Contextuality as a resource for measurement-based quantum computation beyond qubits. New Journal of Physics, 20(10):103011, 2018. https:/​/​​10.1088/​1367-2630/​aae3ad.

[45] Anna Vershynina. Complete criterion for convex-gaussian-state detection. Physical Review A, 90:062329, 2014. https:/​/​​10.1103/​PhysRevA.90.062329.

[46] Shigeo Hakkaku, Yuichiro Tashima, Kosuke Mitarai, Wataru Mizukami, and Keisuke Fujii. Quantifying fermionic nonlinearity of quantum circuits. Physical Review Research, 4:043100, 2022. https:/​/​​10.1103/​PhysRevResearch.4.043100.

[47] Avinash Mocherla, Lingling Lao, and Dan E. Browne. Extending matchgate simulation methods to universal quantum circuits. arxiv:2302.02654, 2023.

[48] Oliver Reardon-Smith, Michał Oszmaniec, and Kamil Korzekwa. Improved classical simulation of quantum circuits dominated by fermionic linear optical gates. arXiv:2307.12702, 2023.

[49] Joshua Cudby and Sergii Strelchuk. Gaussian decomposition of magic states for matchgate computations. arXiv:2307.12654, 2023.

[50] Alonso Botero and Benni Reznik. BCS-like modewise entanglement of fermion Gaussian states. Physics Letters A, 331(1):39–44, 2004. https:/​/​​10.1016/​j.physleta.2004.08.037.

[51] Grigori G. Amosov and Sergey N. Filippov. Spectral properties of reduced fermionic density operators and parity superselection rule. Quantum Information Processing, 16(1):2, 2016. https:/​/​​10.1007/​s11128-016-1467-9.

[52] Wallace Givens. Computation of plain unitary rotations transforming a general matrix to triangular form. Journal of the Society for Industrial and Applied Mathematics, 6(1):26–50, 1958. https:/​/​​10.1137/​0106004.

[53] Gene H. Golub and Charles F. Van Loan. Matrix Computations (3rd Ed.). Johns Hopkins University Press, USA, 1996. https:/​/​​10.56021/​9781421407944.

[54] Sergey Bravyi. Lagrangian representation for fermionic linear optics. Quantum Information & Computation, 5(3):216–238, 2005. https:/​/​​10.26421/​qic5.3-3.

[55] Woody Lichtenstein. A system of quadrics describing the orbit of the highest weight vector. Proceedings of the American Mathematical Society, 84(4):605–608, 1982. https:/​/​​10.1090/​s0002-9939-1982-0643758-8.

[56] Marek Kuś and Ingemar Bengtsson. ``Classical'' quantum states. Physical Review A, 80(2):022319, 2009. https:/​/​​10.1103/​PhysRevA.80.022319.

[57] Michał Oszmaniec and Marek Kuś. On detection of quasiclassical states. Journal of Physics A: Mathematical and Theoretical, 45(24):244034, 2012. https:/​/​​10.1088/​1751-8113/​45/​24/​244034.

[58] Michał Oszmaniec, Jan Gutt, and Marek Kuś. Classical simulation of fermionic linear optics augmented with noisy ancillas. Physical Review A, 90(2):020302, 2014. https:/​/​​10.1103/​PhysRevA.90.020302.

[59] Per-Olov Löwdin. Quantum theory of many-particle systems. i. physical interpretations by means of density matrices, natural spin-orbitals, and convergence problems in the method of configurational interaction. Physical Review, 97:1474–1489, 1955. https:/​/​​10.1103/​PhysRev.97.1474.

[60] Sergey Bravyi and David Gosset. Complexity of quantum impurity problems. Communications in Mathematical Physics, 356(2), 2017. https:/​/​​10.1007/​s00220-017-2976-9.

[61] Huzihiro Araki and Hajime Moriya. Joint extension of states of subsystems for a CAR system. Communications in Mathematical Physics, 237(1):105–122, 2003. https:/​/​​10.1007/​s00220-003-0832-6.

[62] Thomas P Hayes. A large-deviation inequality for vector-valued martingales, 2005. Unpublished manuscript. https:/​/​​$\sim$hayes/​papers/​VectorAzuma/​.

[63] Gongguo Tang, Badri Narayan Bhaskar, and Benjamin Recht. Sparse recovery over continuous dictionaries-just discretize. In 2013 Asilomar Conference on Signals, Systems and Computers, pages 1043–1047, 2013. https:/​/​​10.1109/​ACSSC.2013.6810450.

Cited by

[1] Charlie Wood, "Où se cache l’avantage quantique ?", Pour la Science N° 559 – mai 5, 44 (2024).

[2] M. Cerezo, Martin Larocca, Diego García-Martín, N. L. Diaz, Paolo Braccia, Enrico Fontana, Manuel S. Rudolph, Pablo Bermejo, Aroosa Ijaz, Supanut Thanasilp, Eric R. Anschuetz, and Zoë Holmes, "Does provable absence of barren plateaus imply classical simulability? Or, why we need to rethink variational quantum computing", arXiv:2312.09121, (2023).

[3] Hiroki Hamaguchi, Kou Hamada, and Nobuyuki Yoshioka, "Handbook for Efficiently Quantifying Robustness of Magic", arXiv:2311.01362, (2023).

[4] Oliver Hahn, Ryuji Takagi, Giulia Ferrini, and Hayata Yamasaki, "Classical simulation and quantum resource theory of non-Gaussian optics", arXiv:2404.07115, (2024).

[5] Joshua Cudby and Sergii Strelchuk, "Gaussian decomposition of magic states for matchgate computations", arXiv:2307.12654, (2023).

[6] Michael Zurel, Lawrence Z. Cohen, and Robert Raussendorf, "Simulation of quantum computation with magic states via Jordan-Wigner transformations", arXiv:2307.16034, (2023).

[7] Beatriz Dias and Robert Koenig, "Classical simulation of non-Gaussian bosonic circuits", arXiv:2403.19059, (2024).

[8] Mykola Semenyakin, Yevheniia Cheipesh, and Yaroslav Herasymenko, "Classifying fermionic states via many-body correlation measures", arXiv:2309.07956, (2023).

[9] Vsevolod I. Yashin and Maria A. Elovenkova, "Characterization of non-adaptive Clifford channels", arXiv:2311.06133, (2023).

[10] Elies Gil-Fuster, Casper Gyurik, Adrián Pérez-Salinas, and Vedran Dunjko, "On the relation between trainability and dequantization of variational quantum learning models", arXiv:2406.07072, (2024).

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