Distributed Variational Quantum Algorithm Achieves 1,000-Variable Combinatorial Optimisation Solutions

Combinatorial Optimisation Problems (COPs) present a significant challenge for current and near-future quantum computers due to limitations in qubit numbers! Researchers Yuhan Huang, Siyuan Jin, and Yichi Zhang, from The Hong Kong University of Science and Technology, alongside Qi Zhao, Jun Qi, and Qiming Shao, have developed a novel Distributed Variational Quantum Algorithm (DVQA) to tackle this issue! Their work overcomes the limitations of existing decomposition and compression methods by effectively preserving crucial inter-variable dependencies without demanding complex entanglement, a key innovation utilising truncated higher-order singular value decomposition! This approach not only enables the solution of remarkably large, 1,000-variable instances on existing hardware but also introduces a natural form of noise localisation, scaling errors with subsystem size rather than overall qubit count, and represents a substantial step towards practical, scalable quantum optimisation.

DVQA tackles large COPs with limited qubits by

Scientists are0.7%. ,iK Xi1i2. iK|i1⟩1 ⊗|i2⟩2 ⊗· · · ⊗|iK⟩K, where |ik⟩k = {0, ., 2nk −1} represents a basis state in the k-th subsystem, and Xi1i2. iK are the complex amplitudes! The tensor X represents the correlations among subsystems! However, directly handling X requires operations that scale exponentially with K, limiting scalability! To obtain a tractable yet expressive approximation, the HOSVD is applied to X, obtaining the physical state: |ψ⟩= X α Cα O k Uk(θk)|αk⟩k, X α C2 α = 1, where α = {α1, ., αK}, with {αk}k ∈{0, 1, ., Rk −1}, representing computational basis states in the k-th subsystem, Rk is the rank determined by T-HOSVD decomposition, and C is the amplitude tensor.

Simulating this quantum state generally requires inter-subsystem entanglement! However, under NISQ resource constraints, generating such entanglement can be prohibitive! Instead, a classical parameter tensor C is used to approximate the resulting inter-subsystem correlations and thereby capture the dominant quantum effects! In this representation, the virtual state is: |φ⟩= P α Cα N k Uk(θk)|αk⟩k! This representation retains global expressivity through the classical tensor C while enabling distributed evaluation on isolated NISQ devices.

Substituting Eqs. (2) and (4) into Eq. (1). Crucially, DVQA employs truncated higher-order singular value decomposition (T-HOSVD) to preserve the essential inter-variable dependencies, avoiding the loss of crucial global correlations often seen in conventional decomposition techniques. This innovative approach allows the algorithm to scale effectively without sacrificing solution quality! The study engineered a system where the cost Hamiltonian is divided into sub-Hamiltonians, each implemented on separate quantum circuits. Researchers then harnessed a trainable tensor network to capture the correlations between these circuits, effectively approximating inter-subsystem entanglement with classical parameters.

This distributed objective function synthesises global expectation values from local quantum measurements and tensor contractions, enabling efficient optimisation even with resource-constrained hardware. The team’s method achieves a natural form of noise localisation, where errors scale with subsystem size rather than the total qubit count, significantly improving robustness! Experiments employed simulations on instances of up to 1,000 variables, demonstrating state-of-the-art accuracy for both MaxCut and portfolio optimisation problems. To validate the algorithm on physical hardware, scientists implemented DVQA on the “Wu Kong” quantum computer, successfully tackling portfolio optimisation challenges.

Theoretical bounds were derived to confirm the algorithm’s robustness for p-local Hamiltonians, providing a solid foundation for its scalability. This work demonstrates a scalable, noise-resilient framework that significantly advances the timeline for practical quantum optimisation algorithms! Furthermore, the team’s approach enables the efficient solution of large-scale problems by approximating inter-subsystem correlations with a trainable tensor network. This technique represents a generalisation of bipartite decomposition to a multiparticle decomposition, offering a low-rank but efficient approximation of the original problem. A key innovation lies in DVQA’s use of truncated higher-order singular value decomposition, which effectively preserves relationships between variables without requiring extensive long-range entanglement, a common bottleneck in quantum computation! This technique facilitates noise localisation, meaning errors accumulate at the subsystem level rather than scaling with the total number of qubits, thereby improving both scalability and accuracy.

Theoretical analysis confirms the robustness of DVQA for Hamiltonians with limited interaction order, and experimental validation on the Wu Kong computer, using portfolio optimisation as a test case, demonstrates state-of-the-art performance. The findings represent a substantial advance in the field of quantum optimisation, offering a pathway towards practical applications on near-term quantum processors! By distributing the computational workload across smaller subsystems while retaining crucial inter-variable correlations, DVQA overcomes the challenges of limited qubit capacity and noise sensitivity that plague conventional approaches. The authors acknowledge a limitation in that the theoretical bounds apply specifically to Hamiltonians with low interaction order p, and future research will likely focus on extending the framework to handle more complex Hamiltonian structures. Further investigation into the algorithm’s performance on a wider range of problem instances and quantum hardware platforms is also anticipated.