Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSchedule path optimization for quantum annealing and adiabatic quantum computing
184
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Adiabatic quantum computing and optimization have garnered much attention recently as possible models for achieving a quantum advantage over classical approaches to optimization and other special purpose computations. Both techniques are probabilistic in nature and the minimum gap between the ground state and first excited state of the system during evolution is a major factor in determining the success probability. In this work we investigate a strategy for increasing the minimum gap and success probability by introducing intermediate Hamiltonians that modify the evolution path between initial and final Hamiltonians. We focus on an optimization problem relevant to recent hardware implementations and present numerical evidence for the existence of a purely local intermediate Hamiltonian that achieve the optimum performance in terms of pushing the minimum gap to one of the end points of the evolution. As a part of this study we develop a convex optimization formulation of the search for optimal adiabatic schedules that makes this computation more tractable, and which may be of independent interest. We further study the effectiveness of random intermediate Hamiltonians on the minimum gap and success probability, and empirically find that random Hamiltonians have a significant probability of increasing the success probability, but only by a modest amount.
rate research
Read More
The graph-theoretic Ramsey numbers are notoriously difficult to calculate. In fact, for the two-color Ramsey numbers $R(m,n)$ with $m,ngeq 3$, only nine are currently known. We present a quantum algorithm for the computation of the Ramsey numbers $R(m,n)$. We show how the computation of $R(m,n)$ can be mapped to a combinatorial optimization problem whose solution can be found using adiabatic quantum evolution. We numerically simulate this adiabatic quantum algorithm and show that it correctly determines the Ramsey numbers R(3,3) and R(2,s) for $5leq sleq 7$. We then discuss the algorithms experimental implementation, and close by showing that Ramsey number computation belongs to the quantum complexity class QMA.
In the Graph Isomorphism problem two N-vertex graphs G and G are given and the task is to determine whether there exists a permutation of the vertices of G that preserves adjacency and transforms G into G. If yes, then G and G are said to be isomorphic; otherwise they are non-isomorphic. The GI problem is an important problem in computer science and is thought to be of comparable difficulty to integer factorization. In this paper we present a quantum algorithm that solves arbitrary instances of GI and can also determine all automorphisms of a given graph. We show how the GI problem can be converted to a combinatorial optimization problem that can be solved using adiabatic quantum evolution. We numerically simulate the algorithms quantum dynamics and show that it correctly: (i) distinguishes non-isomorphic graphs; (ii) recognizes isomorphic graphs; and (iii) finds all automorphisms of a given graph G. We then discuss the GI quantum algorithms experimental implementation, and close by showing how it can be leveraged to give a quantum algorithm that solves arbitrary instances of the NP-Complete Sub-Graph Isomorphism problem.
Boltzmann Machines constitute a class of neural networks with applications to image reconstruction, pattern classification and unsupervised learning in general. Their most common variants, called Restricted Boltzmann Machines (RBMs) exhibit a good trade-off between computability on existing silicon-based hardware and generality of possible applications. Still, the diffusion of RBMs is quite limited, since their training process proves to be hard. The advent of commercial Adiabatic Quantum Computers (AQCs) raised the expectation that the implementations of RBMs on such quantum devices could increase the training speed with respect to conventional hardware. To date, however, the implementation of RBM networks on AQCs has been limited by the low qubit connectivity when each qubit acts as a node of the neural network. Here we demonstrate the feasibility of a complete RBM on AQCs, thanks to an embedding that associates its nodes to virtual qubits, thus outperforming previous implementations based on incomplete graphs. Moreover, to accelerate the learning, we implement a semantic quantum search which, contrary to previous proposals, takes the input data as initial boundary conditions to start each learning step of the RBM, thanks to a reverse annealing schedule. Such an approach, unlike the more conventional forward annealing schedule, allows sampling configurations in a meaningful neighborhood of the training data, mimicking the behavior of the classical Gibbs sampling algorithm. We show that the learning based on reverse annealing quickly raises the sampling probability of a meaningful subset of the set of the configurations. Even without a proper optimization of the annealing schedule, the RBM semantically trained by reverse annealing achieves better scores on reconstruction tasks.
Quantum fluctuations driven by non-stoquastic Hamiltonians have been conjectured to be an important and perhaps essential missing ingredient for achieving a quantum advantage with adiabatic optimization. We introduce a transformation that maps every non-stoquastic adiabatic path ending in a classical Hamiltonian to a corresponding stoquastic adiabatic path by appropriately adjusting the phase of each matrix entry in the computational basis. We compare the spectral gaps of these adiabatic paths and find both theoretically and numerically that the paths based on non-stoquastic Hamiltonians have generically smaller spectral gaps between the ground and first excited states, suggesting they are less useful than stoquastic Hamiltonians for quantum adiabatic optimization. These results apply to any adiabatic algorithm which interpolates to a final Hamiltonian that is diagonal in the computational basis.
It is believed that the presence of anticrossings with exponentially small gaps between the lowest two energy levels of the system Hamiltonian, can render adiabatic quantum optimization inefficient. Here, we present a simple adiabatic quantum algorithm designed to eliminate exponentially small gaps caused by anticrossings between eigenstates that correspond with the local and global minima of the problem Hamiltonian. In each iteration of the algorithm, information is gathered about the local minima that are reached after passing the anticrossing non-adiabatically. This information is then used to penalize pathways to the corresponding local minima, by adjusting the initial Hamiltonian. This is repeated for multiple clusters of local minima as needed. We generate 64-qubit random instances of the maximum independent set problem, skewed to be extremely hard, with between 10^5 and 10^6 highly-degenerate local minima. Using quantum Monte Carlo simulations, it is found that the algorithm can trivially solve all the instances in ~10 iterations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
