Ashley Montanaro

The limiting constraint on simulating materials on near-term quantum hardware is the requisite circuit depths and qubit numbers, with current estimates placing them well beyond near-term capabilities. A critical subroutine of simulation algorithms is implementing a layer of unitary evolutions by each local term in the Hamiltonian. In this work we develop a new quantum algorithm which dramatically reduces the estimated cost of material simulations using this subroutine, improving circuit depths by up to 6 orders of magnitude for Strontium Vanadate, for example. We achieve this by introducing a fermionic encoding that leverages the locality of materials Hamiltonians describing an active space in the Wannier basis. This design generates quantum circuits whose depth is independent of the system’s size.

We study the problem of learning an unknown graph provided via an oracle using a quantum algorithm. We consider three query models. In the first model (``OR queries''), the oracle returns whether a given subset of the vertices contains any edges. In the second (``parity queries''), the oracle returns the parity of the number of edges in a subset. In the third model, we are given copies of the graph state corresponding to the graph. We give quantum algorithms that achieve speedups over the best possible classical algorithms in the OR and parity query models, for some families of graphs, and give quantum algorithms in the graph state model whose complexity is similar to the parity query model. For some parameter regimes, the speedups can be exponential in the parity query model. On the other hand, without any promise on the graph, no speedup is possible in the OR query model. A main technique we use is the quantum algorithm for solving the combinatorial group testing problem, for which a query-efficient quantum algorithm was given by Belovs. Here we additionally give a time-efficient quantum algorithm for this problem, based on the algorithm of Ambainis et al.\ for a ``gapped" version of the group testing problem. We also give simple time-efficient quantum algorithms based on Fourier sampling and amplitude amplification for learning the exact-half and majority functions, which almost match the optimal complexity of Belovs' algorithms.

Abstract Majority vote is a basic method for amplifying correct outcomes that is widely used in computer science and beyond. It can, for example, be used to amplify the correctness of a quantum device whose output is classical. However, when the output of a device is a quantum state, it is not apriori clear how to implement an analogous \emph{quantum} majority vote. To this end, we consider an extension of majority vote to quantum inputs and outputs: given a product state of the form $\ket{\phi_1, \phi_2, \dotsc ,\phi_n}$ where each qubit $\ket{\phi_i}$ is in one of two orthogonal states $\ket{\psi_0}$ or $\ket{\psi_1}$, output the majority state $\ket{\psi_0}$ or $\ket{\psi_1}$. We provide an optimal algorithm for this problem that achieves worst-case fidelity of $1/2 + \Theta(1/\sqrt{n})$. Under the promise that at least $2/3$ of the qubits are in the majority state, the fidelity increases to $1 - \Theta(1/n)$ and approaches one in the limit. More generally, we initiate the study of covariant and symmetric Boolean functions $f: \set{0,1^n} \to \set{0,1}$ with quantum inputs and outputs. We provide a simple linear program of size roughly $n/2$ for computing the optimal worst-case fidelity and show that a generalization of our algorithm is optimal for computing $f$. Our algorithm has complexity $O(n^4 \log n)$ where $n$ is the number of qubits.