Abstract

In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on n-bits in time poly(n)2^{n/2}. In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of Ω(2^{n/2}) has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is #P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.

Abstract

We develop three new methods to implement any Linear Combination of Unitaries (LCU), a powerful quantum algorithmic tool with diverse applications. While the standard LCU procedure requires several ancilla qubits and sophisticated multi-qubit controlled operations, our methods consume significantly fewer quantum resources. The first method (Single-Ancilla LCU) estimates expectation values of observables with respect to any quantum state prepared by an LCU procedure while requiring only a single ancilla qubit, and no multi-qubit controlled operations. The second approach (Analog LCU) is a simple, physically motivated, continuous-time analogue of LCU, tailored to hybrid qubit-qumode systems. The third method (Ancilla-free LCU) requires no ancilla qubit at all and is useful when we are interested in the projection of a quantum state (prepared by the LCU procedure) in some subspace of interest. We apply the first two techniques to develop new quantum algorithms for a wide range of practical problems, ranging from Hamiltonian simulation, ground state preparation and property estimation, and quantum linear systems. Remarkably, despite consuming fewer quantum resources they retain a provable quantum advantage. The third technique allows us to connect discrete and continuous-time quantum walks with their classical counterparts. It also unifies the recently developed optimal quantum spatial search algorithms in both these frameworks, and leads to the development of new ones that require fewer ancilla qubits. Overall, our results are quite generic and can be readily applied to other problems, even beyond those considered here.

Abstract

Over the years, the framework of Linear combination of unitaries (LCU) has been extremely useful for designing a plethora of quantum algorithms. In this work, we explore whether this widely applicable paradigm can be implemented on quantum computers that will be available immediately after the current NISQ stage. To this end, we develop three variants of LCU and apply each, to quantum algorithms of practical interest. First, we develop a physically motivated, continuous-time analogue of LCU (“Analog LCU”). This technique, implementable on hybrid qubit-qumode systems, is simpler than its discrete-time counterpart. We use this method to develop analog quantum algorithms for ground state preparation and quantum linear systems. We also develop a randomized quantum algorithm to sample from functions of Hamiltonians applied to quantum states (“Single-Ancilla LCU”). This approach repeatedly samples from a short-depth quantum circuit and uses only a single ancilla qubit. We use this to estimate expectation values of observables in the ground states of a Hamiltonian, and in the solution of quantum linear systems. This method is suitable for early fault-tolerant quantum computers. Our third approach stems from the observation that for several applications, it suffices to replace LCU with randomized sampling of unitaries according to the distribution of the LCU coefficients (“Ancilla-free LCU”). This is particularly useful when one is interested in the projection of a quantum state implemented by an LCU procedure in some subspace of interest. We demonstrate that this technique applies to the spatial search problem and helps establish a relationship between discrete and continuous-time quantum walks with their classical counterparts. Our work demonstrates that generic quantum algorithmic paradigms, such as LCU, can potentially be implemented on intermediate-term quantum devices.

Abstract

Linear regression is a widely used technique to fit linear models and finds widespread applications across different areas such as machine learning and statistics. In most real-world scenarios, however, linear regression problems are often ill-posed or the underlying model suffers from overfitting, leading to erroneous or trivial solutions. This is often dealt with by adding extra constraints, known as regularization. In this paper, we use the frameworks of block-encoding and quantum singular value transformation (QSVT) to design the first quantum algorithms for quantum least squares with general ℓ2-regularization. These include regularized versions of quantum ordinary least squares, quantum weighted least squares, and quantum generalized least squares. Our quantum algorithms substantially improve upon prior results on quantum ridge regression (polynomial improvement in the condition number and an exponential improvement in accuracy), which is a particular case of our result. To this end, we assume approximate block-encodings of the underlying matrices as input and use robust QSVT algorithms for various linear algebra operations. In particular, we develop a variable-time quantum algorithm for matrix inversion using QSVT, where we use quantum eigenvalue discrimination as a subroutine instead of gapped phase estimation. This ensures that substantially fewer ancilla qubits are required for this procedure than prior results. Owing to the generality of the block-encoding framework, our algorithms are applicable to a variety of input models and can also be seen as improved and generalized versions of prior results on standard (non-regularized) quantum least squares algorithms.

Abstract

In this article, we undertake a detailed study of the limiting behavior of a three-state discrete-time quantum walk on a one-dimensional lattice with generalized Grover coins. Two limit theorems are proved and consequently we show that the quantum walk exhibits localization at its initial position for a wide range of coin parameters. Finally, we discuss the effect of the coin parameters on the peak velocities of probability distributions of the underlying quantum walks.

Abstract

Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this article, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analog procedure to perform operations on a state of the form $e^{-tH^2}|\psi\rangle$, for a given Hamiltonian H: it only requires evolving H for time scaling as $\sqrt{t}$. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our work thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.

Abstract

Quantum walks [1–6] are quantum analogs of random walks on graphs and have widespread applications in several areas of quantum information processing [7]. In particular, they are a universal model for quantum computation and are crucial to the design of quantum algorithms for a plethora of problems such as element distinctness [8,9], searching for a marked state in graphs [10–16], matrix product verification [17], triangle finding [18], group commutativity [19], and many others [20–24]. In fact, for some oracular problems, quantum walks exhibit an exponential speedup over their classical counterparts [21,22]. For several of these algorithms, the runtime strongly depends on the time required for the quantum walk on a graph to localize at a vertex inside a marked set of vertices of interest. In the context of classical random walks, the hitting time is defined as the expected time required to hit a marked vertex. As such, the quantum hitting time characterizes the running time of the underlying quantum algorithm [14,15,20,21,25,26]. For continuous-time quantum walk (CTQW), the Hamiltonian governing the dynamics of the walk encodes the (vertex or edge) connectivity of the underlying graph. The dynamics involves evolving some initial state according to this Hamiltonian for time T , followed by a measurement in the basis spanned by the vertices of the graph, thus finding a target state with a high probability. However, Hamiltonian evolutions are unitary, and therefore, unlike classical random walks, quantum walks never converge to a fixed state with time. One method to address this is to evolve the system by H

Abstract

Continuous-time quantum walks have proven to be an extremely useful framework for the design of several quantum algorithms. Often, the running time of quantum algorithms in this framework is characterized by the quantum hitting time: the time required by the quantum walk to find a vertex of interest with a high probability. In this article, we provide improved upper bounds for the quantum hitting time that can be applied to several CTQW-based quantum algorithms. In particular, we apply our techniques to the glued-trees problem, improving their hitting time upper bound by a polynomial factor: from O(n 5 ) to O(n 2 log n). Furthermore, our methods also help to exponentially improve the dependence on precision of the continuous-time quantum walk based algorithm to find a marked node on any ergodic, reversible Markov chain by Chakraborty et al. [PRA 102, 022227 (2020)].