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 operations (called Uhlmann transformations). We show that optimal Uhlmann transformations are rigid - in other words, they must be unique up to some well-characterized degrees of freedom. This rigidity is also robust: Uhlmann transformations achieving near-optimal overlaps must be close to the unique optimal transformation (again, up to well-characterized degrees of freedom). We describe two applications of our robust rigidity theorem: (a) we obtain better interactive proofs for synthesizing Uhlmann transformations and (b) we obtain a simple, alternative proof of the Gowers-Hatami theorem on the stability of approximate representations of finite groups.

Random reversible and quantum circuits form random walks on the alternating group Alt(2n) and unitary group SU(2n), 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 ≤ Θ(2n/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 ≤ Θ(2n/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 ≤Θ(2n/2); for t ≤ Θ(22n/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.

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 cryptographic assumption). Such protocols play a crucial role in the certification of quantum devices. Existing single-round protocols (like asking the quantum computer to factor a large number) require large quantum circuits, whereas multi-round ones use smaller circuits but require experimentally challenging mid-circuit measurements. As such, current proofs of quantumness are out of reach for near-term devices. In this work, we construct efficient single-round proofs of quantumness based on existing knowledge assumptions. While knowledge assumptions have not been previously considered in this context, we show that they provide a natural basis for separating classical and quantum computation. Specifically, we show that multi-round protocols based on Decisional Diffie-Hellman (DDH) or Learning With Errors (LWE) can be "compiled" into single-round protocols using a knowledge-of-exponent assumption or knowledge-of-lattice-point assumption, respectively. We also prove an adaptive hardcore-bit statement for a family of claw-free functions based on DDH, which might be of independent interest. Previous approaches to constructing single-round protocols relied on the random oracle model and thus incurred the overhead associated with instantiating the oracle with a cryptographic hash function. In contrast, our protocols have the same resource requirements as their multi-round counterparts without necessitating mid-circuit measurements, making them, arguably, the most efficient single-round proofs of quantumness to date. Our work also helps in understanding the interplay between black-box/white-box reductions and cryptographic assumptions in the design of proofs of quantumness.

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 only trying to decide if the ground state is volume-law vs near area-law entangled. We prove this by constructing strong forms of pseudoentanglement in a public-key setting, where the circuits used to prepare the states are public knowledge. In particular, we construct two families of quantum circuits which produce volume-law vs near area-law entangled states, but nonetheless the classical descriptions of the circuits are indistinguishable under the Learning with Errors (LWE) assumption. Indistinguishability of the circuits then allows us to translate our construction to Hamiltonians. Our work opens new directions in Hamiltonian complexity, for example whether it is difficult to learn certain phases of matter.

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.

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.

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.

Quantum mechanical effects have enabled the construction of cryptographic primitives that are impossible classically. For example, quantum copy-protection allows for a program to be encoded in a quantum state in such a way that the program can be evaluated, but not copied. Many of these cryptographic primitives are two-party protocols, where one party, Bob, has full quantum computational capabilities, and the other party, Alice, is only required to send random BB84 states to Bob. In this work, we show how such protocols can generically be converted to ones where Alice is fully classical, assuming that Bob cannot efficiently solve the LWE problem. In particular, this means that all communication between (classical) Alice and (quantum) Bob is classical, yet they can still make use of cryptographic primitives that would be impossible if both parties were classical. We apply this conversion procedure to obtain quantum cryptographic protocols with classical communication for unclonable encryption, copy-protection, computing on encrypted data, and verifiable blind delegated computation. The key technical ingredient for our result is a protocol for classically-instructed parallel remote state preparation of BB84 states. This is a multi-round protocol between (classical) Alice and (quantum polynomial-time) Bob that allows Alice to certify that Bob must have prepared n uniformly random BB84 states (up to a change of basis on his space). While previous approaches could only certify one- or two-qubit states, our protocol allows for the certification of an n-fold tensor product of BB84 states. Furthermore, Alice knows which specific BB84 states Bob has prepared, while Bob himself does not. Hence, the situation at the end of this protocol is (almost) equivalent to one where Alice sent n random BB84 states to Bob. This allows us to replace the step of preparing and sending BB84 states in existing protocols by our remote-state preparation protocol in a generic and modular way.

We prove concentration bounds for the following classes of quantum states: (i) output states of shallow quantum circuits, answering an open question from [DPMRF22]; (ii) injective matrix product states; (iii) output states of dense Hamiltonian evolution, i.e. states of the form $e^{ιH^{(p)}} \cdots e^{ιH^{(1)}} |ψ_0\rangle$ for any $n$-qubit product state $|ψ_0\rangle$, where each $H^{(i)}$ can be any local commuting Hamiltonian satisfying a norm constraint, including dense Hamiltonians with interactions between any qubits. Our proofs use polynomial approximations to show that these states are close to local operators. This implies that the distribution of the Hamming weight of a computational basis measurement (and of other related observables) concentrates. An example of (iii) are the states produced by the quantum approximate optimisation algorithm (QAOA). Using our concentration results for these states, we show that for a random spin model, the QAOA can only succeed with negligible probability even at super-constant level $p = o(\log \log n)$, assuming a strengthened version of the so-called overlap gap property. This gives the first limitations on the QAOA on dense instances at super-constant level, improving upon the recent result [BGMZ22].

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 Aiand 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.

Quantum computations are typically performed as a sequence of basic operations, called quantum gates. Different gate sequences, called quantum circuits, can implement the same overall quantum computation. Since every additional quantum gate takes time and introduces noise into the system, it is important to find the smallest possible quantum circuit that implements a given computation, especially for near-term quantum devices that can execute only a limited number of quantum gates before noise renders the computation useless. An important building block for many quantum circuit optimization techniques is pattern matching: given a large and small quantum circuit, we would like to find all maximal matches of the small circuit, called a pattern , in the large circuit, considering pairwise commutation of quantum gates. In this work, we present the first classical algorithm for pattern matching that provably finds all maximal matches and is efficient enough to be practical for circuit sizes typical for near-term devices. We demonstrate numerically 1 that combining our algorithm with known pattern-matching-based circuit optimization techniques reduces the gate count of a random quantum circuit by ∼ 30% and can further improve practically relevant quantum circuits that were already optimized with state-of-the-art techniques.

Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple non-communicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.