I’m always happy to talk about my research! Feel free to reach out at tmetger [at] ethz [dot] ch.
Selected publications
Incompressibility and spectral gaps of random circuits
C.F. Chen, J. Haah, J. Haferkamp, Y. Liu, T. Metger, and X. Tan.
Summary: We prove that the random walk produced by random (classical or quantum) circuits is spectrally gapped, which means it mixes very quickly. This implies that random circuits are $t$-designs in depth linear in $t$ and that random circuits are essentially incompressible, proving the robust Brown–Susskind conjecture from quantum gravity.
[full abstract]
Random reversible and quantum circuits form random walks on the alternating group $\mathrm{Alt}(2^n)$ and unitary group $\mathrm{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 $\Omega(n^{-3})$ for all $t\geq 1$, and the gap for random quantum circuits is $\Omega(n^{-3})$ for $t \leq \Theta(2^{n/2})$. Importantly, these gaps are independent of $t$ in the respective regimes. We can further improve both gaps to $n^{-1}/\mathrm{polylog}(n, t)$ for $t \leq 2^{\Theta(n)}$, which is tight up to polylog factors in $n$ and $t$. Our spectral gap results have a number of consequences:
- Random reversible circuits with $\mathcal{O}(n^4 t)$ gates form multiplicative-error $t$-wise independent (even) permutations for all $t\geq 1$; for $t \leq \Theta(2^{n/6.1})$, we show that $\tilde{\mathcal{O}}(n^2 t)$ gates suffice.
- Random quantum circuits with $\mathcal{O}(n^4 t)$ gates form multiplicative-error unitary $t$-designs for $t \leq \Theta(2^{n/2})$; for $t \leq \Theta(2^{2n/5})$, we show that $\tilde{\mathcal{O}}(n^2 t)$ gates suffice.
- The robust quantum circuit complexity of random quantum circuits grows linearly for an exponentially long time, proving the robust Brown–Susskind conjecture. 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 Metger et al. together with an expander on the alternating group due to Kassabov, 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.
Succinct arguments for QMA from standard assumptions via compiled nonlocal games
T. Metger, A. Natarajan, and T. Zhang.
FOCS 2024 (65th Annual Symposium on Foundations of Computer Science).
Contributed talk at QCrypt 2024 (Best Student Paper Prize).
Summary: We construct succinct arguments for QMA, i.e. a protocol for a classical verifier to check the answer to a QMA question using a computationally bounded untrusted prover with extremely little communication. Our proof combines cryptographic ideas with self-testing techniques inspired by the $\mathsf{MIP}^* = \mathsf{RE}$ proof.
[full abstract]
We construct a succinct classical argument system for $\mathsf{QMA}$, the quantum analogue of $\mathsf{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 $\mathsf{QMA}$. 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 $\mathsf{MIP}^* = \mathsf{RE}$ in quantum complexity.
Simple constructions of linear-depth t-designs and pseudorandom unitaries
T. Metger, A. Poremba, M. Sinha, and H. Yuen.
FOCS 2024 (65th Annual Symposium on Foundations of Computer Science).
Contributed talk at QCrypt 2024.
Summary: We give the first construction of $t$-designs (the quantum analogue to $t$-wise independent functions) that only require depth linear in $t$, which is optimal. We also give the first construction of pseudorandom unitaries (the quantum analogue of pseudorandom functions) secure against general non-adaptive adversaries. The main technical insight for both of these results is that the product of a random permutation, random phase, and random Clifford approximates the uniform distribution on unitaries extremely well.
[full abstract]
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 arbitrary 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.
Unitary Complexity and the Uhlmann Transformation Problem
J. Bostanci, Y. Efron, T. Metger, A. Poremba, L. Qian, and H. Yuen.
Long plenary talk at QIP 2024.
Summary: We introduce a formalism to describe the complexity of quantum state transformation problems, which are not naturally captured by decision complexity. We use this formalism to study a wide variety of “fully quantum” tasks, from breaking quantum commitments to implementing quantum communication protocols and decoding Hawking radiation. It turns out that these problems are connected by the Uhlmann transformation problem, the task of mapping different purifications of a state to each other.
[full abstract]
State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot easily be characterized using traditional complexity theory, which focuses on tasks with classical inputs and outputs.
To study the complexity of such state transformation tasks, we introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. We formalize this as the Uhlmann Transformation Problem, an algorithmic version of Uhlmann’s theorem. Then, we prove structural results relating the complexity of the Uhlmann Transformation Problem, polynomial space quantum computation, and zero knowledge protocols.
The Uhlmann Transformation Problem allows us to characterize the complexity of a variety of tasks in quantum information processing, including decoding noisy quantum channels, breaking falsifiable quantum cryptographic assumptions, implementing optimal prover strategies in quantum interactive proofs, and decoding the Hawking radiation of black holes. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
Generalised entropy accumulation
T. Metger, O. Fawzi, D. Sutter, and R. Renner (ordered by contribution).
FOCS 2022 (IEEE 63rd Annual Symposium on Foundations of Computer Science).
Plenary talk at QIP 2023 and contributed talk at QCrypt 2022 (Best Student Paper Prize).
Summary: We prove that quantum min-entropy “accumulates” in very general sequential quantum processes. In subsequent work, we have used our generalised entropy accumulation theorem to give the first general security proof for prepare-and-measure QKD protocols.
[full abstract]
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, \dots, 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), 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 against general adversaries. Furthermore, our generalised EAT can be used to give improved security proofs for quantum key distribution, and also has applications beyond quantum cryptography.
Full list of publications
See also Google Scholar for a possibly more up-to-date list.
(Following the convention in theoretical computer science, authors are ordered alphabetically by default. A $(\mathcal{C})$ at the end of the author list denotes ordering by contribution (as is common in physics); an $^*$ denotes joint first authorship.)
-
C. Akers, A. Bouland, L. Chen, T. Kohler, T. Metger, U. Vazirani.
Holographic pseudoentanglement and the complexity of the AdS/CFT dictionary. -
A. Arqand, T. Metger, and E. Tan.
Mutual information chain rules for security proofs robust against device imperfections.
Contributed talk at QCrypt 2024. -
C.F. Chen, J. Haah, J. Haferkamp, Y. Liu, T. Metger, and X. Tan.
Incompressibility and spectral gaps of random circuits. -
P. Arabadjieva, A. Gheorghiu, V. Gitton, and T. Metger.
Single-Round Proofs of Quantumness from Knowledge Assumptions.
ITCS 2025 (16th Innovations in Theoretical Computer Science Conference). -
T. Metger, A. Natarajan, and T. Zhang.
Succinct arguments for QMA from standard assumptions via compiled nonlocal games.
FOCS 2024 (65th Annual Symposium on Foundations of Computer Science).
Contributed talk at QCrypt 2024 (Best Student Paper Prize). -
T. Metger, A. Poremba, M. Sinha, and H. Yuen.
Simple constructions of linear-depth t-designs and pseudorandom unitaries.
FOCS 2024 (65th Annual Symposium on Foundations of Computer Science).
Contributed talk at QCrypt 2024. -
A. Bouland, B. Fefferman, S. Ghosh, T. Metger, U. Vazirani, C. Zhang, and Z. Zhou.
Public-key pseudoentanglement and the hardness of learning ground state entanglement structure.
CCC 2024 (39th Computational Complexity Conference).
Contributed talk at QIP 2024. -
J. Bostanci, Y. Efron, T. Metger, A. Poremba, L. Qian, and H. Yuen.
Unitary Complexity and the Uhlmann Transformation Problem.
Long plenary talk at QIP 2024. -
T. Metger and H. Yuen.
stateQIP = statePSPACE.
FOCS 2023 (IEEE 64th Annual Symposium on Foundations of Computer Science).
Contributed talk at QIP 2023. -
A. Anshu and T. Metger.
Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations.
ITCS 2023 (14th Innovations in Theoretical Computer Science Conference).
Contributed talk at TQC 2023. -
T. Metger, R. Renner $(\mathcal{C})$.
Security of quantum key distribution from generalised entropy accumulation.
Nature Communications 14 (1), 5272. -
T. Metger, O. Fawzi, D. Sutter, and R. Renner $(\mathcal{C})$.
Generalised entropy accumulation.
FOCS 2022 (IEEE 63rd Annual Symposium on Foundations of Computer Science).
Plenary talk at QIP 2023 and contributed talk at QCrypt 2022 (Best Student Paper Prize). -
A. Gheorghiu, T. Metger, and A. Poremba.
Quantum cryptography with classical communication: parallel remote state preparation for copy-protection, verification, and more.
ICLAP 2023 (50th International Colloquium on Automata, Languages, and Programming)
Presented as a contributed talk at TQC 2022 and QCrypt 2022. -
T. Metger, Y. Dulek, A. Coladangelo, and R. Arnon-Friedman $(\mathcal{C})$.
Device-independent quantum key distribution from computational assumptions.
New J. Phys. 23 123021 (2021). -
T. Metger and T. Vidick.
Self-testing of a single quantum device under computational assumptions.
ITCS 2021 (12th Innovations in Theoretical Computer Science Conference)
Journal version: Quantum 5, 544 (2021) Presented as a contributed talk at TQC 2020, and as a joint contributed talk with “Device-independent quantum key distribution from computational assumptions” at QIP 2021 and QCrypt 2021 (Best Student Paper Prize).
Featured in Nature Physics. -
H. Poulsen Nautrup$^*$, T. Metger$^*$, R. Iten$^*$, S. Jerbi, L. M. Trenkwalder, H. Wilming, H. Briegel, and R. Renner $(\mathcal{C})$.
Operationally meaningful representations of physical systems in neural networks.
Mach. Learn.: Sci. Technol. 3 045025 (2022) Contributed talk at QTML 2020. -
R. Iten, R. Moyard, T. Metger, D. Sutter, and S. Woerner $(\mathcal{C})$.
Exact and practical pattern matching for quantum circuit optimization. ACM Transactions on Quantum Computing 3 (1), 1-41 (2022). -
R. Iten$^*$, T. Metger$^*$, H. Wilming, L. del Rio, and R. Renner $(\mathcal{C})$.
Discovering physical concepts with neural networks.
Phys. Rev. Lett. 124, 010508 (2020). Editor’s choice.
Press coverage: Nature, APS Physics Viewpoint, APS Physics Highlights of the Year 2020, MIT Technology Review, Neue Zürcher Zeitung (in German), Le Monde (in French).