Domain wall encoding of discrete variables for quantum annealing and QAOA

Abstract

In this paper I propose a new method of encoding discrete variables into Ising model qubits for quantum optimization. The new method is based on the physics of domain walls in one dimensional Ising spin chains. I find that these encodings and the encoding of arbitrary two variable interactions is possible with only two body Ising terms. Following on from similar results for the `one hot' method of encoding discrete variables [Hadfield et. al. Algorithms 12.2 (2019): 34] I also demonstrate that it is possible to construct two body mixer terms which do not leave the logical subspace, an important consideration for optimising using the quantum alternating operator ansatz (QAOA). I additionally discuss how, since the couplings in the domain wall encoding only need to be ferromagnetic and therefore could in principle be much stronger than anti-ferromagnetic couplers, application specific quantum annealers for discrete problems based on this construction may be beneficial. Finally, I compare embedding for synthetic scheduling and colouring problems with the domain wall and one hot encodings on two graphs which are relevant for quantum annealing, the chimera graph and the Pegasus graph. For every case I examine I find a similar or better performance from the domain wall encoding as compared to one hot, but this advantage is highly dependent on the structure of the problem. For encoding some problems, I find an advantage similar to the one found by embedding in a Pegasus graph compared to embedding in a chimera graph.

17 pages 9 figures, code, including simple python module for domain wall encoding, available at https://doi.org/10.15128/r27d278t029 additional acknowledgement and discussion about efficiency of encoding added in v2; changes in response to referees added in v3, title change from 'integer' to 'discrete' in v3. accepted in IoP quantum science and technology, v4 matches accepted version

References in corpus (9)

• Spatial search by quantum walk
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
• Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
• Forecasting financial crashes with quantum computing
• On the qubit routing problem
• Mediated tunable coupling of flux qubits
• A quantum walk assisted approximate algorithm for bounded NP optimisation problems

Cited by in corpus (48)

• Quantum Annealing for Industry Applications: Introduction and Review
• Expanding the horizon of automated metamaterials discovery via quantum annealing
• Resource-efficient digital quantum simulation of $d$-level systems for photonic, vibrational, and spin-$s$ Hamiltonians
• Learning quantum data with the quantum Earth Mover's distance
• Error mitigation for variational quantum algorithms through mid-circuit measurements
• Basic Elements for Simulations of Standard Model Physics with Quantum Annealers: Multigrid and Clock States
• Quantum Shuttle: Traffic Navigation with Quantum Computing
• Quantum Computing for Quantum Tunnelling
• Application of QUBO solver using black-box optimization to structural design for resonance avoidance
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Quantum approximate optimization algorithm for qudit systems
• Understanding domain-wall encoding theoretically and experimentally
• Quantum Optimisation of Complex Systems with a Quantum Annealer
• HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• Recommending Solution Paths for Solving Optimization Problems with Quantum Computing
• Quantum algorithms for scientific computing
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Observing the fate of the false vacuum with a quantum laboratory
• Fluctuation guided search in quantum annealing
• Effectiveness of quantum annealing for continuous-variable optimization
• Variational Quantum Multi-Objective Optimization
• Controller-based Energy-Aware Wireless Sensor Network Routing using Quantum Algorithms
• Error measurements for a quantum annealer using the one-dimensional Ising model with twisted boundaries
• Towards an Automatic Framework for Solving Optimization Problems with Quantum Computers
• Dual-Matrix Domain-Wall: A Novel Technique for Generating Permutations by QUBO and Ising Models with Quadratic Sizes
• Rapid quantum approaches for combinatorial optimisation inspired by optimal state-transfer
• Simulation of a feedback-based algorithm for quantum optimization for a realistic neutral atom system with an optimized small-angle controlled-phase gate
• On connectivity-dependent resource requirements for digital quantum simulation of $d$-level particles
• Quantum optimization with linear Ising penalty functions for customer data science
• QUBO.jl: A Julia Ecosystem for Quadratic Unconstrained Binary Optimization
• Quantum Algorithm for Smoothed Particle Hydrodynamics
• Optimization of ionic configurations in battery materials by quantum annealing
• Quantum annealer accelerates the variational quantum eigensolver in a triple-hybrid algorithm
• Linearizing Binary Optimization Problems Using Variable Posets for Ising Machines
• Improving the efficiency of quantum annealing with controlled diagonal catalysts
• Entropy Computing, A Paradigm for Optimization in Open Photonic Systems
• Multi-disk clutch optimization using quantum annealing
• Mapping State Transition Susceptibility in Quantum Annealing
• Inequality constraints in variational quantum circuits with qudits
• Performance of Domain-Wall Encoding for Quantum Annealing
• Quantum-computing within a bosonic context: Assessing finite basis effects on prototypical vibrational Hamiltonian spectra
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• Variational simulation of higher-spin systems on qubit-based quantum simulators
• Quick design of feasible tensor networks for constrained combinatorial optimization
• Quantum annealing and condensed matter physics