6 papers
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…
A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire
John Bostanci, Barak Nehoran, Mark Zhandry
Aaronson, Atia, and Susskind (2020) established that efficiently mapping between quantum states and is computationally equivalent to distinguishing their…
Local transformations of bipartite entanglement are rigid
John Bostanci, Tony Metger, Henry Yuen
Uhlmann's theorem is a fundamental result in quantum information theory that quantifies the optimal overlap between two bipartite pure states after applying local unitary operation…
Unitary Complexity and the Uhlmann Transformation Problem
John Bostanci, Yuval Efron, Tony Metger +3
State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot…
Efficient Quantum Pseudorandomness from Hamiltonian Phase States
John Bostanci, Jonas Haferkamp, Dominik Hangleiter +1
Quantum pseudorandomness has found applications in many areas of quantum information, ranging from entanglement theory, to models of scrambling phenomena in chaotic quantum systems…
Oracle Separation Between Quantum Commitments and Quantum One-wayness
John Bostanci, Boyang Chen, Barak Nehoran
We show that there exists an oracle relative to which quantum commitments exist but no (efficiently verifiable) one-way state generators exist. Both have been widely considered can…