Quantum algorithms, complexity & simulation

A central challenge in quantum algorithms and cryptography is reasoning about algorithms with oracle access to a random group element (e.g. a random function, permutation, or unitary). Can we efficiently simulate such algorithms? Can we determine what they know after t queries? A classical tool for this is lazy sampling: the oracle does not commit to the full group element upfront, but rather samples partial information about it on the fly. We study a quantum analog of lazy sampling: compressed oracles (or recording oracles). These are quantum data structures that allow on-the-fly simulation for quantum queries, originally introduced by Zhandry (CRYPTO '19) for random functions, and generalized to unitaries by Ma-Huang (STOC '25) and permutations by Carolan (STOC '26), and used to great effect in security proofs and lower bounds due to their interpretability. We define and analyze a general-purpose and interpretable path-recording oracle, derived from first principles, that perfectly simulates random elements of any closed subgroup of $U(N)$. Our oracle stores, in superposition, t input-output pairs, with updates described in terms of the commutant of the group's tensor power representation. This transparently records the information the algorithm has learned. Our oracle builds on recent work of Grinko-Yoshida (QIP '26), who gave a different general-purpose compressed oracle without clear interpretability. One interesting application of our path-recording is allowing direct comparisons between compressed oracles of different groups, giving a new technique for proving pseudorandomness results. For example, comparing SN and $U(N)$ yields what is arguably the simplest construction to date of pseudorandom unitaries: the product PC of a pseudorandom permutation and a random Clifford, improving on the prior PFC construction (Metger-Poremba-Sinha-Yuen, FOCS '24; Ma-Huang, STOC '25).

Given a matrix $A$, the goal of the entrywise low-rank approximation problem is to find argmin \|A-B\|p over all rank-$k$ matrices $B$, where \| · \|p is the entrywise ℓp norm. When $p = 2$ this well-studied problem is solved by the singular value decomposition, but for p ≠ 2 the problem becomes computationally challenging. For every even $p > 2$ and every fixed $k$, we give the first polynomial-time approximation scheme for this problem, improving on the (3 + ε) approximation of Ban, Bhattiprolu, Bringmann, Kolev, Lee, and Woodruff, the bi-criteria approximation of Woodruff and Yasuda, and the additive approximation scheme of Anderson, Bakshi, and Hopkins. Prior algorithmic approaches based on sketching and column selection, which yielded a polynomial-time approximation scheme in the $p 2$. Instead, we use the Sherali-Adams hierarchy of convex programs, and in so doing establish a blueprint for how to use convex hierarchies to design polynomial-time approximation schemes for continuous optimization problems. We use the same algorithmic strategy to give a new family of additive approximation algorithms for matrix p → q norms, which are intimately related to small-set expansion and quantum information. In particular, we give the first nontrivial additive approximation algorithms in the regime $p < 2 < q$.

Abstract. We consider the question of Gaussian mean testing, a fundamental task in high-dimensional distribution testing and signal processing, subject to adversarial corruptions of the samples. We focus on the relative power of different adversaries and show that, in contrast to the common wisdom in robust statistics, there exists a strict separation between adaptive adversaries (strong contamination) and oblivious ones (weak contamination) for this task. Specifically, we resolve both the information-theoretic and computational landscapes for robust mean testing. In the exponential-time setting, we establish the tight sample complexity of testing [Formula: see text] against [Formula: see text], where [Formula: see text], with an [Formula: see text]-fraction of oblivious adversarial corruptions, to be [Formula: see text], while the complexity against adaptive adversarial corruptions is [Formula: see text], which is strictly worse for a large range of vanishing [Formula: see text]. To the best of our knowledge, ours is the first separation in sample complexity between the strong and weak contamination models. In the polynomial-time setting, we close a gap in the literature by providing a polynomial-time algorithm against adaptive adversaries achieving the above sample complexity [Formula: see text], and a low-degree lower bound (which complements an existing reduction from planted clique) suggesting that all efficient algorithms require this many samples, even in the oblivious-adversary setting.

We investigate a classical formulation of the Quantum Approximate Optimization Algorithm (QAOA), realized as a Hamiltonian dynamical system of classical kicked tops, which we call the Variational Iterative Rotation Algorithm (VIRAL). The variational parameters are the transverse and longitudinal rotation angles at each of the p layers of the circuit. We find that VIRAL outperforms QAOA on the canonical Sherrington-Kirkpatrick spin-glass benchmark at all circuit depths, with the energy density converging to the ground state value linearly in 1/p. For large circuit depths, the optimized dynamics follows a Floquet protocol in which a pitchfork bifurcation destabilizes the equatorial fixed point and drives the spins toward polar Ising configurations. Our results demonstrate that the effectiveness of QAOA-like protocols derives primarily from their underlying iterative rotation structure, and that a classical implementation of it outperforms its quantum counterpart. We further elucidate its efficiency by reducing the many-body classical evolution to an effective Landau-Lifshitz dynamics for a single spin in a stochastic magnetic field. In this picture, the covariance matrix of the effective field reveals a nearly rank-one structure in which a single mode dominates the stochastic dynamics. In contrast, quantum fluctuations make the noise covariance of the effective quantum model of higher rank, hampering the control of the system. We propose nanometer-scale magnetic tunnel junctions as a natural physical platform for implementing VIRAL, where spin rotations can be realized using magnetic fields and spin torques.

We propose a novel floating-point encoding scheme that builds on prior work involving fixed-point encodings. We encode floating-point numbers using Two's Complement fixed-point mantissas and Two's Complement integral exponents. We used our proposed approach to develop quantum algorithms for fundamental arithmetic operations, such as bit-shifting, reciprocation, multiplication, and addition. We prototyped and investigated the performance of the floating-point encoding scheme on quantum computer simulations by performing reciprocation on randomly drawn inputs and by solving first-order ordinary differential equations, while varying the number of qubits in the encoding. We observed rapid convergence to the exact solutions as we increased the number of qubits and a significant reduction in the number of ancilla qubits required for reciprocation when compared with similar approaches.

The modern theory of functional programming languages uses monads for encoding computational side-effects and side-contexts, beyond bare-bone program logic. Even though quantum computing is intrinsically side-effectful (as in quantum measurement) and context-dependent (as on mixed ancillary states), little of this monadic paradigm has previously been brought to bear on quantum programming languages. Here, we systematically analyze the (co)monads on categories of parameterized module spectra which are induced by Grothendieck’s “motivic yoga of operations”—for the present purpose specialized to HC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}HC\end{document}-modules and further to set-indexed complex vector spaces, as discussed in a companion article (Sati and Schreiber in Entanglement of sections. arXiv:2309.07245). Interpreting an indexed vector space as a collection of alternative possible quantum state spaces parameterized by quantum measurement results, as familiar from Proto- -semantics, we find that these (co)monads provide a comprehensive natural language for functional quantum programming with classical control and with “dynamic lifting” of quantum measurement results back into classical contexts. We close by indicating a domain-specific quantum programming language () expressing these monadic quantum effects in transparent do-notation, embeddable into the recently constructed Linear Homotopy Type Theory () which interprets into parameterized module spectra. Once embedded into, this should make for formally verifiable universal quantum programming with linear quantum types, classical control, dynamic lifting, and notably also with topological effects (as discussed in the companion article Myers et al. in Commun Math Phys 405:172, 2024).

We consider the task of privately obtaining prediction error guarantees in ordinary least-squares regression problems with Gaussian covariates (with unknown covariance structure). We provide the first sample-optimal polynomial time algorithm for this task under both pure and approximate differential privacy. We show that any improvement to the sample complexity of our algorithm would violate either statistical-query or information-theoretic lower bounds. Additionally, our algorithm is robust to a small fraction of arbitrary outliers and achieves optimal error rates as a function of the fraction of outliers. In contrast, all prior efficient algorithms either incurred sample complexities with sub-optimal dimension dependence, scaling with the condition number of the covariates, or obtained a polynomially worse dependence on the privacy parameters. Our technical contributions are two-fold: first, we leverage resilience guarantees of Gaussians within the sum-of-squares framework. As a consequence, we obtain efficient sum-of-squares algorithms for regression with optimal robustness rates and sample complexity. Second, we generalize the recent robustness-to-privacy framework [HKMN23, (arXiv:2212.05015)] to account for the geometry induced by the covariance of the input samples. This framework crucially relies on the robust estimators to be sum-of-squares algorithms, and combining the two steps yields a sample-optimal private regression algorithm. We believe our techniques are of independent interest, and we demonstrate this by obtaining an efficient algorithm for covariance-aware mean estimation, with an optimal dependence on the privacy parameters.

In the trace reconstruction problem our goal is to learn an unknown string x∈ 0,1ⁿ given independent traces of $x$. A trace is obtained by independently deleting each bit of $x$ with some probability $δ$ and concatenating the remaining bits. It is a major open question whether the trace reconstruction problem can be solved with a polynomial number of traces when the deletion probability $δ$ is constant. The best known upper bound and lower bounds are respectively (O(n1/5)) and Ω(n3/2) both by Chase [Cha21b,Cha21a]. Our main result is that if the string $x$ is mildly separated, meaning that the number of zeros between any two ones in $x$ is at least polylog$n$, and if $δ$ is a sufficiently small constant, then the trace reconstruction problem can be solved with O(n n) traces and in polynomial time.

TeNPy (short for ‘Tensor Network Python’) is a python library for the simulation of strongly correlated quantum systems with tensor networks. The philosophy of this library is to achieve a balance of readability and usability for new-comers, while at the same time providing powerful algorithms for experts. The focus is on MPS algorithms for 1D and 2D lattices, such as DMRG ground state search, as well as dynamics using TEBD, TDVP, or MPO evolution. This article is a companion to the recent version 1.0 release of TeNPy and gives a brief overview of the package.

Model stealing, where a learner tries to recover an unknown model via carefully chosen queries, is a critical problem in machine learning, as it threatens the security of proprietary models and the privacy of data they are trained on. In recent years, there has been particular interest in stealing large language models (LLMs). In this paper, we aim to build a theoretical understanding of stealing language models by studying a simple and mathematically tractable setting. We study model stealing for Hidden Markov Models (HMMs), and more generally low-rank language models. We assume that the learner works in the conditional query model, introduced by Kakade, Krishnamurthy, Mahajan and Zhang. Our main result is an efficient algorithm in the conditional query model, for learning any low-rank distribution. In other words, our algorithm succeeds at stealing any language model whose output distribution is low-rank. This improves upon the previous result by Kakade, Krishnamurthy, Mahajan and Zhang, which also requires the unknown distribution to have high "fidelity", a property that holds only in restricted cases. There are two key insights behind our algorithm: First, we represent the conditional distributions at each timestep by constructing barycentric spanners among a collection of vectors of exponentially large dimension. Second, for sampling from our representation, we iteratively solve a sequence of convex optimization problems that involve projection in relative entropy to prevent compounding of errors over the length of the sequence. This is an interesting example where, at least theoretically, allowing a machine learning model to solve more complex problems at inference time can lead to drastic improvements in its performance.

The existence of pseudorandom unitaries (PRUs) -- efficient quantum circuits that are computationally indistinguishable from Haar-random unitaries -- has been a central open question, with significant implications for cryptography, complexity theory, and fundamental physics. In this work, we close this question by proving that PRUs exist, assuming that any quantum-secure one-way function exists. We establish this result for both (1) the standard notion of PRUs, which are secure against any efficient adversary that makes queries to the unitary $U$, and (2) a stronger notion of PRUs, which are secure even against adversaries that can query both the unitary $U$ and its inverse U. In the process, we prove that any algorithm that makes queries to a Haar-random unitary can be efficiently simulated on a quantum computer, up to inverse-exponential trace distance.

Characterizing strongly correlated matter is an increasingly central challenge in quantum science, where structure is often obscured by massive entanglement. It is becoming clear that in the quantum regime, state preparation and characterization should not be treated separately-entangling the two processes provides a quantum advantage in information extraction. Here, we present an approach that we term "manybody Ramsey interferometry" that combines adiabatic state preparation and Ramsey spectroscopy: Leveraging our recently developed one-to-one mapping between computational-basis states and manybody eigenstates, we prepare a superposition of manybody eigenstates controlled by the state of an ancilla qubit, allow the superposition to evolve relative phase, and then reverse the preparation protocol to disentangle the ancilla while localizing phase information back into it. Ancilla tomography then extracts information about the manybody eigenstates, the associated excitation spectrum, and thermodynamic observables. This work illustrates the potential for using quantum computers to efficiently probe quantum matter.

Random reversible and quantum circuits form random walks on the alternating group Alt(2ⁿ) and unitary group SU(2ⁿ), respectively. Known 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⁻³) for all t≥ 1, and the gap for random quantum circuits is Ω(n⁻³) for t ≤ Θ(2n/2). These gaps are independent of $t$ in the respective regimes. We can further improve both gaps to n⁻¹/polylog(n, t) for t≤ 2Θ(n), which is tight up to polylog factors. Our spectral gap results have a number of consequences: 1) Random reversible circuits with O(n⁴ t) gates form multiplicative-error $t$-wise independent (even) permutations for all t≥ 1; for t ≤ Θ(2n/6.1), we show that O(n² t) gates suffice. 2) Random quantum circuits with O(n⁴ t) gates form multiplicative-error unitary $t$-designs for t ≤ Θ(2n/2); for t≤ Θ(22n/5), we show that O(n²t) gates suffice. 3) The robust quantum circuit complexity of random circuits grows linearly for an exponentially long time, proving the robust Brown--Susskind conjecture [BS18,BCHJ+21]. Our spectral gap bounds are proven by reducing random quantum circuits to a more structured walk: a modification of the ``PFC ensemble'' from [MPSY24] together with an expander on the alternating group due to Kassabov [Kas07a], 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.

A set of high dimensional points X=x1, x2,…, xn ⊂ Rd in isotropic position is said to be $δ$-anti concentrated if for every direction $v$, the fraction of points in $X$ satisfying |⟨ xi,v ⟩ |≤ δ is at most $O(δ)$. Motivated by applications to list-decodable learning and clustering, recent works have considered the problem of constructing efficient certificates of anti-concentration in the average case, when the set of points $X$ corresponds to samples from a Gaussian distribution. Their certificates played a crucial role in several subsequent works in algorithmic robust statistics on list-decodable learning and settling the robust learnability of arbitrary Gaussian mixtures, yet remain limited to rotationally invariant distributions. This work presents a new (and arguably the most natural) formulation for anti-concentration. Using this formulation, we give quasi-polynomial time verifiable sum-of-squares certificates of anti-concentration that hold for a wide class of non-Gaussian distributions including anti-concentrated bounded product distributions and uniform distributions over Lp balls (and their affine transformations). Consequently, our method upgrades and extends results in algorithmic robust statistics e.g., list-decodable learning and clustering, to such distributions. Our approach constructs a canonical integer program for anti-concentration and analysis a sum-of-squares relaxation of it, independent of the intended application. We rely on duality and analyze a pseudo-expectation on large subsets of the input points that take a small value in some direction. Our analysis uses the method of polynomial reweightings to reduce the problem to analyzing only analytically dense or sparse directions.

We study the problem of Hamiltonian structure learning from real-time evolution: given the ability to apply e-i Ht for an unknown local Hamiltonian H = ∑a = 1m λa Ea on $n$ qubits, the goal is to recover $H$. This problem is already well-understood under the assumption that the interaction terms, Ea, are given, and only the interaction strengths, λa, are unknown. But how efficiently can we learn a local Hamiltonian without prior knowledge of its interaction structure? We present a new, general approach to Hamiltonian learning that not only solves the challenging structure learning variant, but also resolves other open questions in the area, all while achieving the gold standard of Heisenberg-limited scaling. In particular, our algorithm recovers the Hamiltonian to ε error with total evolution time O((n)/ε), and has the following appealing properties: (1) it does not need to know the Hamiltonian terms; (2) it works beyond the short-range setting, extending to any Hamiltonian $H$ where the sum of terms interacting with a qubit has bounded norm; (3) it evolves according to $H$ in constant time $t$ increments, thus achieving constant time resolution. As an application, we can also learn Hamiltonians exhibiting power-law decay up to accuracy ε with total evolution time beating the standard limit of 1/ε².

We show that thermal states of local Hamiltonians are separable above a constant temperature. Specifically, for a local Hamiltonian $H$ on a graph with degree d, its Gibbs state at inverse temperature $β$, denoted by ρ= e-βH/ tr(e-βH), is a classical distribution over product states for all β< 1/(cd), where $c$ is a constant. This proof of sudden death of thermal entanglement resolves the fundamental question of whether many-body systems can exhibit entanglement at high temperature. Moreover, we show that we can efficiently sample from the distribution over product states. In particular, for any β< 1/(c d²), we can prepare a state ε-close to $ρ$ in trace distance with a depth-one quantum circuit and poly(n, 1/ε) classical overhead.

There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between looks like. In this work, we study tomography in the natural setting where one can make measurements of $t$ copies at a time. For sufficiently small $ε$, we show that for any t ≤ d², Θ(d³tε²) copies are necessary and sufficient to learn an unknown $d$-dimensional state $ρ$ to trace distance $ε$. This gives a smooth and optimal interpolation between the known rates for single-copy and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at $t = 2$. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently biased and thus precludes naive batching approaches. Instead, we devise a novel two-stage procedure that uses Keyl's algorithm to refine a crude estimate for $ρ$ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of $ρ$, but to estimate the deviation of $ρ$ from the maximally mixed state. When $ρ$ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where $ρ$ is close to maximally mixed.

We consider the problem of clustering mixtures of mean-separated Gaussians in high dimensions. We are given samples from a mixture of $k$ identity covariance Gaussians, so that the minimum pairwise distance between any two pairs of means is at least $Δ$, for some parameter $Δ> 0$, and the goal is to recover the ground truth clustering of these samples. It is folklore that separation Δ= Θ(k) is both necessary and sufficient to recover a good clustering, at least information theoretically. However, the estimators which achieve this guarantee are inefficient. We give the first algorithm which runs in polynomial time, and which almost matches this guarantee. More precisely, we give an algorithm which takes polynomially many samples and time, and which can successfully recover a good clustering, so long as the separation is Δ= Ω(1/2 + c k), for any $c > 0$. Previously, polynomial time algorithms were only known for this problem when the separation was polynomial in $k$, and all algorithms which could tolerate poly(k) separation required quasipolynomial time. We also extend our result to mixtures of translations of a distribution which satisfies the Poincaré inequality, under additional mild assumptions. Our main technical tool, which we believe is of independent interest, is a novel way to implicitly represent and estimate high degree moments of a distribution, which allows us to extract important information about high-degree moments without ever writing down the full moment tensors explicitly.

Metric embeddings are a widely used method in algorithm design, where generally a ``complex'' metric is embedded into a simpler, lower-dimensional one. Historically, the theoretical computer science community has focused on bi-Lipschitz embeddings, which guarantee that every pairwise distance is approximately preserved. In contrast, alternative embedding objectives that are commonly used in practice avoid bi-Lipschitz distortion; yet these approaches have received comparatively less study in theory. In this paper, we focus on Multi-dimensional Scaling (MDS), where we are given a set of non-negative dissimilarities di,ji,j∈ [n] over $n$ points, and the goal is to find an embedding x1,…,xn ⊂ Rk that minimizes OPT=,j∈ [n](1-\|xi - xj\|di,j)². Despite its popularity, our theoretical understanding of MDS is extremely limited. Recently, Demaine et. al. (arXiv:2109.11505) gave the first approximation algorithm with provable guarantees for this objective, which achieves an embedding in constant dimensional Euclidean space with cost OPT +ε in n²· 2poly(Δ/ε) time, where $Δ$ is the aspect ratio of the input dissimilarities. For metrics that admit low-cost embeddings, $Δ$ scales polynomially in $n$. In this work, we give the first approximation algorithm for MDS with quasi-polynomial dependency on $Δ$: for constant dimensional Euclidean space, we achieve a solution with cost O(Δ)· OPTΩ(1)+ε in time nO(1) · 2poly(((Δ)/ε)). Our algorithms are based on a novel geometry-aware analysis of a conditional rounding of the Sherali-Adams LP Hierarchy, allowing us to avoid exponential dependency on the aspect ratio, which would typically result from this rounding.

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 study the problem of learning a local quantum Hamiltonian $H$ given copies of its Gibbs state ρ= e-βH/tr(e-βH) at a known inverse temperature $β>0$. Anshu, Arunachalam, Kuwahara, and Soleimanifar (arXiv:2004.07266) gave an algorithm to learn a Hamiltonian on $n$ qubits to precision $ε$ with only polynomially many copies of the Gibbs state, but which takes exponential time. Obtaining a computationally efficient algorithm has been a major open problem [Alhambra'22 (arXiv:2204.08349)], [Anshu, Arunachalam'22 (arXiv:2204.08349)], with prior work only resolving this in the limited cases of high temperature [Haah, Kothari, Tang'21 (arXiv:2108.04842)] or commuting terms [Anshu, Arunachalam, Kuwahara, Soleimanifar'21]. We fully resolve this problem, giving a polynomial time algorithm for learning $H$ to precision $ε$ from polynomially many copies of the Gibbs state at any constant $β> 0$. Our main technical contribution is a new flat polynomial approximation to the exponential function, and a translation between multi-variate scalar polynomials and nested commutators. This enables us to formulate Hamiltonian learning as a polynomial system. We then show that solving a low-degree sum-of-squares relaxation of this polynomial system suffices to accurately learn the Hamiltonian.

Individual preference (IP) stability, introduced by Ahmadi et al. (ICML 2022), is a natural clustering objective inspired by stability and fairness constraints. A clustering is $α$-IP stable if the average distance of every data point to its own cluster is at most $α$ times the average distance to any other cluster. Unfortunately, determining if a dataset admits a $1$-IP stable clustering is NP-Hard. Moreover, before this work, it was unknown if an $o(n)$-IP stable clustering always \emph{exists}, as the prior state of the art only guaranteed an $O(n)$-IP stable clustering. We close this gap in understanding and show that an $O(1)$-IP stable clustering always exists for general metrics, and we give an efficient algorithm which outputs such a clustering. We also introduce generalizations of IP stability beyond average distance and give efficient, near-optimal algorithms in the cases where we consider the maximum and minimum distances within and between clusters.

Recently Chen and Poor initiated the study of learning mixtures of linear dynamical systems. While linear dynamical systems already have wide-ranging applications in modeling time-series data, using mixture models can lead to a better fit or even a richer understanding of underlying subpopulations represented in the data. In this work we give a new approach to learning mixtures of linear dynamical systems that is based on tensor decompositions. As a result, our algorithm succeeds without strong separation conditions on the components, and can be used to compete with the Bayes optimal clustering of the trajectories. Moreover our algorithm works in the challenging partially-observed setting. Our starting point is the simple but powerful observation that the classic Ho-Kalman algorithm is a close relative of modern tensor decomposition methods for learning latent variable models. This gives us a playbook for how to extend it to work with more complicated generative models.

For any two point sets A,B ⊂ Rd of size up to $n$, the Chamfer distance from $A$ to $B$ is defined as CH(A,B)=∑a ∈ A ∈ B dX(a,b), where dX is the underlying distance measure (e.g., the Euclidean or Manhattan distance). The Chamfer distance is a popular measure of dissimilarity between point clouds, used in many machine learning, computer vision, and graphics applications, and admits a straightforward O(d n²)-time brute force algorithm. Further, the Chamfer distance is often used as a proxy for the more computationally demanding Earth-Mover (Optimal Transport) Distance. However, the \emph{quadratic} dependence on $n$ in the running time makes the naive approach intractable for large datasets. We overcome this bottleneck and present the first $(1+ε)$-approximate algorithm for estimating the Chamfer distance with a near-linear running time. Specifically, our algorithm runs in time O(nd (n)/ε²) and is implementable. Our experiments demonstrate that it is both accurate and fast on large high-dimensional datasets. We believe that our algorithm will open new avenues for analyzing large high-dimensional point clouds. We also give evidence that if the goal is to \emph{report} a (1+ε)-approximate mapping from $A$ to $B$ (as opposed to just its value), then any sub-quadratic time algorithm is unlikely to exist.

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.

We prove concentration bounds for the following classes of quantum states: (i) output states of shallow quantum circuits, answering an open question from \cite{DMRF22}; (ii) injective matrix product states; (iii) output states of dense Hamiltonian evolution, i.e. states of the form eιH(p)⋯eιH(1)|ψ0⟩ for any n-qubit product state |ψ0⟩, 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].

We consider the problem of rank-$1$ low-rank approximation (LRA) in the matrix-vector product model under various Schatten norms: \|u\|2=1 \|A (I - u u)\|Sp, where \|M\|Sp denotes the ℓp norm of the singular values of $M$. Given ε>0, our goal is to output a unit vector $v$ such that \|A(I - vv)\|Sp ≤ (1+ε) \|u\|2=1\|A(I - u u)\|Sp. Our main result shows that Krylov methods (nearly) achieve the information-theoretically optimal number of matrix-vector products for Spectral (p=∞), Frobenius ($p=2$) and Nuclear ($p=1$) LRA. In particular, for Spectral LRA, we show that any algorithm requires Ω((n)/ε1/2) matrix-vector products, exactly matching the upper bound obtained by Krylov methods [MM15, BCW22]. Our lower bound addresses Open Question 1 in [Woo14], providing evidence for the lack of progress on algorithms for Spectral LRA and resolves Open Question 1.2 in [BCW22]. Next, we show that for any fixed constant $p$, i.e. 1≤ p =O(1), there is an upper bound of O((1/ε)/ε1/3) matrix-vector products, implying that the complexity does not grow as a function of input size. This improves the O((n/ε)/ε1/3) bound recently obtained in [BCW22], and matches their Ω(1/ε1/3) lower bound, to a (1/ε) factor.

We study quantum speedups in quantum machine learning (QML) by analyzing the quantum singular value transformation (QSVT) framework. QSVT, introduced by [GSLW, STOC'19, arXiv:1806.01838], unifies all major types of quantum speedup; in particular, a wide variety of QML proposals are applications of QSVT on low-rank classical data. We challenge these proposals by providing a classical algorithm that matches the performance of QSVT in this regime up to a small polynomial overhead. We show that, given a matrix A ∈ Cm× n, a vector b ∈ Cⁿ, a bounded degree-$d$ polynomial $p$, and linear-time pre-processing, we can output a description of a vector $v$ such that \|v - p(A) b\| ≤ ε\|b\| in O(d¹¹ \|A\|F⁴ / (ε² \|A\|⁴)) time. This improves upon the best known classical algorithm [CGLLTW, STOC'20, arXiv:1910.06151], which requires O(d²² \|A\|F⁶ /(ε⁶ \|A\|⁶)) time, and narrows the gap with QSVT, which, after linear-time pre-processing to load input into a quantum-accessible memory, can estimate the magnitude of an entry $p(A)b$ to ε\|b\| error in O(d\|A\|F/(ε \|A\|)) time. Our key insight is to combine the Clenshaw recurrence, an iterative method for computing matrix polynomials, with sketching techniques to simulate QSVT classically. We introduce several new classical techniques in this work, including (a) a non-oblivious matrix sketch for approximately preserving bi-linear forms, (b) a new stability analysis for the Clenshaw recurrence, and (c) a new technique to bound arithmetic progressions of the coefficients appearing in the Chebyshev series expansion of bounded functions, each of which may be of independent interest.

This work represents a natural coalescence of two important lines of work — learning mixtures of Gaussians and algorithmic robust statistics. In particular, we give the first provably robust algorithm for learning mixtures of any constant number of Gaussians. We require only mild assumptions on the mixing weights and that the total variation distance between components is bounded away from zero. At the heart of our algorithm is a new method for proving a type of dimension-independent polynomial identifiability — which we call robust identifiability — through applying a carefully chosen sequence of differential operations to certain generating functions that not only encode the parameters we would like to learn but also the system of polynomial equations we would like to solve. We show how the symbolic identities we derive can be directly used to analyze a natural sum-of-squares relaxation.

Linear dynamical systems are the foundational statistical model upon which control theory is built. Both the celebrated Kalman filter and the linear quadratic regulator require knowledge of the system dynamics to provide analytic guarantees. Naturally, learning the dynamics of a linear dynamical system from linear measurements has been intensively studied since Rudolph Kalman's pioneering work in the 1960's. Towards these ends, we provide the first polynomial time algorithm for learning a linear dynamical system from a polynomial length trajectory up to polynomial error in the system parameters under essentially minimal assumptions: observability, controllability, and marginal stability. Our algorithm is built on a method of moments estimator to directly estimate Markov parameters from which the dynamics can be extracted. Furthermore, we provide statistical lower bounds when our observability and controllability assumptions are violated.

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 polynomial-time 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 stateQIP. Our main result is the reverse inclusion, stateQIP 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 block-encoding 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.

As progress is made towards the first generation of error-corrected quantum computers, robust characterization and validation protocols are required to assess the noise environments of physical quantum processors. While standard coherence metrics and characterization protocols such as T1 and T2, process tomography, and randomized benchmarking are now ubiquitous, these techniques provide only partial information about the dynamic multiqubit loss channels responsible for processor errors, which can be described more fully by a Lindblad operator in the master equation formalism. Here, we introduce and experimentally demonstrate Lindblad tomography, a hardware-agnostic characterization protocol for tomographically reconstructing the Hamiltonian and Lindblad operators of a quantum noise environment from an ensemble of time-domain measurements. Performing Lindblad tomography on a small superconducting quantum processor, we show that this technique naturally builds on standard process tomography and T1/T2 measurement protocols, characterizes and accounts for state-preparation and measurement errors, and allows one to place bounds on the fit to a Markovian model. Comparing the results of single- and two-qubit measurements on a superconducting quantum processor, we demonstrate that Lindblad tomography can also be used to identify and quantify sources of crosstalk on quantum processors, such as the presence of always-on qubit-qubit interactions.

Guiding many-body systems to desired states is a central challenge of modern quantum science, with applications from quantum computation1,2 to many-body physics3 and quantum-enhanced metrology4. Approaches to solving this problem include step-by-step assembly5,6, reservoir engineering to irreversibly pump towards a target state7,8 and adiabatic evolution from a known initial state9,10. Here we construct low-entropy quantum fluids of light in a Bose-Hubbard circuit by combining particle-by-particle assembly and adiabatic preparation. We inject individual photons into a disordered lattice for which the eigenstates are known and localized, then adiabatically remove this disorder, enabling quantum fluctuations to melt the photons into a fluid. Using our platform11, we first benchmark this lattice melting technique by building and characterizing arbitrary single-particle-in-a-box states, then assemble multiparticle strongly correlated fluids. Intersite entanglement measurements performed through single-site tomography indicate that the particles in the fluid delocalize, whereas two-body density correlation measurements demonstrate that they also avoid one another, revealing Friedel oscillations characteristic of a Tonks-Girardeau gas12,13. This work opens new possibilities for the preparation of topological and otherwise exotic phases of synthetic matter3,14,15.

Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency -- given $n$ input points, most kernel-based algorithms need to materialize the full n × n kernel matrix before performing any subsequent computation, thus incurring Ω(n²) runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain subquadratic time algorithms for several fundamental linear-algebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving linear systems, local clustering, low-rank approximation, arboricity estimation and counting weighted triangles. We build on the recent Kernel Density Estimation framework, which (after preprocessing in time subquadratic in $n$) can return estimates of row/column sums of the kernel matrix. In particular, we develop efficient reductions from weighted vertex and weighted edge sampling on kernel graphs, simulating random walks on kernel graphs, and importance sampling on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in sublinear (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on low-rank approximation (LRA) and spectral sparsification, where we observe a 9x decrease in the number of kernel evaluations over baselines for LRA and a 41x reduction in the graph size for spectral sparsification.

While the realization of scalable quantum computation will arguably require topological stabilization and, with it, topological-hardware-aware quantum programming and topological-quantum circuit verification, the proper combination of these strategies into dedicated topological quantum programming languages has not yet received attention. Here we describe a fundamental and natural scheme that we are developing, for typed functional (hence verifiable) topological quantum programming which is topological-hardware aware -- in that it natively reflects the universal fine technical detail of topological q-bits, namely of symmetry-protected (or enhanced) topologically ordered Laughlin-type anyon ground states in topological phases of quantum materials. What makes this work is: (1) our recent result that wavefunctions of realistic and technologically viable anyon species -- namely of su(2)-anyons such as the popular Majorana/Ising anyons but also of computationally universal Fibonacci anyons -- are reflected in the twisted equivariant differential (TED) K-cohomology of configuration spaces of codimension=2 nodal defects in the host material's crystallographic orbifold; (2) combined with our earlier observation that such TED generalized cohomology theories on orbifolds interpret intuitionistically-dependent linear data types in cohesive homotopy type theory (HoTT), supporting a powerful modern form of modal quantum logic. In this short note we give an exposition of the basic ideas, a quick review of the underlying results and a brief indication of the basic language constructs for anyon braiding via TED-K in cohesive HoTT. The language system is under development at the "Center for Quantum and Topological Systems" at the Research Institute of NYU, Abu Dhabi.

In this work, we study the problem of community detection in the stochastic block model with adversarial node corruptions. Our main result is an efficient algorithm that can tolerate an $ε$-fraction of corruptions and achieves error O(ε) + e-C2 (1 ± o(1)) where C = (a - b)² is the signal-to-noise ratio and $a/n$ and $b/n$ are the inter-community and intra-community connection probabilities respectively. These bounds essentially match the minimax rates for the SBM without corruptions. We also give robust algorithms for Z2-synchronization. At the heart of our algorithm is a new semidefinite program that uses global information to robustly boost the accuracy of a rough clustering. Moreover, we show that our algorithms are doubly-robust in the sense that they work in an even more challenging noise model that mixes adversarial corruptions with unbounded monotone changes, from the semi-random model.

We construct a classically verifiable succinct interactive argument for quantum computation (BQP) with communication complexity and verifier runtime that are poly-logarithmic in the runtime of the BQP computation (and polynomial in the security parameter). Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning with Errors (LWE). This is the first succinct argument for quantum computation in the plain model; prior work (Chia-Chung-Yamakawa, TCC '20) requires both a long common reference string and non-black-box use of a hash function modeled as a random oracle. At a technical level, we revisit the framework for constructing classically verifiable quantum computation (Mahadev, FOCS '18). We give a self-contained, modular proof of security for Mahadev's protocol, which we believe is of independent interest. Our proof readily generalizes to a setting in which the verifier's first message (which consists of many public keys) is compressed. Next, we formalize this notion of compressed public keys; we view the object as a generalization of constrained/programmable PRFs and instantiate it based on indistinguishability obfuscation. Finally, we compile the above protocol into a fully succinct argument using a (sufficiently composable) succinct argument of knowledge for NP. Using our framework, we achieve several additional results, including - Succinct arguments for QMA (given multiple copies of the witness), - Succinct non-interactive arguments for BQP (or QMA) in the quantum random oracle model, and - Succinct batch arguments for BQP (or QMA) assuming post-quantum LWE (without iO).

We consider the classic question of state tomography: given copies of an unknown quantum state ρ× d, output ρ which is close to $ρ$ in some sense, e.g. trace distance or fidelity. When one is allowed to make coherent measurements entangled across all copies, Θ(d²/ε²) copies are necessary and sufficient to get trace distance $ε$. Unfortunately, the protocols achieving this rate incur large quantum memory overheads that preclude implementation on near-term devices. On the other hand, the best known protocol using incoherent (single-copy) measurements uses O(d³/ε²) copies, and multiple papers have posed it as an open question to understand whether or not this rate is tight. In this work, we fully resolve this question, by showing that any protocol using incoherent measurements, even if they are chosen adaptively, requires Ω(d³/ε²) copies, matching the best known upper bound. We do so by a new proof technique which directly bounds the ``tilt'' of the posterior distribution after measurements, which yields a surprisingly short proof of our lower bound, and which we believe may be of independent interest. While this implies that adaptivity does not help for tomography with respect to trace distance, we show that it actually does help for tomography with respect to infidelity. We give an adaptive algorithm that outputs a state which is $γ$-close in infidelity to $ρ$ using only O(d³/γ) copies, which is optimal for incoherent measurements. In contrast, it is known that any nonadaptive algorithm requires Ω(d³/γ²) copies. While it is folklore that in $2$ dimensions, one can achieve a scaling of $O(1/γ)$, to the best of our knowledge, our algorithm is the first to achieve the optimal rate in all dimensions.

We consider the problem of quantum state certification, where we are given the description of a mixed state σ∈ Cd × d, $n$ copies of a mixed state ρ∈ Cd × d, and ε > 0, and we are asked to determine whether $ρ= σ$ or whether \| ρ- σ\|1 > ε. When $σ$ is the maximally mixed state 1d Id, this is known as mixedness testing. We focus on algorithms which use incoherent measurements, i.e. which only measure one copy of $ρ$ at a time. Unlike those that use entangled, multi-copy measurements, these can be implemented without persistent quantum memory and thus represent a large class of protocols that can be run on current or near-term devices. For mixedness testing, there is a folklore algorithm which uses incoherent measurements and only needs O(d3/2 / ε²) copies. The algorithm is non-adaptive, that is, its measurements are fixed ahead of time, and is known to be optimal for non-adaptive algorithms. However, when the algorithm can make arbitrary incoherent measurements, the best known lower bound is only Ω(d4/3 / ε²) [Bubeck-Chen-Li '20], and it has been an outstanding open problem to close this polynomial gap. In this work, 1) we settle the copy complexity of mixedness testing with incoherent measurements and show that Ω(d3/2 / ε²) copies are necessary, and 2) we show the instance-optimal bounds for state certification to general $σ$ first derived by [Chen-Li-O'Donnell '21] for non-adaptive measurements also hold for arbitrary incoherent measurements. Qualitatively, our results say that adaptivity does not help at all for these problems. Our results are based on new techniques that allow us to reduce the problem to understanding certain matrix martingales, which we believe may be of independent interest.

Proving superlogarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early '80s. We prove a polynomial (nΩ(1)) lower bound for an explicit range counting problem of n³ convex polygons in R² (each with nO(1) facets/semialgebraic complexity), against linear storage arithmetic data structures in the group model. Our construction and analysis are based on a combination of techniques in Diophantine approximation, pseudorandomness, and compressed sensing—in particular, on the existence and partial derandomization of optimal binary compressed sensing matrices in the polynomial sparsity regime (k = n1-δ). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.

We study the stochastic multi-player multi-armed bandit problem. In this problem, $m$ players cooperate to maximize their total reward from $K > m$ arms. However the players cannot communicate and are penalized (e.g. receive no reward) if they pull the same arm at the same time. We ask whether it is possible to obtain optimal instance-dependent regret O(1/Δ) where $Δ$ is the gap between the $m$-th and $m+1$-st best arms. Such guarantees were recently achieved in a model allowing the players to implicitly communicate through intentional collisions. Surprisingly, we show that with no communication at all, such guarantees are not achievable. In fact, obtaining the optimal O(1/Δ) regret for some values of $Δ$ necessarily implies strictly sub-optimal regret in other regimes. Our main result is a complete characterization of the Pareto optimal instance-dependent trade-offs that are possible with no communication. Our algorithm generalizes that of Bubeck, Budzinski, and the second author. As there, our algorithm succeeds even when feedback upon collision can be corrupted by an adaptive adversary, thanks to a strong no-collision property. Our lower bound is based on topological obstructions at multiple scales and is completely new.

We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Here, given access to a matrix $A$ through matrix-vector products, an accuracy parameter $ε$, and a target rank $k$, the goal is to find a rank-$k$ matrix $Z$ with orthonormal columns such that \| A(I-ZZ)\|Sp ≤ (1+ε) U = Ik \|A(I - U U)\|Sp, where \|M\|Sp denotes the ℓp norm of the the singular values of $M$. For the special cases of $p=2$ (Frobenius norm) and p = ∞ (Spectral norm), Musco and Musco (NeurIPS 2015) obtained an algorithm based on Krylov methods that uses O(k/ε) matrix-vector products, improving on the naïve O(k/ε) dependence obtainable by the power method, where O suppresses poly((dk/ε)) factors. Our main result is an algorithm that uses only O(kp1/6/ε1/3) matrix-vector products, and works for all p ≥ 1. For $p = 2$ our bound improves the previous O(k/ε1/2) bound to O(k/ε1/3). Since the Schatten-$p$ and Schatten-∞ norms are the same up to a $(1+ ε)$-factor when p ≥ (d)/ε, our bound recovers the result of Musco and Musco for p = ∞. Further, we prove a matrix-vector query lower bound of Ω(1/ε1/3) for any fixed constant p ≥ 1, showing that surprisingly Θ(1/ε1/3) is the optimal complexity for constant~$k$. To obtain our results, we introduce several new techniques, including optimizing over multiple Krylov subspaces simultaneously, and pinching inequalities for partitioned operators. Our lower bound for p ∈ [1,2] uses the Araki-Lieb-Thirring trace inequality, whereas for $p>2$, we appeal to a norm-compression inequality for aligned partitioned operators.

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.

In this work we study the orbit recovery problem over $SO(3)$, where the goal is to recover a band-limited function on the sphere from noisy measurements of randomly rotated copies of it. This is a natural abstraction for the problem of recovering the three-dimensional structure of a molecule through cryo-electron tomography. Symmetries play an important role: Recovering the function up to rotation is equivalent to solving a system of polynomial equations that comes from the invariant ring associated with the group action. Prior work investigated this system through computational algebra tools up to a certain size. However many statistical and algorithmic questions remain: How many moments suffice for recovery, or equivalently at what degree do the invariant polynomials generate the full invariant ring? And is it possible to algorithmically solve this system of polynomial equations? We revisit these problems from the perspective of smoothed analysis whereby we perturb the coefficients of the function in the basis of spherical harmonics. Our main result is a quasi-polynomial time algorithm for orbit recovery over $SO(3)$ in this model. We analyze a popular heuristic called frequency marching that exploits the layered structure of the system of polynomial equations by setting up a system of {\em linear} equations to solve for the higher-order frequencies assuming the lower-order ones have already been found. The main questions are: Do these systems have a unique solution? And how fast can the errors compound? Our main technical contribution is in bounding the condition number of these algebraically-structured linear systems. Thus smoothed analysis provides a compelling model in which we can expand the types of group actions we can handle in orbit recovery, beyond the finite and/or abelian case.

In learning theory, a standard assumption is that the data is generated from a finite mixture model. But what happens when the number of components is not known in advance? The problem of estimating the number of components, also called model selection, is important in its own right but there are essentially no known efficient algorithms with provable guarantees let alone ones that can tolerate adversarial corruptions. In this work, we study the problem of robust model selection for univariate Gaussian mixture models (GMMs). Given poly(k/ε) samples from a distribution that is $ε$-close in TV distance to a GMM with $k$ components, we can construct a GMM with O(k) components that approximates the distribution to within O(ε) in poly(k/ε) time. Thus we are able to approximately determine the minimum number of components needed to fit the distribution within a logarithmic factor. Prior to our work, the only known algorithms for learning arbitrary univariate GMMs either output significantly more than $k$ components (e.g. k/ε² components for kernel density estimates) or run in time exponential in $k$. Moreover, by adapting our techniques we obtain similar results for reconstructing Fourier-sparse signals.

In this work we study the orbit recovery problem, which is a natural abstraction for the problem of recovering a planted signal from noisy measurements under unknown group actions. Many important inverse problems in statistics, engineering and the sciences fit into this framework. Prior work has studied cases when the group is discrete and/or abelian. However fundamentally new techniques are needed in order to handle more complex group actions. Our main result is a quasi-polynomial time algorithm to solve orbit recovery over $SO(3)$ - i.e. the cryo-electron tomography problem which asks to recover the three-dimensional structure of a molecule from noisy measurements of randomly rotated copies of it. We analyze a variant of the frequency marching heuristic in the framework of smoothed analysis. Our approach exploits the layered structure of the invariant polynomials, and simultaneously yields a new class of tensor decomposition algorithms that work in settings when the tensor is not low-rank but rather where the factors are algebraically related to each other by a group action.

We consider the problem of learning a latent $k$-vertex simplex K, given access to A× n, which can be viewed as a data matrix with $n$ points that are obtained by randomly perturbing latent points in the simplex $K$ (potentially beyond $K$). A large class of latent variable models, such as adversarial clustering, mixed membership stochastic block models, and topic models can be cast as learning a latent simplex. Bhattacharyya and Kannan (SODA, 2020) give an algorithm for learning such a latent simplex in time roughly O(k(A)), where nnz(A) is the number of non-zeros in $A$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$, which holds in many of these applications. Further, we show this assumption is necessary, as otherwise an algorithm for learning a latent simplex would imply an algorithmic breakthrough for spectral low rank approximation. At a high level, Bhattacharyya and Kannan provide an adaptive algorithm that makes $k$ matrix-vector product queries to $A$ and each query is a function of all queries preceding it. Since each matrix-vector product requires nnz(A) time, their overall running time appears unavoidable. Instead, we obtain a low-rank approximation to $A$ in input-sparsity time and show that the column space thus obtained has small Θ (angular) distance to the right top-$k$ singular space of $A$. Our algorithm then selects $k$ points in the low-rank subspace with the largest inner product with $k$ carefully chosen random vectors. By working in the low-rank subspace, we avoid reading the entire matrix in each iteration and thus circumvent the Θ(k(A)) running time.

Numerous conceptually important quantum algorithms rely on a blackbox device known as an oracle, which is typically difficult to construct without knowing the answer to the problem that the algorithm is intended to solve.A notable example is Grover's search algorithm.Here we propose a Grover search for solutions to a class of NP-complete decision problems known as subset sum problems, including the special case of number partitioning.Each problem instance is encoded in the couplings of a set of qubits to a central spin or boson, which enables a realization of the oracle without knowledge of the solution.The algorithm provides a quantum speedup across a known phase transition in the computational complexity of the partition problem, and we identify signatures of the phase transition in the simulated performance.Whereas the naive implementation of our algorithm requires a spectral resolution that scales exponentially with system size for NP-complete problems, we also present a recursive algorithm that enables scalability.We propose and analyze implementation schemes with cold atoms, including Rydberg-atom and cavity-QED platforms.

In this work we solve the problem of robustly learning a high-dimensional Gaussian mixture model with $k$ components from $ε$-corrupted samples up to accuracy O(ε) in total variation distance for any constant $k$ and with mild assumptions on the mixture. This robustness guarantee is optimal up to polylogarithmic factors. The main challenge is that most earlier works rely on learning individual components in the mixture, but this is impossible in our setting, at least for the types of strong robustness guarantees we are aiming for. Instead we introduce a new framework which we call {\em strong observability} that gives us a route to circumvent this obstacle.

We give a polynomial-time algorithm for the problem of robustly estimating a mixture of $k$ arbitrary Gaussians in Rd, for any fixed $k$, in the presence of a constant fraction of arbitrary corruptions. This resolves the main open problem in several previous works on algorithmic robust statistics, which addressed the special cases of robustly estimating (a) a single Gaussian, (b) a mixture of TV-distance separated Gaussians, and (c) a uniform mixture of two Gaussians. Our main tools are an efficient \emph{partial clustering} algorithm that relies on the sum-of-squares method, and a novel \emph{tensor decomposition} algorithm that allows errors in both Frobenius norm and low-rank terms.

We construct the first constant-round protocols for secure quantum computation in the two-party (2PQC) and multi-party (MPQC) settings with security against malicious adversaries. Our protocols are in the common random string (CRS) model. - Assuming two-message oblivious transfer (OT), we obtain (i) three-message 2PQC, and (ii) five-round MPQC with only three rounds of online (input-dependent) communication; such OT is known from quantum-hard Learning with Errors (QLWE). - Assuming sub-exponential hardness of QLWE, we obtain (i) three-round 2PQC with two online rounds and (ii) four-round MPQC with two online rounds. - When only one (out of two) parties receives output, we achieve minimal interaction (two messages) from two-message OT; classically, such protocols are known as non-interactive secure computation (NISC), and our result constitutes the first maliciously-secure quantum NISC. Additionally assuming reusable malicious designated-verifier NIZK arguments for NP (MDV-NIZKs), we give the first MDV-NIZK for QMA that only requires one copy of the quantum witness. Finally, we perform a preliminary investigation into two-round secure quantum computation where each party must obtain output. On the negative side, we identify a broad class of simulation strategies that suffice for classical two-round secure computation that are unlikely to work in the quantum setting. Next, as a proof-of-concept, we show that two-round secure quantum computation exists with respect to a quantum oracle.

This work represents a natural coalescence of two important lines of work: learning mixtures of Gaussians and algorithmic robust statistics. In particular we give the first provably robust algorithm for learning mixtures of any constant number of Gaussians. We require only mild assumptions on the mixing weights (bounded fractionality) and that the total variation distance between components is bounded away from zero. At the heart of our algorithm is a new method for proving dimension-independent polynomial identifiability through applying a carefully chosen sequence of differential operations to certain generating functions that not only encode the parameters we would like to learn but also the system of polynomial equations we would like to solve. We show how the symbolic identities we derive can be directly used to analyze a natural sum-of-squares relaxation.

Tensor completion is a natural higher-order generalization of matrix completion where the goal is to recover a low-rank tensor from sparse observations of its entries. Existing algorithms are either heuristic without provable guarantees, based on solving large semidefinite programs which are impractical to run, or make strong assumptions such as requiring the factors to be nearly orthogonal. In this paper we introduce a new variant of alternating minimization, which in turn is inspired by understanding how the progress measures that guide convergence of alternating minimization in the matrix setting need to be adapted to the tensor setting. We show strong provable guarantees, including showing that our algorithm converges linearly to the true tensors even when the factors are highly correlated and can be implemented in nearly linear time. Moreover our algorithm is also highly practical and we show that we can complete third order tensors with a thousand dimensions from observing a tiny fraction of its entries. In contrast, and somewhat surprisingly, we show that the standard version of alternating minimization, without our new twist, can converge at a drastically slower rate in practice.

We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a polynomial-time quantum reduction from worst-case lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees to those of LWE. Alternatively, our result can also be seen as opening new avenues of (quantum) attacks on lattice problems. Our work resolves an open problem regarding the computational complexity of learning mixtures of Gaussians without separability assumptions (Diakonikolas 2016, Moitra 2018). As an additional motivation, (a slight variant of) CLWE was considered in the context of robust machine learning (Diakonikolas et al.~FOCS 2017), where hardness in the statistical query (SQ) model was shown; our work addresses the open question regarding its computational hardness (Bubeck et al.~ICML 2019).

We give the first outlier-robust efficient algorithm for clustering a mixture of $k$ statistically separated d-dimensional Gaussians (k-GMMs). Concretely, our algorithm takes input an $ε$-corrupted sample from a $k$-GMM and whp in dpoly(k/η) time, outputs an approximate clustering that misclassifies at most kO(k)(ε+η) fraction of the points whenever every pair of mixture components are separated by 1-(-poly(k/η)k) in total variation (TV) distance. Such a result was not previously known even for $k=2$. TV separation is the statistically weakest possible notion of separation and captures important special cases such as mixed linear regression and subspace clustering. Our main conceptual contribution is to distill simple analytic properties - (certifiable) hypercontractivity and bounded variance of degree 2 polynomials and anti-concentration of linear projections - that are necessary and sufficient for mixture models to be (efficiently) clusterable. As a consequence, our results extend to clustering mixtures of arbitrary affine transforms of the uniform distribution on the $d$-dimensional unit sphere. Even the information-theoretic clusterability of separated distributions satisfying these two analytic assumptions was not known prior to our work and is likely to be of independent interest. Our algorithms build on the recent sequence of works relying on certifiable anti-concentration first introduced in the works of Karmarkar, Klivans, and Kothari and Raghavendra, and Yau in 2019. Our techniques expand the sum-of-squares toolkit to show robust certifiability of TV-separated Gaussian clusters in data. This involves giving a low-degree sum-of-squares proof of statements that relate parameter (i.e. mean and covariances) distance to total variation distance by relying only on hypercontractivity and anti-concentration.

We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number of variables have a tractable structure that we refer to as (ε, δ)-smallness. Using this technique, we make progress on several outstanding problems in the area: - We show that, even in the case of non-identical distributions, it is possible to achieve (arbitrarily close to) the optimal approximation ratio of β≈ 0.745 as long as we are allowed to remove a small constant number of distributions. - We show that for frequent instances of prophet inequalities (where each distribution reoccurs some number of times), it is possible to achieve the optimal approximation ratio of $β$ (improving over the previous best-known bound of $0.738$). - We give a new, simpler proof of Kertz's optimal approximation guarantee of β≈ 0.745 for prophet inequalities with i.i.d. distributions. The proof is primal-dual and simultaneously produces upper and lower bounds. - Using this decomposition in combination with a novel convex programming formulation, we construct the first Efficient PTAS for the Optimal Ordering problem.

Recently, a class of tensor networks called isometric tensor network states (isoTNS) was proposed which generalizes the canonical form of matrix product states to tensor networks in higher dimensions. While this ansatz allows for efficient numerical computations, it remained unclear which phases admit an isoTNS representation. In this work, we show that two-dimensional string-net liquids, which represent a wide variety of topological phases including discrete gauge theories, admit an exact isoTNS representation. We further show that the isometric form can be preserved after applying a finite-depth local quantum circuit. Taken together, these results show that long-range entanglement by itself is not an obstruction to isoTNS representation and suggest that all two-dimensional gapped phases with gappable edges admit an isoTNS representation.

In list-decodable subspace recovery, the input is a collection of $n$ points $αn$ (for some α≪ 1/2) of which are drawn i.i.d. from a distribution D with a isotropic rank $r$ covariance Π* (the \emph{inliers}) and the rest are arbitrary, potential adversarial outliers. The goal is to recover a $O(1/α)$ size list of candidate covariances that contains a Π close to Π*. Two recent independent works (Raghavendra-Yau, Bakshi-Kothari 2020) gave the first efficient algorithm for this problem. These results, however, obtain an error that grows with the dimension (linearly in [RY] and logarithmically in BK) at the cost of quasi-polynomial running time) and rely on \emph{certifiable anti-concentration} - a relatively strict condition satisfied essentially only by the Gaussian distribution. In this work, we improve on these results on all three fronts: \emph{dimension-independent} error via a faster fixed-polynomial running time under less restrictive distributional assumptions. Specifically, we give a poly(1/α) dO(1) time algorithm that outputs a list containing a Π satisfying \|Π -Π*\|F ≤ O(1/α). Our result only needs D to have \emph{certifiably hypercontractive} degree 2 polynomials. As a result, in addition to Gaussians, our algorithm applies to the uniform distribution on the hypercube and $q$-ary cubes and arbitrary product distributions with subgaussian marginals. Prior work (Raghavendra and Yau, 2020) had identified such distributions as potential hard examples as such distributions do not exhibit strong enough anti-concentration. When D satisfies certifiable anti-concentration, we obtain a stronger error guarantee of \|Π-Π*\|F ≤ η for any arbitrary $η> 0$ in dO(poly(1/α) + (1/η)) time.

Copyright © 2020 by Annual Reviews. All rights reserved. Superconducting qubits are leading candidates in the race to build a quantum computer capable of realizing computations beyond the reach of modern supercomputers. The superconducting qubit modality has been used to demonstrate prototype algorithms in the noisy intermediate-scale quantum (NISQ) technology era, in which non-error-corrected qubits are used to implement quantum simulations and quantum algorithms. With the recent demonstrations of multiple high-fidelity, two-qubit gates as well as operations on logical qubits in extensible superconducting qubit systems, this modality also holds promise for the longer-term goal of building larger-scale error-corrected quantum computers. In this brief review, we discuss several of the recent experimental advances in qubit hardware, gate implementations, readout capabilities, early NISQ algorithm implementations, and quantum error correction using superconducting qubits. Although continued work on many aspects of this technology is certainly necessary, the pace of both conceptual and technical progress in recent years has been impressive, and here we hope to convey the excitement stemming from this progress.

We study the Maximum Independent Set problem for geometric objects given in the data stream model. A set of geometric objects is said to be independent if the objects are pairwise disjoint. We consider geometric objects in one and two dimensions, i.e., intervals and disks. Let α be the cardinality of the largest independent set. Our goal is to estimate α in a small amount of space, given that the input is received as a one-pass stream. We also consider a generalization of this problem by assigning weights to each object and estimating β, the largest value of a weighted independent set. We initialize the study of this problem in the turnstile streaming model (insertions and deletions) and provide the first algorithms for estimating α and β. For unit-length intervals, we obtain a (2+ε)-approximation to α and β in poly(log(n)/ε) space. We also show a matching lower bound. Combined with the 3/2-approximation for insertion-only streams by Cabello and Perez-Lanterno [Cabello and Pérez-Lantero, 2017], our result implies a separation between the insertion-only and turnstile model. For unit-radius disks, we obtain a (8√3/π)-approximation to α and β in poly(log(n)/ε) space, which is closely related to the hexagonal circle packing constant. Finally, we provide algorithms for estimating α for arbitrary-length intervals under a bounded intersection assumption and study the parameterized space complexity of estimating α and β, where the parameter is the ratio of maximum to minimum interval length.

We investigate the round complexity of maliciously-secure two-party quantum computation (2PQC) with setup, and obtain the following results: - A three-message protocol (two-message if only one party receives output) in the common random string (CRS) model assuming classical two-message oblivious transfer (OT) with post-quantum malicious security. This round complexity is optimal for the sequential communication setting. Under the additional assumption of reusable malicious designated-verifier non-interactive zero-knowledge (MDV-NIZK) arguments for NP, our techniques give an MDV-NIZK for QMA. Each of the assumptions mentioned above is known from the quantum hardness of learning with errors (QLWE). - A protocol with two simultaneous rounds of communication, in a quantum preprocessing model, assuming sub-exponential QLWE. In fact, we construct a three-round protocol in the CRS model with only two rounds of online communication, which implies the above result. Along the way, we develop a new delayed technique that we call simulation via teleportation, which may be useful in other settings. In addition, we perform a preliminary investigation into barriers and possible approaches for two-round 2PQC in the CRS model, including an impossibility result for a natural class of simulators, and a proof-of-concept construction from a strong form of quantum virtual black-box (VBB) obfuscation. Prior to our work, maliciously-secure 2PQC required round complexity linear in the size of the quantum circuit.

Consider the following fundamental learning problem: given input examples x ∈ Rd and their vector-valued labels, as defined by an underlying generative neural network, recover the weight matrices of this network. We consider two-layer networks, mapping Rd to Rm, with $k$ non-linear activation units f(·), where f(x) = x, 0 is the ReLU. Such a network is specified by two weight matrices, U* ∈ Rm × k, V* ∈ Rk × d, such that the label of an example x ∈ Rd is given by U* f(V* x), where f(·) is applied coordinate-wise. Given $n$ samples as a matrix X ∈ Rd × n and the (possibly noisy) labels U* f(V* X) + E of the network on these samples, where E is a noise matrix, our goal is to recover the weight matrices U* and V*. In this work, we develop algorithms and hardness results under varying assumptions on the input and noise. Although the problem is NP-hard even for $k=2$, by assuming Gaussian marginals over the input X we are able to develop polynomial time algorithms for the approximate recovery of U* and V*. Perhaps surprisingly, in the noiseless case our algorithms recover U*,V* exactly, i.e., with no error. To the best of the our knowledge, this is the first algorithm to accomplish exact recovery. For the noisy case, we give the first polynomial time algorithm that approximately recovers the weights in the presence of mean-zero noise E. Our algorithms generalize to a larger class of rectified activation functions, $f(x) = 0$ when x≤ 0, and $f(x) > 0$ otherwise.

Let P= p1, p2, … pn and Q = q1, q2 … qm be two point sets in an arbitrary metric space. Let A represent the m× n pairwise distance matrix with Ai,j = d(pi, qj). Such distance matrices are commonly computed in software packages and have applications to learning image manifolds, handwriting recognition, and multi-dimensional unfolding, among other things. In an attempt to reduce their description size, we study low rank approximation of such matrices. Our main result is to show that for any underlying distance metric $d$, it is possible to achieve an additive error low-rank approximation in sublinear time. We note that it is provably impossible to achieve such a guarantee in sublinear time for arbitrary matrices A, and consequently our proof exploits special properties of distance matrices. We develop a recursive algorithm based on additive projection-cost preserving sampling. We then show that in general, relative error approximation in sublinear time is impossible for distance matrices, even if one allows for bicriteria solutions. Additionally, we show that if P = Q and $d$ is the squared Euclidean distance, which is not a metric but rather the square of a metric, then a relative error bicriteria solution can be found in sublinear time.

Mixtures of Mallows models are a popular generative model for ranking data coming from a heterogeneous population. They have a variety of applications including social choice, recommendation systems and natural language processing. Here we give the first polynomial time algorithm for provably learning the parameters of a mixture of Mallows models with any constant number of components. Prior to our work, only the two component case had been settled. Our analysis revolves around a determinantal identity of Zagier which was proven in the context of mathematical physics, which we use to show polynomial identifiability and ultimately to construct test functions to peel off one component at a time. To complement our upper bounds, we show information-theoretic lower bounds on the sample complexity as well as lower bounds against restricted families of algorithms that make only local queries. Together, these results demonstrate various impediments to improving the dependence on the number of components. They also motivate the study of learning mixtures of Mallows models from the perspective of beyond worst-case analysis. In this direction, we show that when the scaling parameters of the Mallows models have separation, there are much faster learning algorithms.

In this work, we study the k-median and k-means clustering problems when the data is distributed across many servers and can contain outliers. While there has been a lot of work on these problems for worst-case instances, we focus on gaining a finer understanding through the lens of beyond worst-case analysis. Our main motivation is the following: for many applications such as clustering proteins by function or clustering communities in a social network, there is some unknown target clustering, and the hope is that running a k-median or k-means algorithm will produce clusterings which are close to matching the target clustering. Worst-case results can guarantee constant factor approximations to the optimal k-median or k-means objective value, but not closeness to the target clustering. Our first result is a distributed algorithm which returns a near-optimal clustering assuming a natural notion of stability, namely, approximation stability [Awasthi and Balcan, 2014], even when a constant fraction of the data are outliers. The communication complexity is O~(sk+z) where s is the number of machines, k is the number of clusters, and z is the number of outliers. Next, we show this amount of communication cannot be improved even in the setting when the input satisfies various non-worst-case assumptions. We give a matching Omega(sk+z) lower bound on the communication required both for approximating the optimal k-means or k-median cost up to any constant, and for returning a clustering that is close to the target clustering in Hamming distance. These lower bounds hold even when the data satisfies approximation stability or other common notions of stability, and the cluster sizes are balanced. Therefore, Omega(sk+z) is a communication bottleneck, even for real-world instances.

Clustering with most objective functions is NP-Hard, even to approximate well in the worst case. Recently, there has been work on exploring different notions of stability which lend structure to the problem. The notion of stability, $α$-perturbation resilience, that we study in this paper was originally introduced by Bilu et al.~\cite{Bilu10}. The works of Awasthi et al~\cite{Awasthi12} and Balcan et al.~\cite{Balcan12} provide a polynomial time algorithm for $3$-stable and (1+2)-stable instances respectively. This paper provides a polynomial time algorithm for $2$-stable instances, improving on and answering an open question in ~\cite{Balcan12}.

A function defined on the Boolean hypercube is k - Fourier-sparse if it has at most k nonzero Fourier coefficients. For a function f: F 2 n → R and parameters k and d, we prove a strong upper bound on the number of k-Fourier-sparse Boolean functions that disagree with f on at most d inputs. Our bound implies that the number of uniform and independent random samples needed for learning the class of k-Fourier-sparse Boolean functions on n variables exactly is at most O (n · k log k). As an application, we prove an upper bound on the query complexity of testing Booleanity of Fourier-sparse functions. Our bound is tight up to a logarithmic factor and quadratically improves on a result due to Gur and Tamuz [2013].

In the $k$-junta testing problem, a tester has to efficiently decide whether a given function f:0,1ⁿ→ 0,1 is a $k$-junta (i.e., depends on at most $k$ of its input bits) or is $ε$-far from any $k$-junta. Our main result is a quantum algorithm for this problem with query complexity O(k/ε) and time complexity O(nk/ε). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω(k1/3) queries for junta-testing (for constant $ε$).

The “learning with errors” (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives). We resolve this question in the affirmative by introducing an algebraic variant of LWE called ring-LWE, and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with an efficient security reduction; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE.

We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary $k$-qubit gates each of whose input wires is subject to depolarizing noise of strength $p$, as well as arbitrary one-qubit gates that are essentially noise-free. We assume that the output of the circuit is the result of measuring some designated qubit in the final state. Our main result is that for p>1-Θ(1/k), the output of any such circuit of large enough depth is essentially independent of its input, thereby making the circuit useless. For the important special case of $k=2$, our bound is p>35.7%. Moreover, if the only allowed gate on more than one qubit is the two-qubit CNOT gate, then our bound becomes 29.3%. These bounds on $p$ are numerically better than previous bounds, yet are incomparable because of the somewhat different circuit model that we are using. Our main technique is the use of a Pauli basis decomposition, in which the effects of depolarizing noise are very easy to describe.

We consider the following problem of bounded-error quantum state identification: Given either state α0 or state α1, we are required to output “0”, “1”, or “?” (“don't know"), such that conditioned on outputting “0” or “1”, our guess is correct with high probability. The goal is to maximize the probability of not outputting “?”. We prove the following direct product theorem: If we are given two such problems, with optimal probabilities a and b, respectively, and the states in the first problem are pure, then the optimal probability for the joint bounded-error state identification problem is $O(ab)$. Our proof is based on semidefinite programming duality. Using this result, we present two exponential separations in the simultaneous message passing model of communication complexity. First, we describe a relation that can be computed with O(n) classical bits of communication in the presence of shared randomness, but needs Ω(n1/3) communication if the parties don't share randomness, even if communication is quantum. This shows the optimality of Yao's recent exponential simulation of shared-randomness protocols by quantum protocols without shared randomness. Combined with an earlier separation in the other direction due to Bar-Yossef, Jayram, and Kerenidis, this shows that the quantum simultaneous message passing (SMP) model is incomparable with the classical shared-randomness SMP model. Second, we describe a relation that can be computed with O(n) classical bits of communication in the presence of shared entanglement, but needs Ω((n/ n)1/3) communication if the parties share randomness but no entanglement, even if communication is quantum. This is the first example in communication complexity of a situation where entanglement buys much more than quantum communication.