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

Ryotaro Suzuki; Kosuke Mitarai; Keisuke Fujii

doi:10.22331/q-2022-01-24-631

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

Ryotaro Suzuki^1,2, Kosuke Mitarai^1,3,4, and Keisuke Fujii^1,3,5

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

Published:	2022-01-24, volume 6, page 631
Eprint:	arXiv:2103.09211v2
Doi:	https://doi.org/10.22331/q-2022-01-24-631
Citation:	Quantum 6, 631 (2022).

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

@article{Suzuki2022computationalpower,
  doi = {10.22331/q-2022-01-24-631},
  url = {https://doi.org/10.22331/q-2022-01-24-631},
  title = {Computational power of one- and two-dimensional dual-unitary quantum circuits},
  author = {Suzuki, Ryotaro and Mitarai, Kosuke and Fujii, Keisuke},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {631},
  month = jan,
  year = {2022}
}

► 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", Physical Review B 105 16, 165142 (2022).

[2] S S Gayathri, R. Kumar, and Samiappan Dhanalakshmi, "Efficient Floating-point Division Quantum Circuit using Newton-Raphson Division", Journal of Physics: Conference Series 2335 1, 012058 (2022).

[3] Adam Nahum, Sthitadhi Roy, Sagar Vijay, and Tianci Zhou, "Real-time correlators in chaotic quantum many-body systems", Physical Review B 106 22, 224310 (2022).

[4] Alessandro Foligno, Tianci Zhou, and Bruno Bertini, "Temporal Entanglement in Chaotic Quantum Circuits", Physical Review X 13 4, 041008 (2023).

[5] Giacomo Giudice, Giuliano Giudici, Michael Sonner, Julian Thoenniss, Alessio Lerose, Dmitry A. Abanin, and Lorenzo Piroli, "Temporal Entanglement, Quasiparticles, and the Role of Interactions", Physical Review Letters 128 22, 220401 (2022).

[6] Michael A. Rampp, Roderich Moessner, and Pieter W. Claeys, "From Dual Unitarity to Generic Quantum Operator Spreading", Physical Review Letters 130 13, 130402 (2023).

[7] Pieter W. Claeys and Austen Lamacraft, "Emergent quantum state designs and biunitarity in dual-unitary circuit dynamics", Quantum 6, 738 (2022).

[8] Pavel Kos and Georgios Styliaris, "Circuits of space and time quantum channels", Quantum 7, 1020 (2023).

[9] Alessandro Foligno and Bruno Bertini, "Growth of entanglement of generic states under dual-unitary dynamics", Physical Review B 107 17, 174311 (2023).

[10] Pieter W. Claeys, Marius Henry, Jamie Vicary, and Austen Lamacraft, "Exact dynamics in dual-unitary quantum circuits with projective measurements", Physical Review Research 4 4, 043212 (2022).

[11] Márton Borsi and Balázs Pozsgay, "Construction and the ergodicity properties of dual unitary quantum circuits", Physical Review B 106 1, 014302 (2022).

[12] Richard M. Milbradt, Lisa Scheller, Christopher Aßmus, and Christian B. Mendl, "Ternary Unitary Quantum Lattice Models and Circuits in 2+1 Dimensions", Physical Review Letters 130 9, 090601 (2023).

[13] 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).

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

[15] 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).

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

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

[18] 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).

[19] Bruno Bertini, Pavel Kos, and Tomaz Prosen, "Exact Spectral Statistics in Strongly Localised Circuits", arXiv:2110.15938, (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2023-12-07 07:05:36) and SAO/NASA ADS (last updated successfully 2023-12-07 07:05:37). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.