Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMinimizing minor embedding energy: an application in quantum annealing
63
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A significant challenge in quantum annealing is to map a real-world problem onto a hardware graph of limited connectivity. If the maximum degree of the problem graph exceeds the maximum degree of the hardware graph, one employs minor embedding in which each logical qubit is mapped to a tree of physical qubits. Pairwise interactions between physical qubits in the tree are set to be ferromagnetic with some coupling strength $F<0$. Here we address the question of what value $F$ should take in order to maximise the probability that the annealer finds the correct ground-state of an Ising problem. The sum of $|F|$ for each logical qubit is defined as minor embedding energy. We confirm experimentally that the ground-state probability is maximised when the minor embedding energy is minimised, subject to the constraint that no domain walls appear in every tree of physical qubits associated with each embedded logical qubit. We further develop an analytical lower bound on $|F|$ which satisfies this constraint and show that it is a tighter bound than that previously derived by Choi (Quantum Inf. Proc. 7 193 (2008)).
rate research
Read More
Quantum annealing provides a promising route for the development of quantum optimization devices, but the usefulness of such devices will be limited in part by the range of implementable problems as dictated by hardware constraints. To overcome constraints imposed by restricted connectivity between qubits, a larger set of interactions can be approximated using minor embedding techniques whereby several physical qubits are used to represent a single logical qubit. However, minor embedding introduces new types of errors due to its approximate nature. We introduce and study quantum annealing correction schemes designed to improve the performance of quantum annealers in conjunction with minor embedding, thus leading to a hybrid scheme defined over an encoded graph. We argue that this scheme can be efficiently decoded using an energy minimization technique provided the density of errors does not exceed the per-site percolation threshold of the encoded graph. We test the hybrid scheme using a D-Wave Two processor on problems for which the encoded graph is a 2-level grid and the Ising model is known to be NP-hard. The problems we consider are frustrated Ising model problem instances with planted (a priori known) solutions. Applied in conjunction with optimized energy penalties and decoding techniques, we find that this approach enables the quantum annealer to solve minor embedded instances with significantly higher success probability than it would without error correction. Our work demonstrates that quantum annealing correction can and should be used to improve the robustness of quantum annealing not only for natively embeddable problems, but also when minor embedding is used to extend the connectivity of physical devices.
A major limitation of current generations of quantum annealers is the sparse connectivity of manufactured qubits in the hardware graph. This technological limitation generated considerable interest, motivating efforts to design efficient and adroit minor-embedding procedures that bypass sparsity constraints. In this paper, starting from a previous equational formulation by Dridi et al. (arXiv:1810.01440), we propose integer programming (IP) techniques for solving the minor-embedding problem. The first approach involves a direct translation from the previous equational formulation to IP, while the second decomposes the problem into an assignment master problem and fiber condition checking subproblems. The proposed methods are able to detect instance infeasibility and provide bounds on solution quality, capabilities not offered by currently employed heuristic methods. We demonstrate the efficacy of our methods with an extensive computational assessment involving three different families of random graphs of varying sizes and densities. The direct translation as a monolithic IP model can be solved with existing commercial solvers yielding valid minor-embeddings, however, is outperformed overall by the decomposition approach. Our results demonstrate the promise of our methods for the studied benchmarks, highlighting the advantages of using IP technology for minor-embedding problems.
In order to treat all-to-all connected quadratic binary optimization problems (QUBO) with hardware quantum annealers, an embedding of the original problem is required due to the sparsity of the hardwares topology. Embedding fully-connected graphs -- typically found in industrial applications -- incurs a quadratic space overhead and thus a significant overhead in the time to solution. Here we investigate this embedding penalty of established planar embedding schemes such as minor embedding on a square lattice, minor embedding on a Chimera graph, and the Lechner-Hauke-Zoller scheme using simulated quantum annealing on classical hardware. Large-scale quantum Monte Carlo simulation suggest a polynomial time-to-solution overhead. Our results demonstrate that standard analog quantum annealing hardware is at a disadvantage in comparison to classical digital annealers, as well as gate-model quantum annealers and could also serve as benchmark for improvements of the standard quantum annealing protocol.
We study the effect of the anneal path control per qubit, a new user control feature offered on the D-Wave 2000Q quantum annealer, on the performance of quantum annealing for solving optimization problems by numerically solving the time-dependent Schrodinger equation for the time-dependent Hamiltonian modeling the annealing problems. The anneal path control is thereby modeled as a modified linear annealing scheme, resulting in an advanced and retarded scheme. The considered optimization problems are 2-SAT problems with 12 Boolean variables, a known unique ground state and a highly degenerate first excited state. We show that adjustment of the anneal path control can result in a widening of the minimal spectral gap by one or two orders of magnitude and an enhancement of the success probability of finding the solution of the optimization problem. We scrutinize various iterative methods based on the spin floppiness, the average spin value, and on the average energy and describe their performance in boosting the quantum annealing process.
Advancements in computing based on qubit networks, and in particular the flux-qubit processor architecture developed by D-Wave Systems Inc., have enabled the physical simulation of quantum-dot cellular automata (QCA) networks beyond the limit of classical methods. However, the embedding of QCA networks onto the available processor architecture is a key challenge in preparing such simulations. In this work, two approaches to embedding QCA circuits are characterized: a dense placement algorithm that uses a routing method based on negotiated congestion; and a heuristic method implemented in D-Waves Solver API package. A set of benchmark QCA networks is used to characterise the algorithms and a stochastic circuit generator is employed to investigate the performance for different processor sizes and active flux-qubit yields.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
