TY - JOUR
T1 - Hay from the Haystack
T2 - Explicit Examples of Exponential Quantum Circuit Complexity
AU - Jia, Yifan
AU - Wolf, Michael M.
N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.
PY - 2023/8
Y1 - 2023/8
N2 - The vast majority of quantum states and unitaries have circuit complexity exponential in the number of qubits. In a similar vein, most of them also have exponential minimum description length, which makes it difficult to pinpoint examples of exponential complexity. In this work, we construct examples of constant description length but exponential circuit complexity. We provide infinite families such that each element requires an exponential number of two-qubit gates to be generated exactly from a product and where the same is true for the approximate generation of the vast majority of elements in the family. The results are based on sets of large transcendence degree and discussed for tensor networks, diagonal unitaries and maximally coherent states.
AB - The vast majority of quantum states and unitaries have circuit complexity exponential in the number of qubits. In a similar vein, most of them also have exponential minimum description length, which makes it difficult to pinpoint examples of exponential complexity. In this work, we construct examples of constant description length but exponential circuit complexity. We provide infinite families such that each element requires an exponential number of two-qubit gates to be generated exactly from a product and where the same is true for the approximate generation of the vast majority of elements in the family. The results are based on sets of large transcendence degree and discussed for tensor networks, diagonal unitaries and maximally coherent states.
UR - http://www.scopus.com/inward/record.url?scp=85158116474&partnerID=8YFLogxK
U2 - 10.1007/s00220-023-04720-x
DO - 10.1007/s00220-023-04720-x
M3 - Article
AN - SCOPUS:85158116474
SN - 0010-3616
VL - 402
SP - 141
EP - 156
JO - Communications in Mathematical Physics
JF - Communications in Mathematical Physics
IS - 1
ER -