Besides the traditional circuit-based model of quantum computation, several quantum algorithms based on a continuous-time Hamiltonian evolution have recently been introduced, including for instance continuous-time quantum walk algorithms as well as adiabatic quantum algorithms. Unfortunately, very little is known today about the behavior of these Hamiltonian algorithms in the presence of noise. Here, we perform a fully analytical study of the resistance to noise of these algorithms using perturbation theory combined with a theoretical noise model based on random matrices drawn from the Gaussian orthogonal ensemble, whose elements vary in time and form a stationary random process.
Besides the traditional circuit-based model of quantum computation, several quantum algorithms based on a continuous-time Hamiltonian evolution have recently been introduced, including for instance continuous-time quantum walk algorithms as well as adiabatic quantum algorithms. Unfortunately, very little is known today about the behavior of these Hamiltonian algorithms in the presence of noise. Here, we perform a fully analytical study of the resistance to noise of these algorithms using perturbation theory combined with a theoretical noise model based on random matrices drawn from the Gaussian orthogonal ensemble, whose elements vary in time and form a stationary random process.
Computing using a continuous-time evolution, based on the natural interaction Hamiltonian of the quantum computer hardware, is a promising route to building useful quantum computers in the near term. Adiabatic quantum computing, quantum annealing, computation by a continuous-time quantum walk, and special purpose quantum simulators all use this strategy. In this work, we carry out a detailed examination of adiabatic and quantum-walk implementation of the quantum search algorithm, using the more physically realistic hypercube connectivity, rather than the complete graph, for our base Hamiltonian. We calculate optimal adiabatic schedules both analytically and numerically for the hypercube and then interpolate between adiabatic and quantum-walk searching, obtaining a family of hybrid algorithms. We show that all of these hybrid algorithms provide the quadratic quantum speedup when run with optimal parameter settings, which we determine and discuss in detail. We incorporate the effects of multiple runs of the same algorithm, noise applied to the qubits, and two types of problem misspecification, determining the optimal hybrid algorithm for each case. Our results reveal a rich structure of how these different computational mechanisms operate and should be balanced in different scenarios. For large systems with low noise and good control, a quantum walk is the best choice, while hybrid strategies can mitigate the effects of many shortcomings in hardware and problem misspecification.
We present an analysis of the quantum adiabatic algorithm for solving hard instances of 3-SAT (an NP-complete problem) in terms of random matrix theory (RMT). We determine the global regularity of the spectral fluctuations of the instantaneous Hamiltonians encountered during the interpolation between the starting Hamiltonians and the ones whose ground states encode the solutions to the computational problems of interest. At each interpolation point, we quantify the degree of regularity of the average spectral distribution via its Brody parameter, a measure that distinguishes regular (i.e., Poissonian) from chaotic (i.e., Wigner-type) distributions of normalized nearest-neighbor spacings. We find that for hard problem instances---i.e., those having a critical ratio of clauses to variables---the spectral fluctuations typically become irregular across a contiguous region of the interpolation parameter, while the spectrum is regular for easy instances. Within the hard region, RMT may be applied to obtain a mathematical model of the probability of avoided level crossings and concomitant failure rate of the adiabatic algorithm due to nonadiabatic Landau-Zener-type transitions. Our model predicts that if the interpolation is performed at a uniform rate, the average failure rate of the quantum adiabatic algorithm, when averaged over hard problem instances, scales exponentially with increasing problem size.
This paper investigates the application of Random Matrix Theory (RMT) to the analytical complexity assessment of quantum algorithms. Traditional methods for estimating the computational complexity of quantum algorithms often rely on heuristics and approximations, frequently leading to overly pessimistic or overly optimistic results. We propose a novel approach utilizing RMT to model the statistical behavior of quantum circuits. Specifically, we leverage the eigenvalues and eigenvectors of random matrices to characterize the evolution of quantum states under arbitrary quantum circuits. This allows for a more precise estimation of the number of quantum gates (operations) required to achieve a desired level of accuracy in solving a given problem. We demonstrate, through illustrative examples, how RMT can provide tighter and more accurate bounds on the computational complexity compared to conventional techniques. The core claim of this work is that RMT offers a fundamentally new perspective on complexity analysis, promising to reveal deeper insights into the performance characteristics of quantum algorithms and potentially guide the design of more efficient quantum solutions.
Quantum mechanical computers can solve certain problems asymptotically faster than any classical computing device. Several fast quantum algorithms are known, but the nature of quantum speedup is not well understood, and inventing new quantum algorithms seems to be difficult. In this thesis, we explore two approaches to designing quantum algorithms based on continuous-time Hamiltonian dynamics. In quantum computation by adiabatic evolution, the computer is prepared in the known ground state of a simple Hamiltonian, which is slowly modified so that its ground state encodes the solution to a problem. We argue that this approach should be inherently robust against low-temperature thermal noise and certain control errors, and we support this claim using simulations. We then show that any adiabatic algorithm can be implemented in a different way, using only a sequence of measurements of the Hamiltonian. We illustrate how this approach can achieve quadratic speedup for the unstructured search problem. We also demonstrate two examples of quantum speedup by quantum walk, a quantum mechanical analog of random walk. First, we consider the problem of searching a region
A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.
In this thesis, we study the evolution of qubits evolving according to the Schrödinger equation with a Hamiltonian containing noise terms, modeled by random diagonal and off-diagonal matrix elements. For a single qubit exposed to such noise, we show that the noise-averaged qubit density matrix converges to a specific final state, in the limit of large time t. We find that the convergence speed is polynomial in 1=t, with a power that depends on the regularity and the low frequency behaviour of the noise probability density. We evaluate the final state explicitly in the regimes of weak and strong off-diagonal noise. We show that the process implements the well-known dephasing channel in the localized and delocalized basis, respectively. Furthermore, we consider the evolution of the entanglement of two (or more) qubits subject to Gaussian noises with varying means and variances. We consider two different cases: individual noise where each qubit feels an independent noise, and common noise where all qubits are subjected to the same noise. We find the following characteristics of entanglement, measured by the concurrence of qubits. Initially entangled states lose their amount of entanglement in time due to the presence of the noise. The decay of entanglement happens more quickly for common noise than for individual noise. We also detect creation of entanglement due to the common noise: for some initially disentangled states, entanglement is created for intermediate times and then decays to zero in the long time again.