John Wright 0004

STOC Conference 2025 Conference Paper

The State Hidden Subgroup Problem and an Efficient Algorithm for Locating Unentanglement

• Adam Bouland
• Tudor Giurgica-Tiron
• John Wright 0004

We study a generalization of entanglement testing which we call the “hidden cut problem.” Taking as input copies of an n -qubit pure state which is product across an unknown bipartition, the goal is to learn precisely where the state is unentangled, i.e. to determine which of the exponentially many possible cuts separates the state. We give a polynomial-time quantum algorithm which can find the cut using O ( n /є 2 ) many copies of the state, which is optimal up to logarithmic factors. Our algorithm also generalizes to learn the entanglement structure of arbitrary product states. In the special case of Haar-random states, we further show that our algorithm requires circuits of only constant depth. To develop our algorithm, we introduce a state generalization of the hidden subgroup problem (StateHSP) which might be of independent interest, in which one is given a quantum state invariant under an unknown subgroup action, with the goal of learning the hidden symmetry subgroup. We show how the hidden cut problem can be formulated as a StateHSP with a carefully chosen Abelian group action. We then prove that Fourier sampling on the hidden cut state produces similar outcomes as a variant of the well-known Simon’s problem, allowing us to find the hidden cut efficiently. Therefore, our algorithm can be interpreted as an extension of Simon’s algorithm to entanglement testing. We discuss possible applications of StateHSP and hidden cut problems to cryptography and pseudorandomness.

STOC Conference 2024 Conference Paper

A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography

• Alex Lombardi
• Fermi Ma
• John Wright 0004

The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any n -qubit unitary U can be implemented by an efficient quantum algorithm A augmented with an oracle that computes an arbitrary Boolean function f . In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function? In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries U such that no quantum polynomial-time oracle algorithm A f can implement U , even approximately, if it only makes one (quantum) query to f . Our approach also has implications for quantum cryptography: we prove (relative to a random oracle) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries A f . Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, our result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks. To prove this result, we formulate unitary synthesis as an efficient challenger-adversary game, which enables proving lower bounds by analyzing the maximum success probability of an adversary A f . Our main technical insight is to identify a natural spectral relaxation of the one-query optimization problem, which we bound using tools from random matrix theory. We view our framework as a potential avenue to rule out polynomial-query unitary synthesis, and we state conjectures in this direction.

SODA Conference 2023 Conference Paper

Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality

• Yeongwoo Hwang
• Joe Neeman
• Ojas Parekh
• Kevin Thompson 0007
• John Wright 0004

SODA Conference 2022 Conference Paper

Testing matrix product states

• Mehdi Soleimanifar
• John Wright 0004

Matrix product states (MPS) are a class of physically-relevant quantum states which arise in the study of quantum many-body systems. A quantum state comprised of n qudits is said to be an MPS of bond dimension r if the reduced density matrix ψ 1, …, k has rank r for each k ∊ {1, …, n }. When r = 1, this corresponds to the set of product states, i. e. states of the form | ψ 1 〉 ⊗ ⃛ ⊗ | ψ n ), which possess no entanglement. For larger values of r, this yields a more expressive class of quantum states, which are allowed to possess limited amounts of entanglement. Devising schemes for testing the amount of entanglement in quantum systems has played a crucial role in quantum computing and information theory. In this work, we study the problem of testing whether an unknown state | ψ 〉 is an MPS in the property testing model. In this model, one is given m identical copies of | ψ 〉, and the goal is to determine whether | ψ 〉 is an MPS of bond dimension r or whether | ψ 〉 is far from all such states. For the case of product states, we study the product test, a simple two-copy test previously analyzed by Harrow and Montanaro [17], and a key ingredient in their proof that QMA(2) = QMA( k ) for k ≥ 2. We give a new and simpler analysis of the product test which achieves an optimal bound for a wide range of parameters, answering open problems in [17] and [23]. For the case of r ≥ 2, we give an efficient algorithm for testing whether | ψ 〉 is an MPS of bond dimension r using m = O ( nr 2 ) copies, independent of the dimensions of the qudits, and we show that Ω( n 1/2 ) copies are necessary for this task. This lower bound shows that a dependence on the number of qudits n is necessary, in sharp contrast to the case of product states where a constant number of copies suffices.

FOCS Conference 2021 Conference Paper

Quantum soundness of testing tensor codes

• Zhengfeng Ji
• Anand Natarajan 0001
• Thomas Vidick
• John Wright 0004
• Henry Yuen

A locally testable code is an error-correcting code that admits very efficient probabilistic tests of membership. Tensor codes provide a simple family of combinatorial constructions of locally testable codes that generalize the family of Reed-Muller codes. The natural test for tensor codes, the axis-parallel line vs. point test, plays an essential role in constructions of probabilistically checkable proofs. We analyze the axis-parallel line vs. point test as a two-prover game and show that the test is sound against quantum provers sharing entanglement. Our result implies the quantum-soundness of the low individual degree test, which is an essential component of the MIP* = RE theorem. Our proof also generalizes to the infinite-dimensional commuting-operator model of quantum provers.

FOCS Conference 2019 Conference Paper

NEEXP is Contained in MIP

• Anand Natarajan 0001
• John Wright 0004

We study multiprover interactive proof systems. The power of classical multiprover interactive proof systems, in which the provers do not share entanglement, was characterized in a famous work by Babai, Fortnow, and Lund (Computational Complexity 1991), whose main result was the equality MIP = NEXP. The power of quantum multiprover interactive proof systems, in which the provers are allowed to share entanglement, has proven to be much more difficult to characterize. The best known lower-bound on MIP* is NEXP ⊆ MIP* due to Ito and Vidick (FOCS 2012). As for upper bounds, MIP* could be as large as RE, the class of recursively enumerable languages. The main result of this work is the inclusion NEEXP = NTIME[2 2poly(n) ] ⊆ MIP*. This is an exponential improvement over the prior lower bound and shows that proof systems with entangled provers are at least exponentially more powerful than classical provers. In our protocol the verifier delegates a classical, exponentially large MIP protocol for NEEXP to two entangled provers: the provers obtain their exponentially large questions by measuring their shared state, and use a classical PCP to certify the correctness of their exponentially-long answers. For the soundness of our protocol, it is crucial that each player should not only sample its own question correctly but also avoid performing measurements that would reveal the other player's sampled question. We ensure this by commanding the players to perform a complementary measurement, relying on the Heisenberg uncertainty principle to prevent the forbidden measurements from being performed.

STOC Conference 2019 Conference Paper

Quantum state certification

• Costin Badescu
• Ryan O'Donnell
• John Wright 0004

We consider the problem of quantum state certification , where one is given n copies of an unknown d -dimensional quantum mixed state ρ, and one wants to test whether ρ is equal to some known mixed state σ or else is є-far from σ. The goal is to use notably fewer copies than the Ω( d 2 ) needed for full tomography on ρ (i.e., density estimation). We give two robust state certification algorithms: one with respect to fidelity using n = O ( d /є) copies, and one with respect to trace distance using n = O ( d /є 2 ) copies. The latter algorithm also applies when σ is unknown as well. These copy complexities are optimal up to constant factors.

SODA Conference 2018 Conference Paper

Which Distribution Distances are Sublinearly Testable?

• Constantinos Daskalakis
• Gautam Kamath 0001
• John Wright 0004

Given samples from an unknown distribution p and a description of a distribution q, are p and q close or far? This question of “identity testing” has received significant attention in the case of testing whether p and q are equal or far in total variation distance. However, in recent work [VV11a, ADK15, DP17], the following questions have been been critical to solving problems at the frontiers of distribution testing: Alternative Distances: Can we test whether p and q are far in other distances, say Hellinger? Tolerance: Can we test when p and q are close, rather than equal? And if so, close in which distances? Motivated by these questions, we characterize the complexity of distribution testing under a variety of distances, including total variation, ℓ 2, Hellinger, Kullback-Leibler, and χ 2. For each pair of distances d 1 and d 2, we study the complexity of testing if p and q are close in d 1 versus far in d 2, with a focus on identifying which problems allow strongly sublinear testers (i. e. , those with complexity O ( n 1– γ ) for some γ > 0 where n is the size of the support of the distributions p and q ). We provide matching upper and lower bounds for each case. We also study these questions in the case where we only have samples from q (equivalence testing), showing qualitative differences from identity testing in terms of when tolerance can be achieved. Our algorithms fall into the classical paradigm of χ 2 -statistics, but require crucial changes to handle the challenges introduced by each distance we consider. Finally, we survey other recent results in an attempt to serve as a reference for the complexity of various distribution testing problems.

STOC Conference 2017 Conference Paper

Efficient quantum tomography II

• Ryan O'Donnell
• John Wright 0004

STOC Conference 2016 Conference Paper

Efficient quantum tomography

• Ryan O'Donnell
• John Wright 0004

In the quantum state tomography problem, one wishes to estimate an unknown d -dimensional mixed quantum state ρ, given few copies. We show that O ( d /ε) copies suffice to obtain an estimate ρ that satisfies ||ρ − ρ|| F 2 ≤ ε (with high probability). An immediate consequence is that O ((ρ) · d /ε 2 ) ≤ O ( d 2 /ε 2 ) copies suffice to obtain an ε-accurate estimate in the standard trace distance. This improves on the best known prior result of O ( d 3 /ε 2 ) copies for full tomography, and even on the best known prior result of O ( d 2 log( d /ε)/ε 2 ) copies for spectrum estimation. Our result is the first to show that nontrivial tomography can be obtained using a number of copies that is just linear in the dimension. Next, we generalize these results to show that one can perform efficient principal component analysis on ρ. Our main result is that O ( k d /ε 2 ) copies suffice to output a rank- k approximation ρ whose trace-distance error is at most ε more than that of the best rank- k approximator to ρ. This subsumes our above trace distance tomography result and generalizes it to the case when ρ is not guaranteed to be of low rank. A key part of the proof is the analogous generalization of our spectrum-learning results: we show that the largest k eigenvalues of ρ can be estimated to trace-distance error ε using O ( k 2 /ε 2 ) copies. In turn, this result relies on a new coupling theorem concerning the Robinson–Schensted–Knuth algorithm that should be of independent combinatorial interest.

STOC Conference 2015 Conference Paper

Quantum Spectrum Testing

• Ryan O'Donnell
• John Wright 0004

In this work, we study the problem of testing properties of the spectrum of a mixed quantum state. Here one is given n copies of a mixed state ρ∈ C d x d and the goal is to distinguish (with high probability) whether ρ's spectrum satisfies some property P or whether it is at least ε-far in l 1 -distance from satisfying P. This problem was promoted under the name of testing unitarily invariant properties of mixed states. It is the natural quantum analogue of the classical problem of testing symmetric properties of probability distributions. Unlike property testing probability distributions---where one generally hopes for algorithms with sample complexity that is sublinear in the domain size---here the hope is for algorithms with subquadratic copy complexity in the dimension d. This is because the (frequently rediscovered) "empirical Young diagram (EYD) algorithm" [ARS88,KW01,HM02,CM06] can estimate the spectrum of any mixed state up to ε-accuracy using only O(d 2 /ε 2 ) copies. In this work, we show that given a mixed state ρ ∈ C d x d : Θ(d/ε 2 ) copies are necessary and sufficient to test whether ρ is the maximally mixed state, i.e., has spectrum (1/d, ..., 1/d). This can be viewed as the quantum analogue of a result of Paninski [Pan08]. Θ(r 2 /ε) copies are necessary and sufficient to test with one-sided error whether ρ has rank r, i.e., has at most r nonzero eigenvalues. For two-sided error, a lower bound of Ω(r/ε) copies holds. Θ(r 2 ) copies are necessary and sufficient to distinguish whether ρ is maximally mixed on an r-dimensional or an (r+1)-dimensional subspace. More generally, for r vs. r+Δ (with 1 ≤ Δ ≤ r), Θ(r 2 /Δ) copies are necessary and sufficient. The EYD algorithm requires Ω(d 2 /ε 2 ) copies to estimate the spectrum of ρ up to ε-accuracy, nearly matching the known upper bound. Our techniques involve the asymptotic representation theory of the symmetric group; in particular Kerov's algebra of polynomial functions on Young diagrams.

SODA Conference 2014 Conference Paper

Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs

• Ryan O'Donnell
• John Wright 0004
• Chenggang Wu 0003
• Yuan Zhou 0007

Building on work of Cai, Fürer, and Immerman [18], we show two hardness results for the Graph Isomorphism problem. First, we show that there are pairs of nonisomorphic n -vertex graphs G and H such that any sum-of-squares (SOS) proof of nonisomorphism requires degree Ω( n ). In other words, we show an Ω( n )-round integrality gap for the Lasserre SDP relaxation. In fact, we show this for pairs G and H which are not even (1 – 10 −14 )-isomorphic. (Here we say that two n -vertex, m -edge graphs G and H are α -isomorphic if there is a bijection between their vertices which preserves at least αm edges.) Our second result is that under the R3XOR Hypothesis [23] (and also any of a class of hypotheses which generalize the R3XOR Hypothesis), the robust Graph Isomorphism is hard. I. e. for every ∊ > 0, there is no efficient algorithm which can distinguish graph pairs which are (1 — ∊)-isomorphic from pairs which are not even (1 – ∊ 0 )-isomorphic for some universal constant ∊ 0. Along the way we prove a robust asymmetry result for random graphs and hypergraphs which may be of independent interest.

STOC Conference 2012 Conference Paper

A new point of NP-hardness for unique games

• Ryan O'Donnell
• John Wright 0004

We show that distinguishing 1/2-satisfiable Unique-Games instances from (3/8 + ε)-satisfiable instances is NP-hard (for all ε > 0). A consequence is that we match or improve the best known c vs. s NP-hardness result for Unique-Games for all values of c (except for c very close to 0). For these c, ours is the first hardness result showing that it helps to take the alphabet size larger than 2. Our NP-hardness reductions are quasilinear-size and thus show nearly full exponential time is required, assuming the ETH.