7 papers
Worst-case depth hierarchy for shallow quantum circuits
Min-Hsiu Hsieh, Michael de Oliveira, Sathyawageeswar Subramanian +1
Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth…
Unconditionally separating noisy from bounded polynomial threshold circuits of constant depth
Min-Hsiu Hsieh, Leandro Mendes, Michael de Oliveira +1
The rapid evolution of quantum devices fuels concerted efforts to experimentally establish quantum advantage over classical computing. Many demonstrations of quantum advantage, how…
Unconditional Pseudorandomness against Shallow Quantum Circuits
Soumik Ghosh, Sathyawageeswar Subramanian, Wei Zhan
Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known con…
Quantum Catalytic Space
Harry Buhrman, Marten Folkertsma, Ian Mertz +4
Space complexity is a key field of study in theoretical computer science. In the quantum setting there are clear motivations to understand the power of space-restricted computation…
Do black holes store negative entropy?
Koji Azuma, Sathyawageeswar Subramanian, Go Kato
The Bekenstein-Hawking equation states that black holes should have entropy proportional to their areas to make black hole physics compatible with the second law of thermodynamics.…
Quantum Channel Testing in Average-Case Distance
Gregory Rosenthal, Hugo Aaronson, Sathyawageeswar Subramanian +2
We study the complexity of testing properties of quantum channels. First, we show that testing identity to any channel $\mathcal N: \mathbb C^{d_{\mathrm{in}} \times d_{\mathrm{in}…