Let A be an s-sparse Hermitian matrix, f(x) be a univariate function, and i, j be two indices. In this work, we investigate the query complexity of approximating i f(A) j. We show that for any continuous function f(x):[−1,1]→ [−1,1], the quantum query complexity of computing i f(A) j± ε/4 is lower bounded by Ω(degε(f)). The upper bound is at most quadratic in degε(f) and is linear in degε(f) under certain mild assumptions on A. Here the approximate degree degε(f) is the minimum degree such that there is a polynomial of that degree approximating f up to additive error ε in the interval [−1,1]. We also show that the classical query complexity is lower bounded by Ω((s/2)(deg2ε(f)−1)/6) for any s≥ 4. Our results show that the quantum and classical separation is exponential for any continuous function of sparse Hermitian matrices, and also imply the optimality of implementing smooth functions of sparse Hermitian matrices by quantum singular value transformation. The main techniques we used are the dual polynomial method for functions over the reals, linear semi-infinite programming, and tridiagonal matrices.

Majority vote is a basic method for amplifying correct outcomes that is widely used in computer science and beyond. While it can amplify the correctness of a quantum device with classical output, the analogous procedure for quantum output is not known. We introduce quantum majority vote as the following task: given a product state |ψ_1⟩ ⊗ … ⊗ |ψ_n⟩ where each qubit is in one of two orthogonal states |ψ⟩ or |ψ^⟂⟩, output the majority state. We show that an optimal algorithm for this problem achieves worst-case fidelity of 1/2 + Θ(1/√n). Under the promise that at least 2/3 of the input qubits are in the majority state, the fidelity increases to 1 - Θ(1/n) and approaches 1 as n increases.We also consider the more general problem of computing any symmetric and equivariant Boolean function f: {0,1}ⁿ → {0,1} in an unknown quantum basis, and show that a generalization of our quantum majority vote algorithm is optimal for this task. The optimal parameters for the generalized algorithm and its worst-case fidelity can be determined by a simple linear program of size O(n). The time complexity of the algorithm is O(n⁴ log n) where n is the number of input qubits.

We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system \( A{\bf x}= {\bf b} \) , we show that there is a classical algorithm that outputs a data structure for \( {\bf x} \) allowing sampling and querying to the entries, where \( {\bf x} \) is such that \( \Vert {\bf x}- A^{+}{\bf b}\Vert \le \epsilon \Vert A^{+}{\bf b}\Vert \) . This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is \( \widetilde{O}(\kappa _F^6 \kappa ^2/\epsilon ^2) \) , where \( \kappa _F = \Vert A\Vert _F\Vert A^{+}\Vert \) and \( \kappa = \Vert A\Vert \Vert A^{+}\Vert \) . This improves the previous best algorithm [Gilyén, Song and Tang, arXiv:2009.07268] of complexity \( \widetilde{O}(\kappa _F^6 \kappa ^6/\epsilon ^4) \) . Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when A is row sparse, this method already returns an approximate solution \( {\bf x} \) in time \( \widetilde{O}(\kappa _F^2) \) , while the best quantum algorithm known returns \( | {\bf x} \rangle \) in time \( \widetilde{O}(\kappa _F) \) when A is stored in the QRAM data structure. As a result, assuming access to QRAM and if A is row sparse, the speedup based on current quantum algorithms is quadratic.

We describe two procedures which, given access to one copy of a quantum state and a sequence of two-outcome measurements, can distinguish between the case that at least one of the measurements accepts the state with high probability, and the case that all of the measurements have low probability of acceptance. The measurements cannot simply be tried in sequence, because early measurements may disturb the state being tested. One procedure is based on a variant of Marriott-Watrous amplification. The other procedure is based on the use of a test for this disturbance, which is applied with low probability. We find a number of applications: Quantum query complexity separations in the property testing model for testing isomorphism of functions under group actions. We give quantum algorithms for testing isomorphism, linear isomorphism and affine isomorphism of boolean functions which use exponentially fewer queries than is possible classically, and a quantum algorithm for testing graph isomorphism which uses polynomially fewer queries than the best algorithm known. Testing properties of quantum states and operations. We show that any finite property of quantum states can be tested using a number of copies of the state which is logarithmic in the size of the property, and give a test for genuine multipartite entanglement of states of n qubits that uses O(n) copies of the state. We also show that equivalence of two unitary operations under conjugation by a unitary picked from a fixed set can be tested efficiently. This is a natural quantum generalisation of testing isomorphism of boolean functions. Correcting an error in a result of Aaronson on de- Merlinizing quantum protocols. This result claimed that, in any one-way quantum communication protocol where two parties are assisted by an all-powerful but untrusted third party, the third party can be removed with only a modest increase in the communication cost. We give a corrected proof of a key technical lemma required for Aaronson's result.

The calculation of ground-state energies of physical systems can be formalized as the $k$-local Hamiltonian problem, which is a natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set $\mathcal{S}$ and scaling them by arbitrary weights. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterize the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset $\mathcal{S}$, the problem falls into one of the following categories: in $\mathsf{ P}$; $\mathsf{NP}$-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or $\mathsf{QMA}$-complete. The third of these classes has been shown to be $\mathsf{StoqMA}$-complete by Bravyi and Hastings. The characterization holds even if $\mathcal{S}$ does not contain any 1-local terms; for example, we prove for the first time $\mathsf{QMA}$-completeness of the Heisenberg and XY interactions in this setting. If $\mathcal{S}$ is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterization that goes beyond 2-local interactions: for any constant $k$, all $k$-local qubit Hamiltonians whose terms are picked from a fixed set $\mathcal{S}$ correspond to problems either in $\mathsf{P}$; polynomial-time equivalent to the Ising model with transverse magnetic fields; or $\mathsf{QMA}$-complete. These results are a quantum analogue of the maximization variant of Schaefer's dichotomy theorem for Boolean constraint satisfaction problems.

The calculation of ground-state energies of physical systems can be formalised as the k-local Hamiltonian problem, which is the natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterise the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P, NP-complete, polynomial-time equivalent to the Ising model with transverse magnetic fields, or QMA-complete. The third of these classes contains NP and is contained within StoqMA. The characterisation holds even if S does not contain any 1-local terms, for example, we prove for the first time QMA-completeness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterisation that goes beyond 2-local interactions: for any constant k, all k-local qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P, polynomial-time equivalent to the Ising model with transverse magnetic fields, or QMA-complete. These results are a quantum analogue of Schaefer's dichotomy theorem for boolean constraint satisfaction problems.

We give a test that can distinguish efficiently between product states of n quantum systems and states that are far from product. If applied to a state | ψ 〉 whose maximum overlap with a product state is 1 − ε , the test passes with probability 1 − Θ ( ε ), regardless of n or the local dimensions of the individual systems. The test uses two copies of | ψ 〉. We prove correctness of this test as a special case of a more general result regarding stability of maximum output purity of the depolarizing channel. A key application of the test is to quantum Merlin-Arthur games with multiple Merlins, where we obtain several structural results that had been previously conjectured, including the fact that efficient soundness amplification is possible and that two Merlins can simulate many Merlins: QMA( k ) = QMA(2) for k ≥ 2. Building on a previous result of Aaronson et al., this implies that there is an efficient quantum algorithm to verify 3-SAT with constant soundness, given two unentangled proofs of Õ (√ n ) qubits. We also show how QMA(2) with log-sized proofs is equivalent to a large number of problems, some related to quantum information (such as testing separability of mixed states) as well as problems without any apparent connection to quantum mechanics (such as computing injective tensor norms of 3-index tensors). As a consequence, we obtain many hardness-of-approximation results, as well as potential algorithmic applications of methods for approximating QMA(2) acceptance probabilities. Finally, our test can also be used to construct an efficient test for determining whether a unitary operator is a tensor product, which is a generalization of classical linearity testing.

We give a test that can distinguish efficiently between product states of n quantum systems and states which are far from product. If applied to a state |φ) whose maximum overlap with a product state is 1- ε, the test passes with probability 1-Θ(ε), regardless of n or the local dimensions of the individual systems. The test uses two copies of |φ). We prove correctness of this test as a special case of a more general result regarding stability of maximum output purity of the depolarising channel. A key application of the test is to quantum Merlin-Arthur games with multiple Merlins, where we obtain several structural results that had been previously conjectured, including the fact that soundness amplification is possible and that two Merlins can simulate many Merlins: QMA(k)=QMA(2) for k ≥ 2. Building on a previous result of Aaronson et al, this implies that there is an efficient quantum algorithm to verify 3-SAT with constant soundness, given two unentangled proofs of Õ(√n) qubits. Among other consequences, this result implies complexity-theoretic obstructions to finding a polynomial-time algorithm to determine separability of mixed quantum states, even up to constant error, and also to proving "weak" variants of the additivity conjecture for quantum channels. Finally, our test can also be used to construct an efficient test for determining whether a unitary operator is a tensor product, which is a generalisation of classical linearity testing.

We give a lower bound on the probability of error in quantum state discrimination. The bound is a weighted sum of the pairwise fidelities of the states to be distinguished.