We present a protocol for fault-tolerantly implementing the logical quantum random access memory (QRAM) operation, given access to a specialized, noisy QRAM device. For coherently accessing classical memories of size $2^{n}$, our protocol consumes only poly $(n)$ fault-tolerant quantum resources (logical gates, logical qubits, quantum error correction cycles, etc.), avoiding the need to perform active error correction on all $\Omega\left(2^{n}\right)$ components of the QRAM device. This is the first rigorous conceptual demonstration that a specialized, noisy QRAM device could be useful for implementing a fault-tolerant quantum algorithm. In fact, the fidelity of the device can be as low as $1 / \operatorname{poly}(n)$. The protocol queries the noisy QRAM device $\operatorname{poly}(n)$ times to prepare a sequence of n-qubit QRAM resource states, which are moved to a general-purpose poly $(n)$ size processor to be encoded into a QEC code, distilled, and faulttolerantly teleported into the computation. To aid this protocol, we develop a new gate-efficient streaming version of quantum purity amplification that matches the optimal sample complexity in a wide range of parameters and is therefore of independent interest. The exponential reduction in fault-tolerant quantum resources comes at the expense of an exponential quantity of purely classical complexity-each of the n iterations of the protocol requires adaptively updating the $2^{n}$-size classical dataset and providing the noisy QRAM device with access to the updated dataset at the next iteration. We show that this classical operation can be parallelized to poly $(n)$ classical circuit depth, but only in a model where classical sparse matrix-vector multiplication for $2^{n}$-dimensional vectors can be as well. While our protocol demonstrates that QRAM is more compatible with fault-tolerant quantum computation than previously thought, the need for significant classical computational complexity exposes potentially fundamental limitations to realizing a truly poly $(n)$-cost faulttolerant QRAM.

Finding a good approximation of the top eigenvector of a given d x d matrix A is a basic and important computational problem, with many applications. We give two different quantum algorithms that, given query access to the entries of a Hermitian matrix A and assuming a constant eigenvalue gap, output a classical description of a good approximation of the top eigenvector: one algorithm with time complexity Õ (d 1.75 ) and one with time complexity d 1.5+0(1) (the first algorithm has a slightly better dependence on the ℓ2-error of the approximating vector than the second, and uses different techniques of independent interest). Both of our quantum algorithms provide a polynomial speed-up over the best-possible classical algorithm, which needs Ω (d 2) queries to entries of A, and hence Ω(d 2) time. We extend this to a quantum algorithm that outputs a classical description of the subspace spanned by the top-q eigenvectors in time qd 1.5+o (1). We also prove a nearly-optimal lower bound of on the quantum query complexity of approximating the top eigenvector.

Abstract. Aaronson and Ambainis [ Theory Comput., 10 (2014), pp. 133–166] and Chailloux [ Proceedings of the 10 th Innovations in Theoretical Computer Science Conference, 2018, pp. 19:1–19:7] showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent superpolynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow superpolynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs—where graph symmetry is manifested differently—we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu [ Lecture Notes in Comput. Sci. 6845, Springer, 2011, pp. 365–376] and Montanaro and de Wolf [ Theory Comput., 7 (2016)].

We describe algorithms to obtain an approximate classical description of a d-dimensional quantum state when given access to a unitary (and its inverse) that prepares it. For pure states we characterize the query complexity for ℓq-norm error up to logarithmic factors. As a special case, we show that it takes applications of the unitaries to obtain an ε-ℓ2-approximation of the state. For mixed states we consider a similar model, where the unitary prepares a purification of the state. We characterize the query complexity for obtaining Schatten q-norm estimates of a rank-r mixed state, up to polylogarithmic factors. In particular, we show that a trace-norm (q = 1) estimate can be obtained with queries. This improves (assuming our stronger input model) the ε-dependence over the works of O'Donnell and Wright (STOC 2016) and Haah et al. (IEEE Trans. Inf. Theory, 63.9, 2017), that use a joint measurement on copies of the state. To our knowledge, the most sample-efficient results for pure-state tomography come from setting the rank to 1 in generic mixed-state tomography algorithms, which can require a large amount of computing resources. We describe sample-optimal algorithms for pure states that are simple and fast to implement. Along the way we show that an ℓ∞-norm estimate of a normalized vector induces a (slightly worse) ℓq-norm estimate for that vector, without losing a dimension-dependent factor in the precision. We also develop an unbiased and symmetric version of phase estimation, where the probability distribution of the estimate is centered around the true value. Finally, we give an efficient method for estimating multiple expectation values, improving over the recent result by Huggins et al. (arXiv:2111.09283) when the measurement operators do not fully overlap. More specifically, we show that for E1,…, Em normalized measurement operators, all expectation values Tr(Ejρ) can be efficiently learned up to error ε with applications of a state-preparation unitary for a purification of ρ. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.08800

We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang’s breakthrough quantum-inspired algorithm for recommendation systems [STOC’19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyén et al. [STOC’19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all prior results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: ℓ 2 -norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.

Many quantum algorithms critically rely on quantum walk search, or the use of quantum walks to speed up search problems on graphs. However, the main results on quantum walk search are scattered over different, incomparable frameworks, such as the hitting time framework, the MNRS framework, and the electric network framework. As a consequence, a number of pieces are currently missing. For example, recent work by Ambainis et al. (STOC'20) shows how quantum walks starting from the stationary distribution can always find elements quadratically faster. In contrast, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. We present a new quantum walk search framework that unifies and strengthens these frameworks, leading to a number of new results. For example, the new framework effectively finds marked elements in the electric network setting. The new framework also allows to interpolate between the hitting time framework, minimizing the number of walk steps, and the MNRS framework, minimizing the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. In addition to quantum walks and phase estimation, our new algorithm makes use of quantum fast-forwarding, similar to the recent results by Ambainis et al. This perspective also enables us to derive more general complexity bounds on the quantum walk algorithms, e.g., based on Monte Carlo type bounds of the corresponding classical walk. As a final result, we show how in certain cases we can avoid the use of phase estimation and quantum fast-forwarding, answering an open question of Ambainis et al.

We demonstrate the possibility of (sub)exponential quantum speedup via a quantum algorithm that follows an adiabatic path of a gapped Hamiltonian with no sign problem. The Hamiltonian that exhibits this speed-up comes from the adjacency matrix of an undirected graph whose vertices are labeled by n-bit strings, and we can view the adiabatic evolution as an efficient O(poly(n))-time quantum algorithm for finding a specific “EXIT” vertex in the graph given the “ENTRANCE” vertex. On the other hand we show that if the graph is given via an adjacency-list oracle, there is no classical algorithm that finds the “EXIT” with probability greater than exp(−nδ) using at most exp(nδ) queries for δ= 1/5 − o(1). Our construction of the graph is somewhat similar to the “welded-trees” construction of Childs et al., but uses additional ideas of Hastings for achieving a spectral gap and a short adiabatic path.

Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs-where graph symmetry is manifested differently-we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013).

A fundamental problem in statistics and learning theory is to test properties of distributions. We show that quantum computers can solve such problems with significant speed-ups. In particular, we give fast quantum algorithms for testing closeness between unknown distributions, testing independence between two distributions, and estimating the Shannon / von Neumann entropy of distributions. The distributions can be either classical or quantum, however our quantum algorithms require coherent quantum access to a process preparing the samples. Our results build on the recent technique of quantum singular value transformation, combined with more standard tricks such as divide-and-conquer. The presented approach is a natural fit for distributional property testing both in the classical and the quantum case, demonstrating the first speed-ups for testing properties of density operators that can be accessed coherently rather than only via sampling; for classical distributions our algorithms significantly improve the precision dependence of some earlier results.

We present classical sublinear-time algorithms for solving low-rank linear systems of equations. Our algorithms are inspired by the HHL quantum algorithm for solving linear systems and the recent breakthrough by Tang of dequantizing the quantum algorithm for recommendation systems. Let $A \in \mathbb{C}^{m \times n}$ be a rank-$k$ matrix, and $b \in \mathbb{C}^m$ be a vector. We present two algorithms: a "sampling" algorithm that provides a sample from $A^{-1}b$ and a "query" algorithm that outputs an estimate of an entry of $A^{-1}b$, where $A^{-1}$ denotes the Moore-Penrose pseudo-inverse. Both of our algorithms have query and time complexity $O(\mathrm{poly}(k, κ, \|A\|_F, 1/ε)\,\mathrm{polylog}(m, n))$, where $κ$ is the condition number of $A$ and $ε$ is the precision parameter. Note that the algorithms we consider are sublinear time, so they cannot write and read the whole matrix or vectors. In this paper, we assume that $A$ and $b$ come with well-known low-overhead data structures such that entries of $A$ and $b$ can be sampled according to some natural probability distributions. Alternatively, when $A$ is positive semidefinite, our algorithms can be adapted so that the sampling assumption on $b$ is not required.

A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk, resolving a question that had been open for 15 years.

We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang’s breakthrough quantum-inspired algorithm for recommendation systems [STOC’19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyén et al. [STOC’19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffices to generalize all recent results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: ℓ2-norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.

Following the first paper on quantum algorithms for SDP-solving by Brandão and Svore in 2016, rapid developments has been made on quantum optimization algorithms. Recently Brandão et al. improved the quantum SDP-solver in the so-called quantum state input model, where the input matrices of the SDP are given as purified mixed states. They also gave the first non-trivial application of quantum SDP-solving by obtaining a more efficient algorithm for the problem of shadow tomography (proposed by Aaronson in 2017). In this paper we improve on all previous quantum SDP-solvers. Mainly we construct better Gibbs-samplers for both input models, which directly gives better bounds for SDP-solving. For an SDP with $m$ constraints involving $n\times n$ matrices, our improvements yield an $\widetilde{\mathcal O}\left( \left( \sqrt{m} + \sqrt{n}γ\right)s γ^4\right)$ upper bound on SDP-solving in the sparse matrix input model and an $\widetilde{\mathcal O}\left( \left(\sqrt{m}+B^{2.5}γ^{3.5} \right)Bγ^4 \right)$ upper bound in the quantum state input model. We then apply these results to the problem of shadow tomography to simultaneously improve the best known upper bounds on sample complexity due to Aaronson and complexity due Brandao et al. Furthermore, we apply our quantum SDP-solvers to the problems of quantum state discrimination and E-optimal design. In both cases we beat the classical lower bound in terms of some parameters, at the expense of heavy dependence on some other parameters. Finally we prove two lowers bounds for solving SDPs using quantum algorithms: (1) $\tildeΩ(\sqrt{m}B/\eps)$ in the quantum state input model, and (2) $\tildeΩ(\sqrt{m}α/\eps)$ in the quantum operator input model. These lower bounds show that the $\sqrt{m}$ factor and the polynomial dependence on the parameters $B,α$, and $1/\eps$ are necessary.

We apply the framework of block-encodings, introduced by Low and Chuang (under the name standard-form), to the study of quantum machine learning algorithms and derive general results that are applicable to a variety of input models, including sparse matrix oracles and matrices stored in a data structure. We develop several tools within the block-encoding framework, such as singular value estimation of a block-encoded matrix, and quantum linear system solvers using block-encodings. The presented results give new techniques for Hamiltonian simulation of non-sparse matrices, which could be relevant for certain quantum chemistry applications, and which in turn imply an exponential improvement in the dependence on precision in quantum linear systems solvers for non-sparse matrices. In addition, we develop a technique of variable-time amplitude estimation, based on Ambainis' variable-time amplitude amplification technique, which we are also able to apply within the framework. As applications, we design the following algorithms: (1) a quantum algorithm for the quantum weighted least squares problem, exhibiting a 6-th power improvement in the dependence on the condition number and an exponential improvement in the dependence on the precision over the previous best algorithm of Kerenidis and Prakash; (2) the first quantum algorithm for the quantum generalized least squares problem; and (3) quantum algorithms for estimating electrical-network quantities, including effective resistance and dissipated power, improving upon previous work.

We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate realvalued function f : ℝd → ℝ by evaluating it at only a logarithmic number of times in superposition. Our algorithm is an improved version of Jordan's gradient computation algorithm [28], providing an approximation of the gradient ▽f with quadratically better dependence on the evaluation accuracy of f, for an important class of smooth functions. Furthermore, we show that objective functions arising from variational quantum circuits usually satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension d. One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function f. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).

An n-qubit quantum circuit performs a unitary operation on an exponentially large, 2n-dimensional, Hilbert space, which is a major source of quantum speed-ups. We develop a new “Quantum singular value transformation” algorithm that can directly harness the advantages of exponential dimensionality by applying polynomial transformations to the singular values of a block of a unitary operator. The transformations are realized by quantum circuits with a very simple structure - typically using only a constant number of ancilla qubits - leading to optimal algorithms with appealing constant factors. We show that our framework allows describing many quantum algorithms on a high level, and enables remarkably concise proofs for many prominent quantum algorithms, ranging from optimal Hamiltonian simulation to various quantum machine learning applications. We also devise a new singular vector transformation algorithm, describe how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum, and show how to efficiently implement principal component regression. Finally, we also prove a quantum lower bound on spectral transformations.

Brandao and Svore recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension n of the problem and the number m of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure.We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimizations problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with mn when m is approximately n, which is the same as classical.

A frustration-free local Hamiltonian has the property that its ground state minimises the energy of all local terms simultaneously. In general, even deciding whether a Hamiltonian is frustration-free is a hard task, as it is closely related to the QMA1-complete quantum satisfiability problem (QSAT) - the quantum analogue of SAT, which is the archetypal NP-complete problem in classical computer science. This connection shows that the frustration-free property is not only relevant to physics but also to computer science. The Quantum Lovasz Local Lemma (QLLL) provides a sufficient condition for frustration-freeness. Is there an efficient way to prepare a frustration-free state under the conditions of the QLLL? Previous results showed that the answer is positive if all local terms commute. These works were based on Moser's “compression argument” which was the original analysis technique of the celebrated resampling algorithm. We generalise and simplify the “compression argument”, so that it provides a simplified version of the previous quantum results, and improves on some classical results as well. More importantly, we improve on the previous constructive results by designing an algorithm that works efficiently for non-commuting terms as well, assuming that the system is “uniformly” gapped, by which we mean that the system and all its subsystems have an inverse polynomial energy gap. Similarly to the previous results, our algorithm has the charming feature that it uses only local measurement operations corresponding to the local Hamiltonian terms.