© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2409.12240

Large-scale quantum annealing simulation with tensor networks and belief propagation

I. A. Luchnikov, Egor Tiunov, Tobias Haug, Leandro Aolita

Published Sep 18, 2024• 0 citations

Abstract

Quantum annealing and quantum approximate optimization algorithms hold a great potential to speed-up optimization problems. This could be game-changing for a plethora of applications. Yet, in order to hope to beat classical solvers, quantum circuits must scale up to sizes and performances much beyond current hardware. In that quest, intense experimental effort has been recently devoted to optimizations on 3-regular graphs, which are computationally hard but experimentally relatively amenable. However, even there, the amount and quality of quantum resources required for quantum solvers to outperform classical ones is unclear. Here, we show that quantum annealing for 3-regular graphs can be classically simulated even at scales of 1000 qubits and 5000000 two-qubit gates with all-to-all connectivity. To this end, we develop a graph tensor-network quantum annealer (GTQA) able of high-precision simulations of Trotterized circuits of near-adiabatic evolutions. Based on a recently proposed belief-propagation technique for tensor canonicalization, GTQA is equipped with re-gauging and truncation primitives that keep approximation errors small in spite of the circuits generating significant amounts of entanglement. As a result, even with a maximal bond dimension as low as 4, GTQA produces solutions competitive with those of state-of-the-art classical solvers. For non-degenerate instances, the unique solution can be read out from the final reduced single-qubit states. In contrast, for degenerate problems, such as MaxCut, we introduce an approximate measurement simulation algorithm for graph tensor-network states. On one hand, our findings showcase the potential of GTQA as a powerful quantum-inspired optimizer. On the other hand, they considerably raise the bar required for experimental demonstrations of quantum speed-ups in combinatorial optimizations.

DOI: 10.48550/arxiv.2409.12240

Related papers

Belief Propagation-based Disentanglers for Tensor Network State Preparation

Tomasz Szołdra, Peter Schmelcher

We develop a quantum circuit synthesis method for preparing a class of tensor network states. The scheme applies to states tractable with belief propagation (BP), a tensor network gauging scheme which recently allowed for classical simulations at large scales. The problem is reduced to independent, strictly local, classical variational optimizations: each nearest-neighbor two-qubit "disentangler" gate minimizes the entropy defined on an edge. Disentanglers drive the state to a product state and their Hermitian conjugate prepares the target. Each disentangling layer has depth at most $z+1$ (with $z$ the maximal number of nearest neighbors per site), the optimization has no barren plateaus, and the bond dimension stays bounded. As a demonstration, with only $3$-$5$ disentangling layers we prepare a $102$-qubit tree tensor network encoding a $17$-dimensional normal distribution and the transverse-field Ising model ground states on a $64$- to $127$-qubit heavy-hex lattice with fidelities of order $0.9-0.999$. The method opens new possibilities for quantum applications by transferring classical tensor network states onto hardware.

quant-pharXiv:2608.21902•Aug 25, 2026•0 citations

Quantum annealing for neural network optimization problems: A new approach via tensor network simulations

Guglielmo Lami, Pietro Torta, Giuseppe E. Santoro +1 more

Here, we focus on the problem of minimizing complex classical cost functions associated with prototypical discrete neural networks, specifically the paradigmatic Hopfield model and binary perceptron. We show that the adiabatic time evolution of QA can be efficiently represented as a suitable Tensor Network. This representation allows for simple classical simulations, well-beyond small sizes amenable to exact diagonalization techniques. We show that the optimized state, expressed as a Matrix Product State (MPS), can be recast into a Quantum Circuit, whose depth scales only linearly with the system size and quadratically with the MPS bond dimension. This may represent a valuable starting point allowing for further circuit optimization on near-term quantum devices.

arXiv:2208.14468•SciPost Physics•May 17, 2023•17 citations

Large-scale quantum approximate optimization on nonplanar graphs with machine learning noise mitigation

Stefan H. Sack, Daniel J. Egger

Quantum computers are increasing in size and quality but are still very noisy. Error mitigation extends the size of the quantum circuits that noisy devices can meaningfully execute. However, state-of-the-art error mitigation methods are hard to implement and the limited qubit connectivity in superconducting qubit devices restricts most applications to the hardware's native topology. Here we show a quantum approximate optimization algorithm (QAOA) on nonplanar random regular graphs with up to 40 nodes enabled by a machine learning-based error mitigation. We use a swap network with careful decision-variable-to-qubit mapping and a feed-forward neural network to optimize a depth-two QAOA on up to 40 qubits. We observe a meaningful parameter optimization for the largest graph which requires running quantum circuits with 958 two-qubit gates. Our paper emphasizes the need to mitigate samples, and not only expectation values, in quantum approximate optimization. These results are a step towards executing quantum approximate optimization at a scale that is not classically simulable. Reaching such system sizes is key to properly understanding the true potential of heuristic algorithms like QAOA. Published by the American Physical Society 2024

arXiv:2307.14427•Physical Review Research•Mar 1, 2024•39 citations

Efficient Combinatorial Optimization Using Quantum Annealing

Hristo N. Djidjev, Guillaume Chapuis, Georg Hahn +1 more

The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.

arXiv:1801.08653•Jan 26, 2018•27 citations

Multi-Objective Optimization with Quantum-Annealing-Inspired Algorithms

Xian-Zhe Tao, Pavel Mosharev, Zhaofeng Su +1 more

Combinatorial optimization is widely regarded as a primary application for near-term quantum processors, although a definitive demonstration of the practical quantum advantage remains elusive. Recent studies have reported that both gate-based quantum circuits and quantum annealers can outperform state-of-the-art classical heuristics on multi-objective optimization (MO-MaxCut) problems. However, these studies did not fully account for the substantial pre- and post-processing overheads intrinsic to quantum solvers, leading to incomplete comparisons between quantum and classical approaches. In this work, we re-examine the same benchmark suite using GPU-based quantum-annealing-inspired algorithms (QAIAs), which, analogously to quantum processors, generate probabilistic samples and thus serve as formidable classical contenders. Our results show that QAIAs can sample candidate solutions approximately two orders of magnitude faster than previously studied quantum processors. In terms of end-to-end runtime, QAIAs also surpass industry-leading classical solvers, thereby establishing themselves as the superior performers among the quantum and classical solvers evaluated thus far for the MO-MaxCut instances.

quant-pharXiv:2604.26477•Apr 30, 2026•0 citations

Simulation of quantum computing on classical supercomputers with tensor-network edge cutting

Ya-Qian Zhao, Ren-Gang Li, Jin-Zhe Jiang +6 more

Simulation of quantum computing on supercomputers is a significant research topic, which plays a vital role in quantum algorithm verification, error-tolerant verification, and other applications. Tensor-network contraction based on density matrix is an important single-amplitude simulation strategy, but it is hard to execute on the distributed computing systems. In this paper, we studied the problem in detail, and propose a scheme based on cutting edges of undirected graphs. This scheme cuts edges of undirected graphs with large tree width to obtain many undirected subgraphs with small tree width, and these subgraphs contracted on different computing cores. The contraction results of slave cores are summarized in the master node, which is consistent with the original tensor-network contraction. Thus, we can simulate the larger scale quantum circuit than single core. Moreover, it is an NP-hard problem to find the global optimum cutting edges, and we propose a search strategy based on a heuristic algorithm to approach it. In order to verify the effectiveness of our scheme, we conduct tests based on the quantum approximation optimization algorithm (QAOA) and Shor's algorithm, and it can simulate a 120-qubit three-regular QAOA algorithm on a 4096-core supercomputer, which greatly exceeds the simulation scale on a single core of 100 qubits.

arXiv:2010.14962•Physical Review A•Sep 2, 2021•14 citations

Quantum annealing and quantum approximate optimization algorithms hold a great potential to speed-up optimization problems. This could be game-changing for a plethora of applications. Yet, in order to hope to beat classical solvers, quantum circuits must scale up to sizes and performances much beyond current hardware. In that quest, intense experimental effort has been recently devoted to optimizations on 3-regular graphs, which are computationally hard but experimentally relatively amenable. However, even there, the amount and quality of quantum resources required for quantum solvers to outperform classical ones is unclear. Here, we show that quantum annealing for 3-regular graphs can be classically simulated even at scales of 1000 qubits and 5000000 two-qubit gates with all-to-all connectivity. To this end, we develop a graph tensor-network quantum annealer (GTQA) able of high-precision simulations of Trotterized circuits of near-adiabatic evolutions. Based on a recently proposed belief-propagation technique for tensor canonicalization, GTQA is equipped with re-gauging and truncation primitives that keep approximation errors small in spite of the circuits generating significant amounts of entanglement. As a result, even with a maximal bond dimension as low as 4, GTQA produces solutions competitive with those of state-of-the-art classical solvers. For non-degenerate instances, the unique solution can be read out from the final reduced single-qubit states. In contrast, for degenerate problems, such as MaxCut, we introduce an approximate measurement simulation algorithm for graph tensor-network states. On one hand, our findings showcase the potential of GTQA as a powerful quantum-inspired optimizer. On the other hand, they considerably raise the bar required for experimental demonstrations of quantum speed-ups in combinatorial optimizations.

We develop a quantum circuit synthesis method for preparing a class of tensor network states. The scheme applies to states tractable with belief propagation (BP), a tensor network gauging scheme which recently allowed for classical simulations at large scales. The problem is reduced to independent, strictly local, classical variational optimizations: each nearest-neighbor two-qubit "disentangler" gate minimizes the entropy defined on an edge. Disentanglers drive the state to a product state and their Hermitian conjugate prepares the target. Each disentangling layer has depth at most

z+1

(with

z

the maximal number of nearest neighbors per site), the optimization has no barren plateaus, and the bond dimension stays bounded. As a demonstration, with only

3

-

5

disentangling layers we prepare a

102

-qubit tree tensor network encoding a

17

-dimensional normal distribution and the transverse-field Ising model ground states on a

64

- to

127

-qubit heavy-hex lattice with fidelities of order

0.9-0.999

. The method opens new possibilities for quantum applications by transferring classical tensor network states onto hardware.

Here, we focus on the problem of minimizing complex classical cost functions associated with prototypical discrete neural networks, specifically the paradigmatic Hopfield model and binary perceptron. We show that the adiabatic time evolution of QA can be efficiently represented as a suitable Tensor Network. This representation allows for simple classical simulations, well-beyond small sizes amenable to exact diagonalization techniques. We show that the optimized state, expressed as a Matrix Product State (MPS), can be recast into a Quantum Circuit, whose depth scales only linearly with the system size and quadratically with the MPS bond dimension. This may represent a valuable starting point allowing for further circuit optimization on near-term quantum devices.

Quantum computers are increasing in size and quality but are still very noisy. Error mitigation extends the size of the quantum circuits that noisy devices can meaningfully execute. However, state-of-the-art error mitigation methods are hard to implement and the limited qubit connectivity in superconducting qubit devices restricts most applications to the hardware's native topology. Here we show a quantum approximate optimization algorithm (QAOA) on nonplanar random regular graphs with up to 40 nodes enabled by a machine learning-based error mitigation. We use a swap network with careful decision-variable-to-qubit mapping and a feed-forward neural network to optimize a depth-two QAOA on up to 40 qubits. We observe a meaningful parameter optimization for the largest graph which requires running quantum circuits with 958 two-qubit gates. Our paper emphasizes the need to mitigate samples, and not only expectation values, in quantum approximate optimization. These results are a step towards executing quantum approximate optimization at a scale that is not classically simulable. Reaching such system sizes is key to properly understanding the true potential of heuristic algorithms like QAOA. Published by the American Physical Society 2024

The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.

Combinatorial optimization is widely regarded as a primary application for near-term quantum processors, although a definitive demonstration of the practical quantum advantage remains elusive. Recent studies have reported that both gate-based quantum circuits and quantum annealers can outperform state-of-the-art classical heuristics on multi-objective optimization (MO-MaxCut) problems. However, these studies did not fully account for the substantial pre- and post-processing overheads intrinsic to quantum solvers, leading to incomplete comparisons between quantum and classical approaches. In this work, we re-examine the same benchmark suite using GPU-based quantum-annealing-inspired algorithms (QAIAs), which, analogously to quantum processors, generate probabilistic samples and thus serve as formidable classical contenders. Our results show that QAIAs can sample candidate solutions approximately two orders of magnitude faster than previously studied quantum processors. In terms of end-to-end runtime, QAIAs also surpass industry-leading classical solvers, thereby establishing themselves as the superior performers among the quantum and classical solvers evaluated thus far for the MO-MaxCut instances.

Simulation of quantum computing on supercomputers is a significant research topic, which plays a vital role in quantum algorithm verification, error-tolerant verification, and other applications. Tensor-network contraction based on density matrix is an important single-amplitude simulation strategy, but it is hard to execute on the distributed computing systems. In this paper, we studied the problem in detail, and propose a scheme based on cutting edges of undirected graphs. This scheme cuts edges of undirected graphs with large tree width to obtain many undirected subgraphs with small tree width, and these subgraphs contracted on different computing cores. The contraction results of slave cores are summarized in the master node, which is consistent with the original tensor-network contraction. Thus, we can simulate the larger scale quantum circuit than single core. Moreover, it is an NP-hard problem to find the global optimum cutting edges, and we propose a search strategy based on a heuristic algorithm to approach it. In order to verify the effectiveness of our scheme, we conduct tests based on the quantum approximation optimization algorithm (QAOA) and Shor's algorithm, and it can simulate a 120-qubit three-regular QAOA algorithm on a 4096-core supercomputer, which greatly exceeds the simulation scale on a single core of 100 qubits.