Author name cluster

Tony Metger

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

FOCS Conference 2025 Conference Paper

Incompressibility and Spectral Gaps of Random Circuits

Chi-Fang Chen
Jeongwan Haah
Jonas Haferkamp
Yunchao Liu 0002
Tony Metger
Xinyu Tan

Random reversible and quantum circuits form random walks on the alternating group Alt(2 n ) and unitary group SU(2 n ), respectively, with each random gate as one step of the walk. Existing bounds on the spectral gap for the t-th moment of these random walks have inverse-polynomial dependence in both n and t. We prove that the gap for random reversible circuits is Ω(n −3 ) for all t≥1, and the gap for random quantum circuits is Ω(n −3 ) for t ≤ Θ(2 n/2 ). Importantly, these gaps are independent of t in the respective regimes. We can further improve both gaps to n −1 /polylog(n, t) for t ≤ 2 Θ(n), which is tight up to polylog factors in n and t. Our spectral gap results have a number of consequences: 1)Random reversible circuits with $\mathcal{O}\left( {{n^4}t} \right)$ gates form multiplicative-error t-wise independent (even) permutations for all t ≥ 1; for t ≤ Θ(2 n/6. 1 ), we show that $\tilde {\mathcal{O}}\left( {{n^2}t} \right)$ gates suffice. 2)Random quantum circuits with $\mathcal{O}\left( {{n^4}t} \right)$ gates form multiplicative-error unitary t-designs for t ≤Θ(2 n/2 ); for t ≤ Θ(2 2n/5 ), we show that $\tilde {\mathcal{O}}\left( {{n^2}t} \right)$ gates suffice. 3)The robust quantum circuit complexity of random quantum circuits grows linearly for an exponentially long time, proving the robust Brown–Susskind conjecture [1], [2]. We also show an analogous result for random reversible circuits. Our spectral gap bounds are proven by reducing random quantum circuits to a more structured walk: a modification of the "PFC ensemble" from [3] together with an expander on the alternating group due to Kassabov [4], for which we give an efficient implementation using reversible circuits. In our reduction, we approximate the structured walk with local random circuits without losing the gap, which uses tools from the study of frustration-free Hamiltonians.

Details

FOCS Conference 2024 Conference Paper

Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries

Tony Metger
Alexander Poremba
Makrand Sinha
Henry Yuen

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 research into random unitaries that “look” sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged: $t$ -designs are random unitaries that information-theoretically reproduce the first $t$ moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random. In this work, we take a unified approach to constructing $t$ -designs and PRUs. For this, we introduce and analyse the “ $PFC$ ensemble”, the product of a random computational basis permutation $P$, a random binary phase operator $F$, and a random Clifford unitary $C$. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise the $PFC$ ensemble to show the following: •Linear-depth $t$ -designs. We give the first construction of a (diamond-error) approximate $t$ -design with circuit depth linear in $t$. This follows from the $PFC$ ensemble by replacing the random phase and permutation operators with their $2t$ -wise independent counterparts. •Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i. e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from the $PFC$ ensemble by replacing the random phase and permutation operators with their pseudorandom counterparts. •Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) from $n$ to $n+\omega(\log n)$ qubits, a small modification of our PRU construction achieves adaptive security, i. e. even a distinguisher that can query the isometry adaptively in sequence cannot distinguish it from Haar random isometries. This gives the first construction of adaptive pseudorandom isometries. Under an additional conjecture, this proof also extends to adaptive PRUs.

Details

FOCS Conference 2024 Conference Paper

Succinct Arguments for QMA from Standard Assumptions via Compiled Nonlocal Games

Tony Metger
Anand Natarajan 0001
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 of Mahadev (FOCS '18), Bartusek et al. (CRYPTo ‘22) also constructed a succinct classical argument system for Q M A. However, their construction relied on post-quantumly secure indistinguishability obfuscation, a very strong primitive which is not known from standard cryptographic assumptions. In contrast, the primitives we use (namely, collapsing hash functions and a mild version of quantum homomorphic encryption) are much weaker and are implied by standard assumptions such as LWE. Our protocol is constructed using a general transformation which was designed by Kalai et al. (STOC '23) as a candidate method to compile any quantum nonlocal game into an argument system. Our main technical contribution is to analyze the soundness of this transformation when it is applied to a succinct self-test for Pauli measurements on maximally entangled states, the latter of which is a key component in the proof of MIP * = R E in Quantum complexity.

Details

FOCS Conference 2023 Conference Paper

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 complexity, namely the complexity of physically preparing a certain quantum state. We study the relation between two such state complexity classes: statePSPACE, which contains states that can be generated by space-uniform polynomial-space quantum circuits, and stateQIP, which contains states that a polynomialtime quantum verifier can generate by interacting with an all-powerful untrusted quantum prover. The latter class was recently introduced by Rosenthal and Yuen (ITCS 2022), who proved that statePSPACE $\subseteq$ stateQIP. Our main result is the reverse inclusion, stateQIP $\subseteq$ statePSPACE, thereby establishing equality of the two classes and providing a natural state-complexity analogue to the celebrated QIP = PSPACE theorem of Jain, et al. (J. ACM 2011). To prove this, we develop a polynomial-space quantum algorithm for solving a large class of exponentially large “PSPACE-computable” semidefinite programs (SDPs), which also prepares an optimiser encoded in a quantum state. Our SDP solver relies on recent blockencoding techniques from quantum algorithms, demonstrating that these techniques are also useful for complexity theory. Using similar techniques, we also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum polynomial space. We prove this by studying an algorithmic version of Uhlmann’s theorem and establishing an upper bound on the complexity of implementing Uhlmann transformations.

Details

FOCS Conference 2022 Conference Paper

Generalised entropy accumulation

Tony Metger
Omar Fawzi
David Sutter
Renato Renner

The min-entropy of a quantum system A conditioned on another quantum system E describes how much randomness can be extracted from A with respect to an adversary in possession of E. This quantity plays a crucial role in quantum cryptography: the security proofs of many quantum cryptographic protocols reduce to showing a lower bound on such a min-entropy. Here, we develop a new tool, called generalised entropy accumulation, for computing such bounds. Concretely, we consider a sequential process in which each step outputs a system A i and updates a side information register E. We prove that if this process satisfies a natural “non-signalling” condition between past outputs and future side information, the min-entropy of the outputs $A_{1}, \ldots, \ A_{n}$ conditioned on the side information E at the end of the process can be bounded from below by a sum of von Neumann entropies associated with the individual steps. This is a generalisation of the entropy accumulation theorem (EAT) [1], which deals with a more restrictive model of side information: there, past side information cannot be updated in subsequent rounds, and newly generated side information has to satisfy a Markov condition. Due to its more general model of side-information, our generalised EAT can be applied more easily and to a broader range of cryptographic protocols. In particular, it is the first general tool that is applicable to mistrustful device-independent cryptography. To demonstrate this, we give the first security proof for blind randomness expansion [2] against general adversaries. Furthermore, our generalised EAT can be used to give improved security proofs for quantum key distribution [3], and also has applications beyond quantum cryptography.

Details