Models of Quantum Complexity Growth
The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high-energy physics. The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2021-07-01
|
| Series: | PRX Quantum |
| Online Access: | http://doi.org/10.1103/PRXQuantum.2.030316 |
| _version_ | 1819018353193254912 |
|---|---|
| author | Fernando G.S.L. Brandão Wissam Chemissany Nicholas Hunter-Jones Richard Kueng John Preskill |
| author_facet | Fernando G.S.L. Brandão Wissam Chemissany Nicholas Hunter-Jones Richard Kueng John Preskill |
| author_sort | Fernando G.S.L. Brandão |
| collection | DOAJ |
| description | The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high-energy physics. The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state. It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a shortcut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions. To go further, one may study more generic models of complexity growth. We provide a rigorous connection between complexity growth and unitary k-designs, ensembles that capture the randomness of the unitary group. This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity. We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind. Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements. |
| first_indexed | 2024-12-21T03:18:04Z |
| format | Article |
| id | doaj.art-2aa33215ff454cf1a8f50cac17c29374 |
| institution | Directory Open Access Journal |
| issn | 2691-3399 |
| language | English |
| last_indexed | 2024-12-21T03:18:04Z |
| publishDate | 2021-07-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | PRX Quantum |
| spelling | doaj.art-2aa33215ff454cf1a8f50cac17c293742022-12-21T19:17:47ZengAmerican Physical SocietyPRX Quantum2691-33992021-07-012303031610.1103/PRXQuantum.2.030316Models of Quantum Complexity GrowthFernando G.S.L. BrandãoWissam ChemissanyNicholas Hunter-JonesRichard KuengJohn PreskillThe concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high-energy physics. The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state. It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a shortcut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions. To go further, one may study more generic models of complexity growth. We provide a rigorous connection between complexity growth and unitary k-designs, ensembles that capture the randomness of the unitary group. This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity. We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind. Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.http://doi.org/10.1103/PRXQuantum.2.030316 |
| spellingShingle | Fernando G.S.L. Brandão Wissam Chemissany Nicholas Hunter-Jones Richard Kueng John Preskill Models of Quantum Complexity Growth PRX Quantum |
| title | Models of Quantum Complexity Growth |
| title_full | Models of Quantum Complexity Growth |
| title_fullStr | Models of Quantum Complexity Growth |
| title_full_unstemmed | Models of Quantum Complexity Growth |
| title_short | Models of Quantum Complexity Growth |
| title_sort | models of quantum complexity growth |
| url | http://doi.org/10.1103/PRXQuantum.2.030316 |
| work_keys_str_mv | AT fernandogslbrandao modelsofquantumcomplexitygrowth AT wissamchemissany modelsofquantumcomplexitygrowth AT nicholashunterjones modelsofquantumcomplexitygrowth AT richardkueng modelsofquantumcomplexitygrowth AT johnpreskill modelsofquantumcomplexitygrowth |