3 citations · 7 across the 6 of their papers we have counts for
11 papers
Exponential quantum speedup for -Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
Robin Kothari, Tony Metger, Ryan O'Donnell +2
We study vector subset sum over : given random vectors from , find a nonempty subset that sums to zero; the smaller , the more difficult it i…
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…
Holographic pseudoentanglement and the complexity of the AdS/CFT dictionary
Chris Akers, Adam Bouland, Lijie Chen +3
The `quantum gravity in the lab' paradigm suggests that quantum computers might shed light on quantum gravity by simulating the CFT side of the AdS/CFT correspondence and mapping t…
Single-Round Proofs of Quantumness from Knowledge Assumptions
Petia Arabadjieva, Alexandru Gheorghiu, Victor Gitton +1
A proof of quantumness is an efficiently verifiable interactive test that an efficient quantum computer can pass, but all efficient classical computers cannot (under some cryptogra…
Succinct arguments for QMA from standard assumptions via compiled nonlocal games
Tony Metger, Anand Natarajan, Tina Zhang
We construct a succinct classical argument system for QMA, the quantum analogue of NP, from generic and standard cryptographic assumptions. Previously, building on the prior work o…
Simple constructions of linear-depth t-designs and pseudorandom unitaries
Tony Metger, Alexander Poremba, Makrand Sinha +1
Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. This has motivated a long line of resear…
Pseudorandom unitaries with non-adaptive security
Tony Metger, Alexander Poremba, Makrand Sinha +1
Pseudorandom unitaries (PRUs) are ensembles of efficiently implementable unitary operators that cannot be distinguished from Haar random unitaries by any quantum polynomial-time al…
Public-key pseudoentanglement and the hardness of learning ground state entanglement structure
Adam Bouland, Bill Fefferman, Soumik Ghosh +4
Given a local Hamiltonian, how difficult is it to determine the entanglement structure of its ground state? We show that this problem is computationally intractable even if one is…
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…
stateQIP = statePSPACE
Tony Metger, Henry Yuen
Complexity theory traditionally studies the hardness of solving classical computational problems. In the quantum setting, it is also natural to consider a different notion of compl…
Quantum cryptography with classical communication: parallel remote state preparation for copy-protection, verification, and more
Alexandru Gheorghiu, Tony Metger, Alexander Poremba
Quantum mechanical effects have enabled the construction of cryptographic primitives that are impossible classically. For example, quantum copy-protection allows for a program to b…