Quantum Annealing (QA) is a quantum computing paradigm for solving combinatorial optimization problems formulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. An essential step in QA is minor embedding, which maps the problem graph onto the sparse topology of the quantum processor and then adjusts the problem weights. The process of mapping the problem variables to the hardware is computationally expensive and scales poorly with increasing problem size and hardware complexity. Existing heuristics are often developed for specific problem graphs or hardware topologies and are difficult to generalize. To address this limitation, we explore the use of machine learning methods, which would allow a much greater degree of flexibility, in particular of Reinforcement Learning (RL). RL offers a promising alternative by treating minor embedding as a sequential decision-making problem, where an agent learns to construct minor embeddings by iteratively mapping the problem variables to the hardware qubits. We propose a RL-based approach to minor embedding using a Proximal Policy Optimization agent, testing its ability to embed both fully connected and randomly generated problem graphs on two hardware topologies, Chimera and Zephyr. The results show that our agent consistently produces valid minor embeddings even when they span over more than a thousand qubits, in particular on the more modern Zephyr topology. Our proposed approach is also able to scale to moderate problem sizes and adapts well to different graph structures, highlighting RL’s potential as a flexible and general-purpose framework for minor embedding in QA but also pointing to limitations that will need to be addressed, for example in reducing the number of qubits required.
This paper investigates the application of quantum annealing algorithms to the field of topological optimization, specifically focusing on a probabilistic approach. Traditional topological optimization relies on iterative refinement of a mesh, often computationally expensive. We propose a novel method leveraging the quantum annealing algorithm's inherent probabilistic search capabilities, combined with topological structural information, to achieve more efficient solutions for complex optimization problems. The core concept involves translating the optimization problem into a search problem within the space of possible topological structures. The quantum annealing algorithm then explores this space probabilistically, guided by the topological constraints, with the goal of identifying the optimal topology. This approach aims to reduce the computational burden associated with conventional iterative methods and potentially unlock solutions that are inaccessible through classical optimization techniques. The presented framework is theoretically grounded and offers a promising avenue for future research in hybrid quantum-classical optimization. The key performance indicator for this approach is the convergence rate and the quality of the solutions obtained compared to traditional methods. The algorithm's success depends heavily on the effective encoding of the problem's constraints into the topology search space.
Abstract As a typical quantum computing algorithm, quantum annealing is widely used in the optimization of glass-like problems to find the best solution. However, the optimization problems in constrained complex systems usually involve topological structures, and the performance of the quantum annealing algorithm is still largely unknown. Here, we take an Ising system as a typical example with local constraints accompanied by intrinsic topological properties that can be implemented on quantum computing platforms such as the D-wave machine, and study the effectiveness of the quantum annealing algorithm in its optimization and compare it with that of the thermal annealing. We find that although conventional quantum annealing is difficult for the optimization of constrained topological problems, a generalized algorithm --- the sweeping quantum annealing method --- can be designed and solve the problem with better efficiency than both conventional quantum and thermal annealing algorithms. The sweeping quantum annealing algorithm, therefore, opens up a promising avenue for quantum computing of constrained problems and can be readily employed on the optimizations in quantum material design, engineering, and even social sciences.
Quantum Annealing (QA) offers a promising framework for solving NP-hard optimization problems, but its effectiveness is constrained by the topology of the underlying quantum hardware. Solving an optimization problem
P via QA involves a hardware-aware circuit compilation which requires representing
P as a graph
GP and embedding it into the hardware connectivity graph
GQ that defines how qubits connect to each other in a QA-based quantum processing unit (QPU).
Minor Embedding (ME) is a possible operational form of this hardware-aware compilation. ME heuristically builds a map that associates each node of
GP -- the logical variables of
P -- to a chain of adjacent nodes in
GQ by means of one of its minors, so that the arcs of
GP are preserved as physical connections among qubits in
GQ.
The static topology of hardwired qubits can clearly lead to inefficient compilations because
GQ cannot be a clique, currently. We propose a methodology and a set of criteria to evaluate how the hardware topology
GQ can negatively affect the embedded problem, thus making the quantum optimization more sensible to noise.
We evaluate the result of ME across two QPU topologies: Zephyr graphs (used in current D-Wave systems) and Havel-Hakimi graphs, which allow controlled variation of the average node degree. This enables us to study how the ratio `number of nodes/number of incident arcs per node' affects ME success rates to map
GP into a minor of
GQ.
Our findings, obtained through ME executed on classical, i.e. non-quantum, architectures, suggest that Havel-Hakimi-based topologies, on average, require shorter qubit chains in the minor of
GP, exhibiting smoother scaling of the largest embeddable
GP as the QPU size increases. These characteristics indicate their potential as alternative designs for QA-based QPUs.