15 citations · 22 across the 6 of their papers we have counts for
8 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…
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…
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 su…
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…
An efficient quantum parallel repetition theorem and applications
John Bostanci, Luowen Qian, Nicholas Spooner +1
We prove a tight parallel repetition theorem for -message computationally-secure quantum interactive protocols between an efficient challenger and an efficient adversary. We als…
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…
Quantum game theory and the complexity of approximating quantum Nash equilibria
John Bostanci, John Watrous
This paper is concerned with complexity theoretic aspects of a general formulation of quantum game theory that models strategic interactions among rational agents that process and…