How many copies of a mixed state \(\rho \in \mathbb{C}^{d \times d}\) are needed to learn its spectrum? To date, the best known algorithms for spectrum estimation require as many copies as full state tomography, suggesting the possibility that learning a state's spectrum might be as difficult as learning the entire state. We show that this is not the case in the setting of unentangled measurements, by giving a spectrum estimation algorithm that uses \(n = O\left(d^{3} \cdot (\log \log(d) / \log(d))^{4}\right)\) copies of \(\rho\), which is asymptotically fewer than the \(n = \Omega(d^{3})\) copies necessary for full state tomography. Our algorithm is inspired by the technique of local moment matching from classical statistics, and shows how it can be applied in the quantum setting.

In this work, we establish the strongest known lower bounds against QAC0, while allowing its full power of polynomially many ancillae and gates. Our two main results show that: (1) Depth 3 QAC0 circuits cannot compute PARITY regardless of size, and require at least Ω(exp(√n)) many gates to compute MAJORITY. (2) Depth 2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size.

In the problem of quantum state tomography, one is given n copies of an unknown rank-r mixed state ρ ∈ ℂd × d and asked to produce an estimator of ρ. In this work, we present the debiased Keyl’s algorithm, the first estimator for full state tomography which is both unbiased and sample-optimal. We derive an explicit formula for the second moment of our estimator, with which we show the following five applications. First, we give a new proof that n = O(rd/ε2) copies are sufficient to learn a rank-r mixed state to trace distance error ε, which is optimal. Second, we show that n = O(rd/ε2) copies are sufficient to learn to error ε in the more challenging Bures distance, which is also optimal. Third, we consider full state tomography when one is only allowed to measure k copies at once. We show that n =O(max(d3/√kε2, d2/ε2 ) ) copies suffice to learn in trace distance. This improves on the prior work of Chen et al. and matches their lower bound. Fourth, for shadow tomography, we show that O(log(m)/ε2) copies are sufficient to learn m given observables O1, …, Om in the ”high accuracy regime”, when ε = O(1/d), improving on a result of Chen et al. More generally, we show that if tr(Oi2) ≤ F for all i, then n = O(log(m) · (min{√r F/ε, F2/3/ε4/3}+ 1/ε2)) copies suffice, improving on existing work. Finally, for quantum metrology, we give a locally unbiased algorithm whose mean squared error matrix is upper bounded by twice the inverse of the quantum Fisher information matrix in the asymptotic limit of large n, which is optimal.

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

The Gaussian noise stability of a function f: ℝn → {-1,1} is the expected value of f (x) · f (y) over ρ-correlated Gaussian random variables x and y. Borell's inequality states that for —1 ≤ ρ ≤ 0, this is minimized by the mean-zero halfspace f (x) = sign(x1). In this work, we conjecture that a natural generalization of this result holds for functions f: ℝn → Sk-1 which output k-dimensional unit vectors. Our main conjecture, which we call the vector-valued Borell's inequality, asserts that the expectation Ex~ρy 〈f(x), f(y)〉 is minimized by the function f (x) = x≤k/||x≤k||, where x≤k = (x1,…, xk). We give several pieces of evidence in favor of this conjecture, including a proof that it does indeed hold in the special case of n = k.

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(nr2) copies, independent of the dimensions of the qudits, and we show that Ω(n1/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.

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.

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[22poly(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.

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 Ω(d2) 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.

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 d1 and d2, we study the complexity of testing if p and q are close in d1 versus far in d2, with a focus on identifying which problems allow strongly sublinear testers (i.e., those with complexity O(n1–γ) 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.

We continue our analysis of: (i) "Quantum tomography", i.e., learning a quantum state, i.e., the quantum generalization of learning a discrete probability distribution; (ii) The distribution of Young diagrams output by the RSK algorithm on random words. Regarding (ii), we introduce two powerful new tools: first, a precise upper bound on the expected length of the longest union of k disjoint increasing subsequences in a random length-n word with letter distribution α1 ≥ α2 ≥ … ≥ αd. Our bound has the correct main term and second-order term, and holds for all n, not just in the large-n limit. Second, a new majorization property of the RSK algorithm that allows one to analyze the Young diagram formed by the lower rows λk, λk+1, … of its output. These tools allow us to prove several new theorems concerning the distribution of random Young diagrams in the nonasymptotic regime, giving concrete error bounds that are optimal, or nearly so, in all parameters. As one example, we give a fundamentally new proof of the celebrated fact that the expected length of the longest increasing sequence in a random length-n permutation is bounded by 2√n. This is the k = 1, αi ≡ 1/d, d → ∞ special case of a much more general result we prove: the expected length of the kth Young diagram row produced by an α-random word is αk n ± 2√αkd n.

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 ||ρ − ρ||F2 ≤ ε (with high probability). An immediate consequence is that O((ρ) · d/ε2) ≤ O(d2/ε2) copies suffice to obtain an ε-accurate estimate in the standard trace distance. This improves on the best known prior result of O(d3/ε2) copies for full tomography, and even on the best known prior result of O(d2log(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.

We show that for any odd k and any instance I of the max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a 1/2 + Omega(1/sqrt(D)) fraction of I's constraints, where D is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a quantum algorithm to find an assignment satisfying a 1/2 Omega(D^{-3/4}) fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a mu + Omega(1/sqrt(degree)) fraction of constraints, where mu is the fraction that would be satisfied by a uniformly random assignment.

An instance of the 2-Lin(2) problem is a system of equations of the form "x_i + x_j = b (mod 2)". Given such a system in which it's possible to satisfy all but an epsilon fraction of the equations, we show it is NP-hard to satisfy all but a C*epsilon fraction of the equations, for any C < 11/8 = 1.375 (and any 0 < epsilon <= 1/8). The previous best result, standing for over 15 years, had 5/4 in place of 11/8. Our result provides the best known NP-hardness even for the Unique Games problem, and it also holds for the special case of Max-Cut. The precise factor 11/8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2. Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitation on gadget reductions was known.

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 ρ∈ Cd 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 l1-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.

In this work, we study the parity complexity measures pCmin[f] and PDT[f]. Pcmin[f] is the parity kill number of f, the fewest number of parities on the input variables one has to fix in order to "kill" f, i.e. To make it constant. PDT[f] is the depth of the shortest emph{parity decision tree} which computes f. These complexity measures have in recent years become increasingly important in the fields of communication complexity [1], [2], [3], [4] and pseudorandomness [5], [6], [7]. Our main result is a composition theorem for pCmin. The k-th power of f, denoted f^{circ k}, is the function which results from composing f with itself k times. We prove that if f is not a parity function, then pCmin[f^{circ k}] geq Omega(Cmin[f]^{k}). In other words, the parity kill number of f is essentially super multiplicative in the normal kill number of f (also known as the minimum certificate complexity). As an application of our composition theorem, we show lower bounds on the parity complexity measures of sort^{circ k} and HI^{circ k}. Here sort is the sort function due to Ambainis [8], and HI is Kushilevitz's hemi-icosahedron function [9]. In doing so, we disprove a conjecture of Montanaro and Osborne [2] which had applications to communication complexity and computational learning theory. In addition, we give new lower bounds for conjectures of [2], [3] and [4].

Given ƒ : {--1, 1}n → {-- 1, 1}, define the spectral distribution of ƒ to be the distribution on subsets of [n] in which the set S is sampled with probability ƒ(S)2. Then the Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [2] states that there is some absolute constant C such that H[ƒ2] ≤ C ⋅ Inf[ƒ]. Here, H[ƒ2] denotes the Shannon entropy of ƒ's spectral distribution, and Inf[ƒ] is the total influence of ƒ. This conjecture is one of the major open problems in the analysis of Boolean functions, and settling it would have several interesting consequences.

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.

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.