Quantum Annealers Chain Strengths: A Simple Heuristic to Set Them All
2404.05443
0
0
Abstract
Quantum annealers (QA), such as D-Wave systems, become increasingly efficient and competitive at solving combinatorial optimization problems. However, solving problems that do not directly map the chip topology remains challenging for this type of quantum computer. The creation of logical qubits as sets of interconnected physical qubits overcomes limitations imposed by the sparsity of the chip at the expense of increasing the problem size and adding new parameters to optimize. This paper explores the advantages and drawbacks provided by the structure of the logical qubits and the impact of the rescaling of coupler strength on the minimum spectral gap of Ising models. We show that densely connected logical qubits require a lower chain strength to maintain the ferromagnetic coupling. We also analyze the optimal chain strength variations considering different minor embeddings of the same instance. This experimental study suggests that the chain strength can be optimized for each instance. We design a heuristic that optimizes the chain strength using a very low number of shots during the pre-processing step. This heuristic outperforms the default method used to initialize the chain strength on D-Wave systems, increasing the quality of the best solution by up to 17.2% for tested instances on the max-cut problem.
Create account to get full access
Overview
- This paper presents a simple heuristic to set the chain strengths for quantum annealers, which are a type of quantum computing hardware.
- Chain strengths are an important parameter in minor embedding, a technique used to map problems onto the limited hardware of quantum annealers.
- The authors show that their heuristic outperforms existing methods and can improve the performance of quantum annealers on a variety of optimization problems.
Plain English Explanation
Quantum annealers are a type of quantum computer that can be used to solve optimization problems. However, these devices have limited hardware capabilities, so a technique called "minor embedding" is used to map the problem onto the available hardware.
One key parameter in minor embedding is the "chain strength," which determines how tightly the qubits (the basic units of quantum information) are coupled together. Setting the right chain strength is important for the performance of the quantum annealer.
In this paper, the authors propose a simple heuristic to automatically set the chain strengths. Their method is easy to implement and outperforms existing approaches. By using the right chain strengths, the quantum annealer can find better solutions to optimization problems more efficiently.
The authors demonstrate the effectiveness of their heuristic on a variety of optimization problems, showing that it can significantly improve the performance of quantum annealers compared to other techniques for setting chain strengths.
Technical Explanation
The authors present a simple heuristic to set the chain strengths for quantum annealers, a type of quantum computing hardware. Chain strengths are an important parameter in the minor embedding process, which is used to map problems onto the limited hardware of quantum annealers.
The heuristic works by estimating the required chain strength based on the characteristics of the problem being solved, such as the degree of connectivity in the problem graph. The authors show that this heuristic outperforms existing methods for setting chain strengths, such as using a fixed value or adaptively adjusting the strength.
The authors evaluate their heuristic on a range of optimization problems, including hybrid quantum-classical algorithms and post-variational quantum neural networks. They demonstrate that their method can significantly improve the performance of quantum annealers, leading to better solutions found more efficiently.
Critical Analysis
The authors present a well-designed and thorough evaluation of their heuristic for setting chain strengths in quantum annealers. They compare their method to several existing approaches and show clear performance improvements across a diverse set of optimization problems.
One potential limitation of the study is that it focuses on a specific type of quantum annealer hardware, the D-Wave quantum annealer. It would be interesting to see if the heuristic also performs well on other quantum annealing platforms or even on different types of quantum computers, such as gate-based quantum computers.
Additionally, the authors do not discuss the computational complexity or runtime of their heuristic compared to the other methods. This information would be useful for understanding the practical implications of using the heuristic in real-world applications.
Overall, the paper makes a valuable contribution to the field of quantum computing by providing a simple yet effective technique for improving the performance of quantum annealers on optimization problems. The findings could have important implications for the practical use of quantum annealers in areas such as logistics, finance, and machine learning.
Conclusion
This paper presents a simple heuristic for setting the chain strengths in quantum annealers, a type of quantum computing hardware. The authors show that their method outperforms existing approaches and can significantly improve the performance of quantum annealers on a variety of optimization problems.
The heuristic is easy to implement and could have important practical implications for the use of quantum annealers in real-world applications. The findings of this study contribute to the ongoing efforts to make quantum computing more accessible and practical for solving complex problems in fields such as logistics, finance, and machine learning.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
Benchmarking Quantum Annealers with Near-Optimal Minor-Embedded Instances
Valentin Gilbert, Julien Rodriguez, Stephane Louise
0
0
Benchmarking Quantum Process Units (QPU) at an application level usually requires considering the whole programming stack of the quantum computer. One critical task is the minor-embedding (resp. transpilation) step, which involves space-time overheads for annealing-based (resp. gate-based) quantum computers. This paper establishes a new protocol to generate graph instances with their associated near-optimal minor-embedding mappings to D-Wave Quantum Annealers (QA). This set of favorable mappings is used to generate a wide diversity of optimization problem instances. We use this method to benchmark QA on large instances of unconstrained and constrained optimization problems and compare the performance of the QPU with efficient classical solvers. The benchmark aims to evaluate and quantify the key characteristics of instances that could benefit from the use of a quantum computer. In this context, existing QA seem best suited for unconstrained problems on instances with densities less than $10%$. For constrained problems, the penalty terms used to encode the hard constraints restrict the performance of QA and suggest that these QPU will be less efficient on these problems of comparable size.
5/3/2024
An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem
Alessandro Gherardi, Alberto Leporati
0
0
Quantum annealers can be used to solve many (possibly NP-hard) combinatorial optimization problems, by formulating them as quadratic unconstrained binary optimization (QUBO) problems or, equivalently, using the Ising formulation. In this paper we analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. Due to the embedding limit of 164 nodes imposed by the anneler, we conducted a study on graph decomposition to enable instance embedding. We thus propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes. We then statistically analysed how these variables affect the quality of the solutions found by the quantum annealer. The results of our investigation include recommendations on ratio and density limits not to be exceeded, as well as a series of precautions and a priori analyses to be carried out in order to maximise the probability of obtaining a solution close to the optimum.
6/13/2024
🛠️
Design and execution of quantum circuits using tens of superconducting qubits and thousands of gates for dense Ising optimization problems
Filip B. Maciejewski, Stuart Hadfield, Benjamin Hall, Mark Hodson, Maxime Dupont, Bram Evert, James Sud, M. Sohaib Alam, Zhihui Wang, Stephen Jeffrey, Bhuvanesh Sundar, P. Aaron Lott, Shon Grabbe, Eleanor G. Rieffel, Matthew J. Reagor, Davide Venturelli
0
0
We develop a hardware-efficient ansatz for variational optimization, derived from existing ansatze in the literature, that parametrizes subsets of all interactions in the Cost Hamiltonian in each layer. We treat gate orderings as a variational parameter and observe that doing so can provide significant performance boosts in experiments. We carried out experimental runs of a compilation-optimized implementation of fully-connected Sherrington-Kirkpatrick Hamiltonians on a 50-qubit linear-chain subsystem of Rigetti Aspen-M-3 transmon processor. Our results indicate that, for the best circuit designs tested, the average performance at optimized angles and gate orderings increases with circuit depth (using more parameters), despite the presence of a high level of noise. We report performance significantly better than using a random guess oracle for circuits involving up to approx 5000 two-qubit and approx 5000 one-qubit native gates. We additionally discuss various takeaways of our results toward more effective utilization of current and future quantum processors for optimization.
5/3/2024
Identifying Bottlenecks of NISQ-friendly HHL algorithms
Marc Andreu Marfany, Alona Sakhnenko, Jeanette Miriam Lorenz
0
0
Quantum computing promises enabling solving large problem instances, e.g. large linear equation systems with HHL algorithm, once the hardware stack matures. For the foreseeable future quantum computing will remain in the so-called NISQ era, in which the algorithms need to account for the flaws of the hardware such as noise. In this work, we perform an empirical study to test scaling properties and directly related noise resilience of the the most resources-intense component of the HHL algorithm, namely QPE and its NISQ-adaptation Iterative QPE. We explore the effectiveness of noise mitigation techniques for these algorithms and investigate whether we can keep the gate number low by enforcing sparsity constraints on the input or using circuit optimization techniques provided by Qiskit package. Our results indicate that currently available noise mitigation techniques, such as Qiskit readout and Mthree readout packages, are insufficient for enabling results recovery even in the small instances tested here. Moreover, our results indicate that the scaling of these algorithms with increase in precision seems to be the most substantial obstacle. These insights allowed us to deduce an approximate bottleneck for algorithms that consider a similar time evolution as QPE. Such observations provide evidence of weaknesses of such algorithms on NISQ devices and help us formulate meaningful future research directions.
6/11/2024