Search

All known examples confirming the possibility of an exponential separation between classical simulation algorithms and stoquastic adiabatic quantum computing (AQC) exploit symmetries that constrain adiabatic dynamics to effective, symmetric subspaces. The symmetries produce large effective eigenvalue gaps, which in turn make adiabatic computation efficient. We present a classical algorithm to efficiently sample from the effective subspace of a $k$-local stoquastic Hamiltonian $H$, without a priori knowledge of its symmetries (or near-symmetries). Our algorithm maps any $k$-local Hamiltonian to a graph $G=(V,E)$ with $\lvert V \rvert = O\left(\mathrm{poly}(n)\right)$ where $n$ is the number of qubits. Given the well-known result of Babai, we exploit graph isomorphism to study the automorphisms of $G$ and arrive at an algorithm quasi-polynomial in $\lvert V\rvert$ for producing samples from the effective subspace eigenstates of $H$. Our results rule out exponential separations between stoquastic AQC and classical computation that arise from hidden symmetries in $k$-local Hamiltonians. Furthermore, our graph representation of $H$ is not limited to stoquastic Hamiltonians and may rule out corresponding obstructions in non-stoquastic cases, or be useful in studying additional properties of $k$-local Hamiltonians., Comment: 12 pages, 6 figures, added footnotes (v2), updated following peer review (v3)

An important family of span programs, st-connectivity span programs, have been used to design quantum algorithms in various contexts, including a number of graph problems and formula evaluation problems. The complexity of the resulting algorithms depends on the largest positive witness size of any 1-input, and the largest negative witness size of any 0-input. Belovs and Reichardt first showed that the positive witness size is exactly characterized by the effective resistance of the input graph, but only rough upper bounds were known previously on the negative witness size. We show that the negative witness size in an st-connectivity span program is exactly characterized by the capacitance of the input graph. This gives a tight analysis for algorithms based on st-connectivity span programs on any set of inputs. We use this analysis to give a new quantum algorithm for estimating the capacitance of a graph. We also describe a new quantum algorithm for deciding if a graph is connected, which improves the previous best quantum algorithm for this problem if we're promised that either the graph has at least kappa>1 components, or the graph is connected and has small average resistance, which is upper bounded by the diameter. We also give an alternative algorithm for deciding if a graph is connected that can be better than our first algorithm when the maximum degree is small. Finally, using ideas from our second connectivity algorithm, we give an algorithm for estimating the algebraic connectivity of a graph, the second largest eigenvalue of the Laplacian.

An important family of span programs, st-connectivity span programs, have been used to design quantum algorithms in various contexts, including a number of graph problems and formula evaluation problems. The complexity of the resulting algorithms depends on the largest positive witness size of any 1-input, and the largest negative witness size of any 0-input. Belovs and Reichardt first showed that the positive witness size is exactly characterized by the effective resistance of the input graph, but only rough upper bounds were known previously on the negative witness size. We show that the negative witness size in an st-connectivity span program is exactly characterized by the capacitance of the input graph. This gives a tight analysis for algorithms based on st-connectivity span programs on any set of inputs. We use this analysis to give a new quantum algorithm for estimating the capacitance of a graph. We also describe a new quantum algorithm for deciding if a graph is connected, which improves the previous best quantum algorithm for this problem if we're promised that either the graph has at least kappa>1 components, or the graph is connected and has small average resistance, which is upper bounded by the diameter. We also give an alternative algorithm for deciding if a graph is connected that can be better than our first algorithm when the maximum degree is small. Finally, using ideas from our second connectivity algorithm, we give an algorithm for estimating the algebraic connectivity of a graph, the second largest eigenvalue of the Laplacian.

Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian $H(s)$ with spectral gap $\gamma(s)$. Assuming the existence of an oracle $\Gamma$ such that $\gamma_\min = \Theta\left(\min_s\Gamma(s)\right)$, we provide an algorithm that reliably performs QAO in time $O\left(\gamma_\min^{-1}\right)$ with $O\left(\log(\gamma_\min^{-1})\right)$ oracle queries, where $\gamma_\min = \min_s \gamma(s)$. Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that $\|dH/ds\| \approx \gamma(s)$ and chooses its own runtime to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle $\Gamma$ for the problem of finding the minimum point $m = \mathrm{argmin}_u W(u)$ of the cost function $W:\mathcal{V}\longrightarrow [0,1]$, restricting ourselves to computational basis measurements and driving Hamiltonian $H(0)=I - |\mathcal{V}|^{-1}\sum_{u,v \in \mathcal{V}}\vert{u}\rangle\langle{v}\vert$. Requiring only that $W$ have a constant lower bound on its spectral gap and upper bound $\kappa$ on its spectral ratio, our QAO algorithm returns $m$ with probability $(1-\epsilon)(1-e^{-1/\epsilon})$ in time $\widetilde{\mathcal{O}}(\epsilon^{-1}[\sqrt{|\mathcal{V}|} + (\kappa-1)^{2/3}|\mathcal{V}|^{2/3}])$. This achieves a quantum advantage for all $\kappa$, and recovers Grover scaling up to logarithmic factors when $\kappa \approx 1$. We implement the algorithm as a subroutine in an optimization procedure that produces $m$ with exponentially small failure probability and expected runtime $\widetilde{\mathcal{O}}(\epsilon^{-1}[\sqrt{|\mathcal{V}|} + (\kappa-1)^{2/3}|\mathcal{V}|^{2/3}])$ even when $\kappa$ is not known beforehand., Comment: 41 pages, 1 figure

An important family of span programs, st-connectivity span programs, have been used to design quantum algorithms in various contexts, including a number of graph problems and formula evaluation problems. The complexity of the resulting algorithms depends on the largest positive witness size of any 1-input, and the largest negative witness size of any 0-input. Belovs and Reichardt first showed that the positive witness size is exactly characterized by the effective resistance of the input graph, but only rough upper bounds were known previously on the negative witness size. We show that the negative witness size in an st-connectivity span program is exactly characterized by the capacitance of the input graph. This gives a tight analysis for algorithms based on st-connectivity span programs on any set of inputs. We use this analysis to give a new quantum algorithm for estimating the capacitance of a graph. We also describe a new quantum algorithm for deciding if a graph is connected, which improves the previous best quantum algorithm for this problem if we're promised that either the graph has at least kappa > 1 components, or the graph is connected and has small average resistance, which is upper bounded by the diameter. We also give an alternative algorithm for deciding if a graph is connected that can be better than our first algorithm when the maximum degree is small. Finally, using ideas from our second connectivity algorithm, we give an algorithm for estimating the algebraic connectivity of a graph, the second largest eigenvalue of the Laplacian., Comment: 33 pages

In this paper we introduce and formalize Substochastic Monte Carlo (SSMC) algorithms. These algorithms, originally intended to be a better classical foil to quantum annealing than simulated annealing, prove to be worthy optimization algorithms in their own right. In SSMC, a population of walkers is initialized according to a known distribution on an arbitrary search space and varied into the solution of some optimization problem of interest. The first argument of this paper shows how an existing classical algorithm, "Go-With-The-Winners" (GWW), is a limiting case of SSMC when restricted to binary search and particular driving dynamics. Although limiting to GWW, SSMC is more general. We show that (1) GWW can be efficiently simulated within the SSMC framework, (2) SSMC can be exponentially faster than GWW, (3) by naturally incorporating structural information, SSMC can exponentially outperform the quantum algorithm that first inspired it, and (4) SSMC exhibits desirable search features in general spaces. Our approach combines ideas from genetic algorithms (GWW), theoretical probability (Fleming-Viot processes), and quantum computing. Not only do we demonstrate that SSMC is often more efficient than competing algorithms, but we also hope that our results connecting these disciplines will impact each independently. An implemented version of SSMC has previously enjoyed some success as a competitive optimization algorithm for Max-$k$-SAT., Comment: 24 pages, 2 figures

We investigate quantum backtracking algorithms of a type previously introduced by Montanaro (arXiv:1509.02374). These algorithms explore trees of unknown structure, and in certain cases exponentially outperform classical procedures (such as DPLL). Some of the previous work focused on obtaining a quantum advantage for trees in which a unique marked vertex is promised to exist. We remove this restriction and re-characterise the problem in terms of the effective resistance of the search space. To this end, we present a generalisation of one of Montanaro's algorithms to trees containing $k \geq 1$ marked vertices, where $k$ is not necessarily known \textit{a priori}. Our approach involves using amplitude estimation to determine a near-optimal weighting of a diffusion operator, which can then be applied to prepare a superposition state that has support only on marked vertices and ancestors thereof. By repeatedly sampling this state and updating the input vertex, a marked vertex is reached in a logarithmic number of steps. The algorithm thereby achieves the conjectured bound of $\widetilde{\mathcal{O}}(\sqrt{TR_{\mathrm{max}}})$ for finding a single marked vertex and $\widetilde{\mathcal{O}}\left(k\sqrt{T R_{\mathrm{max}}}\right)$ for finding all $k$ marked vertices, where $T$ is an upper bound on the tree size and $R_{\mathrm{max}}$ is the maximum effective resistance encountered by the algorithm. This constitutes a speedup over Montanaro's original procedure in both the case of finding one and finding multiple marked vertices in an arbitrary tree. If there are no marked vertices, the effective resistance becomes infinite, and we recover the scaling of Montanaro's existence algorithm., Comment: 27 pages; typos fixed