Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
142
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper we study the performance of the quantum adiabatic algorithm on random instances of two combinatorial optimization problems, 3-regular 3-XORSAT and 3-regular Max-Cut. The cost functions associated with these two clause-based optimization problems are similar as they are both defined on 3-regular hypergraphs. For 3-regular 3-XORSAT the clauses contain three variables and for 3-regular Max-Cut the clauses contain two variables. The quantum adiabatic algorithms we study for these two problems use interpolating Hamiltonians which are stoquastic and therefore amenable to sign-problem free quantum Monte Carlo and quantum cavity methods. Using these techniques we find that the quantum adiabatic algorithm fails to solve either of these problems efficiently, although for different reasons.
rate research
Read More
A 2-coloring of a hypergraph is a mapping from its vertices to a set of two colors such that no edge is monochromatic. Let $H_k(n,m)$ be a random $k$-uniform hypergraph on $n$ vertices formed by picking $m$ edges uniformly, independently and with replacement. It is easy to show that if $r geq r_c = 2^{k-1} ln 2 - (ln 2) /2$, then with high probability $H_k(n,m=rn)$ is not 2-colorable. We complement this observation by proving that if $r leq r_c - 1$ then with high probability $H_k(n,m=rn)$ is 2-colorable.
Adiabatic quantum optimization offers a new method for solving hard optimization problems. In this paper we calculate median adiabatic times (in seconds) determined by the minimum gap during the adiabatic quantum optimization for an NP-hard Ising spin glass instance class with up to 128 binary variables. Using parameters obtained from a realistic superconducting adiabatic quantum processor, we extract the minimum gap and matrix elements using high performance Quantum Monte Carlo simulations on a large-scale Internet-based computing platform. We compare the median adiabatic times with the median running times of two classical solvers and find that, for the considered problem sizes, the adiabatic times for the simulated processor architecture are about 4 and 6 orders of magnitude shorter than the two classical solvers times. This shows that if the adiabatic time scale were to determine the computation time, adiabatic quantum optimization would be significantly superior to those classical solvers for median spin glass problems of at least up to 128 qubits. We also discuss important additional constraints that affect the performance of a realistic system.
Motivated by the quantum adiabatic algorithm (QAA), we consider the scaling of the Hamiltonian gap at quantum first order transitions, generally expected to be exponentially small in the size of the system. However, we show that a quantum antiferromagnetic Ising chain in a staggered field can exhibit a first order transition with only an algebraically small gap. In addition, we construct a simple classical translationally invariant one-dimensional Hamiltonian containing nearest-neighbour interactions only, which exhibits an exponential gap at a thermodynamic quantum first-order transition of essentially topological origin. This establishes that (i) the QAA can be successful even across first order transitions but also that (ii) it can fail on exceedingly simple problems readily solved by inspection, or by classical annealing.
We report the realization of a nuclear magnetic resonance computer with three quantum bits that simulates an adiabatic quantum optimization algorithm. Adiabatic quantum algorithms offer new insight into how quantum resources can be used to solve hard problems. This experiment uses a particularly well suited three quantum bit molecule and was made possible by introducing a technique that encodes general instances of the given optimization problem into an easily applicable Hamiltonian. Our results indicate an optimal run time of the adiabatic algorithm that agrees well with the prediction of a simple decoherence model.
We report on the energy-expectation-value landscapes produced by the single-layer ($p=1$) Quantum Approximate Optimization Algorithm (QAOA) when being used to solve Ising problems. The landscapes are obtained using an analytical formula that we derive. The formula allows us to predict the landscape for any given Ising problem instance and consequently predict the optimal QAOA parameters for heuristically solving that instance using the single-layer QAOA. We have validated our analytical formula by showing that it accurately reproduces the landscapes published in recent experimental reports. We then applied our methods to address the question: how well is the single-layer QAOA able to solve large benchmark problem instances? We used our analytical formula to calculate the optimal energy-expectation values for benchmark MAX-CUT problems containing up to $7,000$ vertices and $41,459$ edges. We also calculated the optimal energy expectations for general Ising problems with up to $100,000$ vertices and $150,000$ edges. Our results provide an estimate for how well the single-layer QAOA may work when run on a quantum computer with thousands of qubits. In addition to providing performance estimates when optimal angles are used, we are able to use our analytical results to investigate the difficulties one may encounter when running the QAOA in practice for different classes of Ising instances. We find that depending on the parameters of the Ising Hamiltonian, the expectation-value landscapes can be rather complex, with sharp features that necessitate highly accurate rotation gates in order for the QAOA to be run optimally on quantum hardware. We also present analytical results that explain some of the qualitative landscape features that are observed numerically.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
