In this article, we experimentally test the performance of the recently proposed domain-wall encoding of discrete variables Chancellor, 2019, on Ising model flux qubit quantum annealers. We compare this encoding with the traditional one-hot methods and find that they outperform the one-hot encoding for three different problems at different sizes of both the problem and the variables. From these results, we conclude that the domain-wall encoding yields superior performance against a variety of metrics furthermore; we do not find a single metric by which one hot performs better. We even find that a 2000Q quantum annealer with a drastically less connected hardware graph but using the domain-wall encoding can outperform the next-generation Advantage processor if that processor uses one-hot encoding.
In this article, we experimentally test the performance of the recently proposed domain-wall encoding of discrete variables Chancellor, 2019, on Ising model flux qubit quantum annealers. We compare this encoding with the traditional one-hot methods and find that they outperform the one-hot encoding for three different problems at different sizes of both the problem and the variables. From these results, we conclude that the domain-wall encoding yields superior performance against a variety of metrics furthermore; we do not find a single metric by which one hot performs better. We even find that a 2000Q quantum annealer with a drastically less connected hardware graph but using the domain-wall encoding can outperform the next-generation Advantage processor if that processor uses one-hot encoding.
We analyse 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 with 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. This article is part of the theme issue 'Quantum annealing and computation: challenges and perspectives'.
Abstract In this paper I propose a new method of encoding discrete variables into Ising model qubits for quantum optimisation. 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 2019 Algorithms 12 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. 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.
To tackle combinatorial optimization problems using an Ising machine, the objective function and constraints must be mapped onto a quadratic unconstrained binary optimization (QUBO) model. While QUBO involves binary variables, combinatorial optimization problems frequently include integer variables, which require encoding by binary variables. This process, known as binary-integer encoding, includes various methods, one of which is domain-wall encoding - a recently proposed approach. Experiments on a quantum annealing machine have demonstrated that domain-wall encoding outperforms the commonly used one-hot encoding in terms of objective function value and the probability of obtaining the optimal solution. In a digital Ising machine, domain-wall encoding required less computation time to reach optimal solutions compared to one-hot encoding. However, its practical effectiveness in digital Ising machines remains unclear. To address this uncertainty, the performance of one-hot and domain-wall encoding methods was evaluated on a digital Ising machine using the quadratic knapsack problem (QKP). The comparison focused on the dependency of penalty coefficient and sensitivity to computation time. Domain-wall encoding demonstrated a higher feasible solution rate when relative penalty coefficients for the two constraint terms were adjusted, a strategy not commonly used in previous studies. Additionally, domain-wall encoding obtained higher performance practical evaluation metrics for QKPs with large knapsack capacities compared to one-hot encoding. Furthermore, it was observed to be more sensitive to computation time than one-hot encoding.
The application of quantum annealing to the optimization of continuous-variable functions is a relatively unexplored area of research. We test the performance of quantum annealing applied to a one-dimensional continuous-variable function with a rugged energy landscape. After domain-wall encoding to map a continuous variable to discrete Ising variables, we first benchmark the performance of the real hardware, the D-Wave 2000Q, against several state-of-the-art classical optimization algorithms designed for continuous-variable problems to find that the D-Wave 2000Q matches the classical algorithms in a limited domain of computation time. Beyond this domain, classical global optimization algorithms outperform the quantum device. Next we examine several optimization algorithms that are applicable to the Ising formulation of the problem, such as the time-evolving block decimation (TEBD) to simulate ideal coherent quantum annealing, simulated annealing, simulated quantum annealing, and spin-vector Monte Carlo. The data show that TEBD's coherent quantum annealing achieves far better results than the other approaches, demonstrating the effectiveness of coherent tunneling. From these two types of benchmarks, we conclude that the hardware realization of quantum annealing has the potential to significantly outperform the best classical algorithms if thermal noise and other imperfections are sufficiently suppressed and the device operates coherently, as demonstrated in recent short-time quantum simulations.
QUBO is the input language of quantum computers based on quantum annealing such as the D-Wave systems and of the "quantum-inspired" dedicated hardware such as Fujitsu’s Digital Annealing Unit. We propose a new way to represent integer variables in QUBO together with constraints on those variables by using unary/domain-wall encoding in order to solve constrained optimization problem by quantum annealing. We detail in particular how to encode permutation constraints on integers within the unary/domain-wall encoding scheme, as these constraints are omnipresent in complex combinatorial problems. This new encoding in QUBO is interesting in the context of quantum annealing because it minimizes interactions between variables, and therefore connections needed between qubits in hardware. When compared to the usual one-hot encoding of integers in QUBO, we show than the new encoding scheme divides by nearly a factor 2 the number of connections between qubits for complex problems involving permutation constraints and makes it possible to cope with larger problem instances on current quantum and quantum-inspired hardware.
Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.