Understanding domain-wall encoding theoretically and experimentally

Abstract

We analyze the method of encoding pairwise interactions of higher-than-binary discrete variables (these models are sometimes referred to as discrete quadratic models) into binary variables based on domain walls on one dimensional Ising chains. We discuss how this is relevant to quantum annealing, but also many gate model algorithms such as VQE and QAOA. We theoretically show that for problems of practical interest for quantum computing and assuming only quadratic interactions are available between the binary variables, it is not possible to have a more efficient general encoding in terms of number of binary variables per discrete variable. We furthermore use a D-Wave Advantage 1.1 flux qubit quantum annealing computer to show that the dynamics effectively freeze later for a domain-wall encoding compared to a traditional one-hot encoding. This second result could help explain the dramatic performance improvement of domain wall over one hot which has been seen in a recent experiment on D-Wave hardware. This is an important result because usually problem encoding and the underlying physics are considered separately, our work suggests that considering them together may be a more useful paradigm. We argue that this experimental result is also likely to carry over to a number of other settings, we discuss how this has implications for gate-model and quantum-inspired algorithms.

15 pages, 16 figures, typo in metadata fixed in v2, referee requested changes in v3, accepted in Royal Society Philosophical Transactions A, current version matches author accepted manuscript

References in corpus (33)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• A Quantum Approximate Optimization Algorithm
• Cosmological Experiments in Condensed Matter Systems
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• The simplest quantum model supporting the Kibble-Zurek mechanism of topological defect production: Landau-Zener transitions from a new perspective
• Experimental signature of programmable quantum annealing
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Resource-efficient digital quantum simulation of $d$-level systems for photonic, vibrational, and spin-$s$ Hamiltonians
• Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• Optimal Protocols in Quantum Annealing and QAOA Problems
• Domain wall encoding of discrete variables for quantum annealing and QAOA
• Detecting Multiple Communities Using Quantum Annealing on the D-Wave System
• Scaling and diabatic effects in quantum annealing with a D-Wave device
• Climbing Mount Scalable: Physical-Resource Requirements for a Scalable Quantum Computer
• Temperature scaling law for quantum annealing optimizers
• Error mitigation for variational quantum algorithms through mid-circuit measurements
• A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
• Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
• Stabilisers as a design tool for new forms of Lechner-Hauke-Zoller Annealer
• Quantum Computing for Quantum Tunnelling
• Quantum Shuttle: Traffic Navigation with Quantum Computing
• Implementation of a Hybrid Classical-Quantum Annealing Algorithm for Logistic Network Design
• Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
• Two quantum Ising algorithms for the Shortest Vector Problem: one for now and one for later
• Search range in experimental quantum annealing
• Practical designs for permutation symmetric problem Hamiltonians on hypercubes
• Fluctuation guided search in quantum annealing
• A Novel Algebraic Geometry Compiling Framework for Adiabatic Quantum Computations
• Graver Bases via Quantum Annealing with Application to Non-Linear Integer Programs
• Experimental Freezing of mid-Evolution Fluctuations with a Programmable Annealer

Cited by in corpus (13)

• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• Quantum algorithms for scientific computing
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Error measurements for a quantum annealer using the one-dimensional Ising model with twisted boundaries
• Dual-Matrix Domain-Wall: A Novel Technique for Generating Permutations by QUBO and Ising Models with Quadratic Sizes
• Quantum optimization with linear Ising penalty functions for customer data science
• Quantum Algorithm for Smoothed Particle Hydrodynamics
• Mapping State Transition Susceptibility in Quantum Annealing
• Multi-disk clutch optimization using quantum annealing
• Quantum Software Ecosystem Design
• Variational simulation of higher-spin systems on qubit-based quantum simulators
• Quantum annealing and condensed matter physics