Recently, W. Lechner, P. Hauke, and P. Zoller [Sci. Adv. 1, e1500838 (2015)] have proposed a quantum annealing architecture, in which a classical spin glass with all-to-all pairwise connectivity is simulated by a spin glass with geometrically local interactions. We interpret this architecture as a classical error-correcting code, which is highly robust against weakly correlated bit-flip noise, and we analyze the code's performance using a belief-propagation decoding algorithm. Our observations may also apply to more general encoding schemes and noise models.
Recently, W. Lechner, P. Hauke, and P. Zoller [Sci. Adv. 1, e1500838 (2015)] have proposed a quantum annealing architecture, in which a classical spin glass with all-to-all pairwise connectivity is simulated by a spin glass with geometrically local interactions. We interpret this architecture as a classical error-correcting code, which is highly robust against weakly correlated bit-flip noise, and we analyze the code's performance using a belief-propagation decoding algorithm. Our observations may also apply to more general encoding schemes and noise models.
Quantum annealing (QA) has emerged as a promising candidate for fast solvers for combinatorial optimization problems (COPs) and has attracted the interest of many researchers. Since COP is logically encoded in the Ising interaction among spins, its realization necessitates a spin system with all-to-all connectivity, presenting technical challenges in the physical implementation of large-scale QA devices. W. Lechner, P. Hauke, and P. Zoller proposed a parity-encoding (PE) architecture consisting of an expanded spin system with only local connectivity among them to circumvent this difficulty in developing near-future QA devices. They suggested that this architecture not only alleviates implementation challenges and enhances scalability but also possesses intrinsic fault tolerance. This paper proposes a practical decoding method tailored to correlated spin-flip errors in spin readout of PE architecture. Our work is based on the close connection between PE architecture and classical low-density parity-check (LDPC) codes. We show that the bit-flip (BF) decoding algorithm can correct independent and identically distributed errors in the readout of the SLHZ system with comparable performance to the belief propagation (BP) decoding algorithm. Then, we show evidence that the proposed BF decoding algorithm can efficiently correct correlated spinflip errors by simulation. The result suggests that introducing post-readout BF decoding reduces the computational cost of QA using the PE architecture and improves the performance of global optimal solution search. Our results emphasize the importance of the proper selection of decoding algorithms to exploit the inherent fault tolerance potential of the PE architecture.
Lechner, Hauke, and Zoller proposed a parity-encoded spin-embedding scheme for quantum annealing (QA) with all-to-all connectivity to avoid the issue of limited connectivity in near-term QA hardware and to enable the implementation thereof using only geometrically local interactions between spins fabricated on the planar substrate. Nevertheless, the redundant encoding of logical information, i.e., using a large number of spins to embed the logical information, increases the computational cost and reduces the efficiency. In this study, we show through Monte Carlo simulation that this redundant encoding may be exploited to solve the problems of the inefficiency and computational cost of the parity-encoded scheme by incorporating appropriate decoding, namely classical post-processing, of the spins to retrieve the logical information. Our findings open up the possibility of parity-encoded schemes for realizing the QA with near-term quantum technologies.
Quantum annealing aims to exploit quantum mechanics to speed up the search for the solution to optimization problems. Most problems exhibit complete connectivity between the logical spin variables after they are mapped to the Ising spin Hamiltonian of quantum annealing. To account for hardware constraints of current and future physical quantum annealers, methods enabling the embedding of fully connected graphs of logical spins into a constant-degree graph of physical spins are therefore essential. Here, we compare the recently proposed embedding scheme for quantum annealing with all-to-all connectivity by Lechner, Hauke, and Zoller (LHZ) [Sci. Adv. 1, e1500838 (2015)] to the commonly used minor embedding (ME) scheme. Using both simulated quantum annealing and parallel tempering simulations, we find that for a set of instances randomly chosen from a class of fully connected, random Ising problems, the ME scheme outperforms the LHZ scheme when using identical simulation parameters, despite the fault tolerance of the latter to weakly correlated spin-flip noise. This result persists even after we introduce several decoding strategies for the LHZ scheme, including a minimum-weight decoding algorithm that results in substantially improved performance over the original LHZ scheme. We explain the better performance of the ME scheme in terms of more efficient spin updates, which allows it to better tolerate the correlated spin-flip errors that arise in our model of quantum annealing. Our results leave open the question of whether the performance of the two embedding schemes can be improved using scheme-specific parameters and new error correction approaches.
We propose a practical hybrid decoding scheme for the parity-encoding architecture. This architecture was first introduced by N. Sourlas [Phys. Rev. Lett. , 070601 (2005)] as a computational technique for tackling hard optimization problems, especially those modeled by spin systems such as the Ising model and spin glasses, and reinvented by W. Lechner, P. Hauke, and P. Zoller [Sci. Adv. , e1500838 (2015)] to develop quantum annealing devices. We study the specific model, called the SLHZ model, aiming to achieve a near-term quantum annealing device implemented solely through geometrically local spin interactions. Taking account of the close connection between the SLHZ model and a classical low-density parity-check (LDPC) code, two approaches can be chosen for the decoding: (1) finding the ground state of a spin Hamiltonian derived from the SLHZ model, which can be achieved via stochastic decoders such as a quantum annealer or a classical Monte Carlo sampler; or (2) using deterministic decoding techniques for the classical LDPC code, such as belief propagation and a bit-flip decoder. The proposed hybrid approach combines the two approaches by applying bit-flip decoding to the readout of the stochastic decoder based on the SLHZ model. We present simulations demonstrating that this approach can reveal the latent potential of the SLHZ model, realizing the soft-annealing concept proposed by Sourlas.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.