Computational power of one- and two-dimensional dual-unitary quantum circuits

Ryotaro Suzuki1,2, Kosuke Mitarai1,3,4, and Keisuke Fujii1,3,5

1Graduate School of Engineering Science, Osaka University, 1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan
2Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, Berlin 14195, Germany
3Center for Quantum Information and Quantum Biology, Institute for Open and Transdisciplinary Research Initiatives, Osaka University, Osaka 560-8531, Japan
4JST, PRESTO, 4-1-8 Honcho, Kawaguchi, Saitama 332-0012, Japan
5Center for Emergent Matter Science, RIKEN, Wako Saitama 351-0198, Japan

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

Abstract

Quantum circuits that are classically simulatable tell us when quantum computation becomes less powerful than or equivalent to classical computation. Such classically simulatable circuits are of importance because they illustrate what makes universal quantum computation different from classical computers. In this work, we propose a novel family of classically simulatable circuits by making use of dual-unitary quantum circuits (DUQCs), which have been recently investigated as exactly solvable models of non-equilibrium physics, and we characterize their computational power. Specifically, we investigate the computational complexity of the problem of calculating local expectation values and the sampling problem of one-dimensional DUQCs, and we generalize them to two spatial dimensions. We reveal that a local expectation value of a DUQC is classically simulatable at an early time, which is linear in a system length. In contrast, in a late time, they can perform universal quantum computation, and the problem becomes a BQP-complete problem. Moreover, classical simulation of sampling from a DUQC turns out to be hard.

► BibTeX data

► References

[1] D Gottesman. Stabilizer codes and quantum error correction. PhD thesis, California Institute of Technology, 1997.

[2] Leslie G Valiant. Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing, 31(4):1229–1254, 2002. doi:10.1137/​S0097539700377025.
https:/​/​doi.org/​10.1137/​S0097539700377025

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

[4] Sergey Bravyi. Lagrangian representation for fermionic linear optics. Quantum information & computation, 5, 05 2004. doi:10.26421/​QIC5.3-3.
https:/​/​doi.org/​10.26421/​QIC5.3-3

[5] 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. doi:10.1098/​rspa.2008.0189.
https:/​/​doi.org/​10.1098/​rspa.2008.0189

[6] Easwar Magesan, Jay M Gambetta, and Joseph Emerson. Scalable and robust randomized benchmarking of quantum processes. Physical review letters, 106(18):180504, 2011. doi:10.1103/​PhysRevLett.106.180504.
https:/​/​doi.org/​10.1103/​PhysRevLett.106.180504

[7] Easwar Magesan, Jay M. Gambetta, and Joseph Emerson. Characterizing quantum gates via randomized benchmarking. Phys. Rev. A, 85:042311, Apr 2012. doi:10.1103/​PhysRevA.85.042311.
https:/​/​doi.org/​10.1103/​PhysRevA.85.042311

[8] Jonas Helsen, Sepehr Nezami, Matthew Reagor, and Michael Walter. Matchgate benchmarking: Scalable benchmarking of a continuous family of many-qubit gates, 2020. arXiv:2011.13048.
arXiv:2011.13048

[9] Mark Howard and Earl Campbell. Application of a resource theory for magic states to fault-tolerant quantum computing. Physical review letters, 118(9):090501, 2017. doi:10.1103/​PhysRevLett.118.090501.
https:/​/​doi.org/​10.1103/​PhysRevLett.118.090501

[10] Yasunari Suzuki, Keisuke Fujii, and Masato Koashi. Efficient simulation of quantum error correction under coherent error based on the nonunitary free-fermionic formalism. Physical review letters, 119(19):190503, 2017. doi:10.1103/​PhysRevLett.119.190503.
https:/​/​doi.org/​10.1103/​PhysRevLett.119.190503

[11] Anatoli Polkovnikov, Krishnendu Sengupta, Alessandro Silva, and Mukund Vengalattore. Colloquium: Nonequilibrium dynamics of closed interacting quantum systems. Rev. Mod. Phys., 83:863–883, Aug 2011. doi:10.1103/​RevModPhys.83.863.
https:/​/​doi.org/​10.1103/​RevModPhys.83.863

[12] Jens Eisert, Mathis Friesdorf, and Christian Gogolin. Quantum many-body systems out of equilibrium. Nature Physics, 11(2):124–130, 2015. doi:10.1038/​nphys3215.
https:/​/​doi.org/​10.1038/​nphys3215

[13] Luca D'Alessio, Yariv Kafri, Anatoli Polkovnikov, and Marcos Rigol. From quantum chaos and eigenstate thermalization to statistical mechanics and thermodynamics. Advances in Physics, 65(3):239–362, 2016. doi:10.1080/​00018732.2016.1198134.
https:/​/​doi.org/​10.1080/​00018732.2016.1198134

[14] Anushya Chandran and CR Laumann. Semiclassical limit for the many-body localization transition. Physical Review B, 92(2):024301, 2015. doi:10.1103/​PhysRevB.92.024301.
https:/​/​doi.org/​10.1103/​PhysRevB.92.024301

[15] Sarang Gopalakrishnan and Bahti Zakirov. Facilitated quantum cellular automata as simple models with non-thermal eigenstates and dynamics. Quantum Science and Technology, 3(4):044004, 2018. doi:10.1088/​2058-9565/​aad759.
https:/​/​doi.org/​10.1088/​2058-9565/​aad759

[16] David Berenstein and Jiayao Zhao. Exotic equilibration dynamics on a 1-d quantum cnot gate lattice, 2021. arXiv:2102.05745.
arXiv:2102.05745

[17] Adam Nahum, Jonathan Ruhman, Sagar Vijay, and Jeongwan Haah. Quantum entanglement growth under random unitary dynamics. Physical Review X, 7(3):031016, 2017. doi:10.1103/​PhysRevX.7.031016.
https:/​/​doi.org/​10.1103/​PhysRevX.7.031016

[18] Adam Nahum, Sagar Vijay, and Jeongwan Haah. Operator spreading in random unitary circuits. Physical Review X, 8(2):021014, 2018. doi:10.1103/​PhysRevX.8.021014.
https:/​/​doi.org/​10.1103/​PhysRevX.8.021014

[19] CW Von Keyserlingk, Tibor Rakovszky, Frank Pollmann, and Shivaji Lal Sondhi. Operator hydrodynamics, otocs, and entanglement growth in systems without conservation laws. Physical Review X, 8(2):021013, 2018. doi:10.1103/​PhysRevX.8.021013.
https:/​/​doi.org/​10.1103/​PhysRevX.8.021013

[20] Fabian HL Essler and Maurizio Fagotti. Quench dynamics and relaxation in isolated integrable quantum spin chains. Journal of Statistical Mechanics: Theory and Experiment, 2016(6):064002, 2016. doi:10.1088/​1742-5468/​2016/​06/​064002.
https:/​/​doi.org/​10.1088/​1742-5468/​2016/​06/​064002

[21] Sarang Gopalakrishnan and Austen Lamacraft. Unitary circuits of finite depth and infinite width from quantum channels. Physical Review B, 100(6):064309, 2019. doi:10.1103/​PhysRevB.100.064309.
https:/​/​doi.org/​10.1103/​PhysRevB.100.064309

[22] Bruno Bertini, Pavel Kos, and TomažProsen. Exact correlation functions for dual-unitary lattice models in $1+1$ dimensions. Phys. Rev. Lett., 123:210601, Nov 2019. doi:10.1103/​PhysRevLett.123.210601.
https:/​/​doi.org/​10.1103/​PhysRevLett.123.210601

[23] Bruno Bertini, Pavel Kos, and Tomaz Prosen. Operator Entanglement in Local Quantum Circuits I: Chaotic Dual-Unitary Circuits. SciPost Phys., 8:67, 2020. doi:10.21468/​SciPostPhys.8.4.067.
https:/​/​doi.org/​10.21468/​SciPostPhys.8.4.067

[24] Lorenzo Piroli, Bruno Bertini, J. Ignacio Cirac, and TomažProsen. Exact dynamics in dual-unitary quantum circuits. Phys. Rev. B, 101:094304, Mar 2020. doi:10.1103/​PhysRevB.101.094304.
https:/​/​doi.org/​10.1103/​PhysRevB.101.094304

[25] Michael J Bremner, Christopher M Dawson, Jennifer L Dodd, Alexei Gilchrist, Aram W Harrow, Duncan Mortimer, Michael A Nielsen, and Tobias J Osborne. Practical scheme for quantum computation with any two-qubit entangling gate. Physical review letters, 89(24):247902, 2002. doi:10.1103/​PhysRevLett.89.247902.
https:/​/​doi.org/​10.1103/​PhysRevLett.89.247902

[26] Michael J Bremner, Richard Jozsa, and Dan J Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467(2126):459–472, 2011. doi:10.1098/​rspa.2010.0301.
https:/​/​doi.org/​10.1098/​rspa.2010.0301

[27] Tianci Zhou and Adam Nahum. Entanglement membrane in chaotic many-body systems. Phys. Rev. X, 10:031066, Sep 2020. doi:10.1103/​PhysRevX.10.031066.
https:/​/​doi.org/​10.1103/​PhysRevX.10.031066

[28] Boris Gutkin, Petr Braun, Maram Akila, Daniel Waltner, and Thomas Guhr. Exact local correlations in kicked chains. Phys. Rev. B, 102:174307, Nov 2020. doi:10.1103/​PhysRevB.102.174307.
https:/​/​doi.org/​10.1103/​PhysRevB.102.174307

[29] Pieter W. Claeys and Austen Lamacraft. Maximum velocity quantum circuits. Phys. Rev. Research, 2:033032, Jul 2020. doi:10.1103/​PhysRevResearch.2.033032.
https:/​/​doi.org/​10.1103/​PhysRevResearch.2.033032

[30] Bruno Bertini and Lorenzo Piroli. Scrambling in random unitary circuits: Exact results. Phys. Rev. B, 102:064305, Aug 2020. doi:10.1103/​PhysRevB.102.064305.
https:/​/​doi.org/​10.1103/​PhysRevB.102.064305

[31] Pavel Kos, Bruno Bertini, and TomažProsen. Correlations in perturbed dual-unitary circuits: Efficient path-integral formula. Phys. Rev. X, 11:011022, Feb 2021. doi:10.1103/​PhysRevX.11.011022.
https:/​/​doi.org/​10.1103/​PhysRevX.11.011022

[32] Pieter W. Claeys and Austen Lamacraft. Ergodic and nonergodic dual-unitary quantum circuits with arbitrary local hilbert space dimension. Phys. Rev. Lett., 126:100603, Mar 2021. doi:10.1103/​PhysRevLett.126.100603.
https:/​/​doi.org/​10.1103/​PhysRevLett.126.100603

[33] Bruno Bertini, Pavel Kos, and Tomaz Prosen. Random matrix spectral form factor of dual-unitary quantum circuits. Communications in Mathematical Physics, 387:597–620, Jul 2021. doi:10.1007/​s00220-021-04139-2.
https:/​/​doi.org/​10.1007/​s00220-021-04139-2

[34] Suhail Ahmad Rather, S. Aravinda, and Arul Lakshminarayan. Creating ensembles of dual unitary and maximally entangling quantum evolutions. Phys. Rev. Lett., 125:070501, Aug 2020. doi:10.1103/​PhysRevLett.125.070501.
https:/​/​doi.org/​10.1103/​PhysRevLett.125.070501

[35] S. Aravinda, Suhail Ahmad Rather, and Arul Lakshminarayan. From dual-unitary to quantum bernoulli circuits: Role of the entangling power in constructing a quantum ergodic hierarchy. Phys. Rev. Research, 3:043034, Oct 2021. doi:10.1103/​PhysRevResearch.3.043034.
https:/​/​doi.org/​10.1103/​PhysRevResearch.3.043034

[36] Felix Fritzsch and TomažProsen. Eigenstate thermalization in dual-unitary quantum circuits: Asymptotics of spectral functions. Phys. Rev. E, 103:062133, Jun 2021. URL: https:/​/​link.aps.org/​doi/​10.1103/​PhysRevE.103.062133, doi:10.1103/​PhysRevE.103.062133.
https:/​/​doi.org/​10.1103/​PhysRevE.103.062133

[37] Isaac Reid and Bruno Bertini. Entanglement barriers in dual-unitary circuits. Phys. Rev. B, 104:014301, Jul 2021. doi:10.1103/​PhysRevB.104.014301.
https:/​/​doi.org/​10.1103/​PhysRevB.104.014301

[38] Ryusuke Hamazaki. Exceptional dynamical quantum phase transitions in periodically driven systems. Nature communications, 12(1):1–7, 2021. doi:10.1038/​s41467-021-25355-3.
https:/​/​doi.org/​10.1038/​s41467-021-25355-3

[39] D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac. Matrix product state representations. Quantum Info. Comput., 7(5):401–430, jul 2007. URL: https:/​/​dl.acm.org/​doi/​10.5555/​2011832.2011833.
https:/​/​dl.acm.org/​doi/​10.5555/​2011832.2011833

[40] Bruno Bertini, Pavel Kos, and Tomaž Prosen. Entanglement spreading in a minimal model of maximal many-body quantum chaos. Physical Review X, 9(2):021033, 2019. doi:10.1103/​PhysRevX.9.021033.
https:/​/​doi.org/​10.1103/​PhysRevX.9.021033

[41] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Phys. Rev. A, 52:3457–3467, Nov 1995. doi:10.1103/​PhysRevA.52.3457.
https:/​/​doi.org/​10.1103/​PhysRevA.52.3457

[42] Robert Raussendorf and Hans J. Briegel. A one-way quantum computer. Phys. Rev. Lett., 86:5188–5191, May 2001. doi:10.1103/​PhysRevLett.86.5188.
https:/​/​doi.org/​10.1103/​PhysRevLett.86.5188

[43] Takashi Mori, Tatsuhiko N Ikeda, Eriko Kaminishi, and Masahito Ueda. Thermalization and prethermalization in isolated quantum systems: a theoretical overview. Journal of Physics B: Atomic, Molecular and Optical Physics, 51(11):112001, 2018. doi:10.1088/​1361-6455/​aabcdf.
https:/​/​doi.org/​10.1088/​1361-6455/​aabcdf

[44] Abhinav Deshpande, Bill Fefferman, Minh C Tran, Michael Foss-Feig, and Alexey V Gorshkov. Dynamical phase transitions in sampling complexity. Physical review letters, 121(3):030501, 2018. doi:10.1103/​PhysRevLett.121.030501.
https:/​/​doi.org/​10.1103/​PhysRevLett.121.030501

[45] Nishad Maskara, Abhinav Deshpande, Adam Ehrenberg, Minh C. Tran, Bill Fefferman, and Alexey V. Gorshkov. Complexity phase diagram for interacting and long-range bosonic hamiltonians, 2020. arXiv:1906.04178.
arXiv:1906.04178

[46] John Napp, Rolando L. La Placa, Alexander M. Dalzell, Fernando G. S. L. Brandao, and Aram W. Harrow. Efficient classical simulation of random shallow 2d quantum circuits, 2020. arXiv:2001.00021.
arXiv:2001.00021

[47] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal clifford gates and noisy ancillas. Physical Review A, 71(2):022316, 2005. doi:10.1103/​PhysRevA.71.022316.
https:/​/​doi.org/​10.1103/​PhysRevA.71.022316

[48] 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(8):080503, 2019. doi:10.1103/​PhysRevLett.123.080503.
https:/​/​doi.org/​10.1103/​PhysRevLett.123.080503

[49] Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11, page 333–342, New York, NY, USA, 2011. Association for Computing Machinery. doi:10.1145/​1993636.1993682.
https:/​/​doi.org/​10.1145/​1993636.1993682

[50] Michael J Bremner, Ashley Montanaro, and Dan J Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Physical review letters, 117(8):080501, 2016. doi:10.1103/​PhysRevLett.117.080501.
https:/​/​doi.org/​10.1103/​PhysRevLett.117.080501

[51] Tomoyuki Morimae. Hardness of classically sampling the one-clean-qubit model with constant total variation distance error. Physical Review A, 96(4):040302, 2017. doi:10.1103/​PhysRevA.96.040302.
https:/​/​doi.org/​10.1103/​PhysRevA.96.040302

[52] 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. doi:10.1038/​s41567-018-0318-2.
https:/​/​doi.org/​10.1038/​s41567-018-0318-2

[53] 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. doi:10.1038/​s41586-019-1666-5.
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[54] J. Ignacio Cirac, David Pérez-García, Norbert Schuch, and Frank Verstraete. Matrix product states and projected entangled pair states: Concepts, symmetries, theorems. Rev. Mod. Phys., 93:045003, Dec 2021. doi:10.1103/​RevModPhys.93.045003.
https:/​/​doi.org/​10.1103/​RevModPhys.93.045003

[55] Gene H Golub and Charles F Van Loan. Matrix computations, volume 3. JHU press, 2013.

[56] Daniel J Brod and Ernesto F Galvão. Geometries for universal quantum computation with matchgates. Physical Review A, 86(5):052307, 2012. doi:10.1103/​PhysRevA.86.052307.
https:/​/​doi.org/​10.1103/​PhysRevA.86.052307

Cited by

[1] Bruno Bertini, Pavel Kos, and Tomaž Prosen, "Exact spectral statistics in strongly localized circuits", arXiv:2110.15938, Physical Review B 105 16, 165142 (2022).

[2] Giacomo Giudice, Giuliano Giudici, Michael Sonner, Julian Thoenniss, Alessio Lerose, Dmitry A. Abanin, and Lorenzo Piroli, "Temporal entanglement, quasiparticles and the role of interactions", arXiv:2112.14264.

[3] Cheryne Jonay, Vedika Khemani, and Matteo Ippoliti, "Triunitary quantum circuits", Physical Review Research 3 4, 043046 (2021).

[4] Isaac Reid and Bruno Bertini, "Entanglement barriers in dual-unitary circuits", Physical Review B 104 1, 014301 (2021).

[5] Katja Klobas and Bruno Bertini, "Entanglement dynamics in Rule 54: Exact results and quasiparticle picture", SciPost Physics 11 6, 107 (2021).

[6] S. Aravinda, Suhail Ahmad Rather, and Arul Lakshminarayan, "From dual-unitary to quantum Bernoulli circuits: Role of the entangling power in constructing a quantum ergodic hierarchy", Physical Review Research 3 4, 043034 (2021).

[7] Katja Klobas and Bruno Bertini, "Exact relaxation to Gibbs and non-equilibrium steady states in the quantum cellular automaton Rule 54", SciPost Physics 11 6, 106 (2021).

[8] Márton Borsi and Balázs Pozsgay, "Remarks on the construction and the ergodicity properties of dual unitary quantum circuits (with an Appendix by Roland Bacher and Denis Serre)", arXiv:2201.07768.

[9] Pavel Kos, Tomaž Prosen, and Bruno Bertini, "Thermalization dynamics and spectral statistics of extended systems with thermalizing boundaries", Physical Review B 104 21, 214303 (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2022-05-20 13:39:49) and SAO/NASA ADS (last updated successfully 2022-05-20 13:39:50). The list may be incomplete as not all publishers provide suitable and complete citation data.