12 papers
Ideal random quantum circuits pass the LXEB test
Nicholas Hunter-Jones, Jonas Haferkamp
We show that noiseless random quantum circuits pass the linear cross-entropy benchmark (LXEB) test with high probability. If the circuits are linear depth, and thus form unitary 4-…
Separating QMA from QCMA with a classical oracle
John Bostanci, Jonas Haferkamp, Chinmay Nirkhe +1
We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly big…
Anti-concentration is (almost) all you need
Markus Heinrich, Jonas Haferkamp, Ingo Roth +1
Until very recently, it was generally believed that the (approximate) 2-design property is strictly stronger than anticoncentration of random quantum circuits, mainly because it wa…
Quantum complexity in gravity, quantum field theory, and quantum information science
Stefano Baiguera, Vijay Balasubramanian, Pawel Caputa +4
Quantum complexity quantifies the difficulty of preparing a state or implementing a unitary transformation with limited resources. Applications range from quantum computation to co…
On the average-case complexity of learning output distributions of quantum circuits
Alexander Nietner, Marios Ioannou, Ryan Sweke +4
In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely…
Will it glue? On short-depth designs beyond the unitary group
Lorenzo Grevink, Jonas Haferkamp, Markus Heinrich +4
We study the formation of short-depth designs beyond the unitary group. We provide a range of results on several groups of broad interest in quantum information science: the Cliffo…