Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.10772

Scaling Quantum Optimization to the Thousand-Qubit Scale with Distributed Quantum Sampling

Amana Liaqat, Ahmed Darwish, Stephen DiAdamo, Dan Holme, Kieran McDowall, Emre Sahin, Naeimeh Mohseni, Giorgio Cortiana, Corey O'Meara

On Aqora:Stephen DiAdamoStephen DiAdamo
quant-phcs.ETmath.OCSubmitted Oct 7, 2026• Announced Oct 9, 2026• 1 citation
arXivHTMLPDF

Abstract

The Minimum Birkhoff Decomposition (MBD) seeks a sparse weighted sum of matchings and is a challenging optimization problem with applications in network scheduling and energy trading. We scale a quantum-assisted decomposition method by combining single-layer QAOA sampling with Extended Fully-Corrective Frank-Wolfe (E-FCFW) optimization, spectral graph partitioning, and greedy feasibility repair. We demonstrate the pipeline on the 1,354-node PEGASE bus test case (representing a 1,354-bus transmission grid with 1,710 transmission lines), whose 1,710 edges define a native 1,710-variable matching optimization problem requiring 1,710 qubits in the unpartitioned encoding. Partitioning enables distributed execution on IBM superconducting quantum processors. The best reported hardware result uses a 50-qubit partition bound, while reducing partitions to 20 qubits degrades convergence in the partition-size comparison. Larger partitions are more demanding for matrix product state (MPS) simulation, and bond-dimension tests show that truncating quantum correlations reduces candidate quality. The results therefore motivate retaining a substantive quantum sampling task within each partition as the overall problem scales. On the PEGASE-1354 benchmark, repaired QAOA samples achieve lower residual decomposition error than both simulated annealing and uniform random sampling baselines, while spatial circuit packing reduces hardware execution time by approximately a factor of three. These results demonstrate that combining spectral partitioning, spatial circuit packing, and classical feasibility repair provides an executable path for deploying gate-based quantum sampling on thousand-variable constrained optimization problems on current hardware.

AI Summary

The paper asks whether partitioned quantum sampling can support sparse matching decompositions beyond a single processor’s width. It studies Minimum Birkhoff Decomposition: approximating a weighted graph by a small weighted sum of matchings. An Extended Fully-Corrective Frank–Wolfe solver combines a classical maximum-weight matching oracle with candidates from fixed-angle, single-layer QAOA. Spectral partitioning limits circuit width; local samples are stitched, greedily pruned into feasible matchings, and passed to cardinality-constrained classical weight optimization. Independent circuits are spatially packed on IBM Heron processors. Experiments use a synthetic 132-edge graph and the PEGASE-1354 transmission network, with 1,354 vertices and 1,710 edges—the latter requiring 1,710 qubits under the unpartitioned encoding. A 50-qubit partition bound produces 41 subgraphs. On PEGASE, unpacked hardware reaches normalized squared reconstruction error $1.11\times10^{-6}$ after 20 rounds; packed execution stops after 17 rounds at $1.58\times10^{-6}$ while reducing measured execution time approximately threefold. Repaired QAOA samples outperform the tested simulated-annealing and repaired-uniform baselines. Reducing partition width to 20 worsens convergence; MPS bond-dimension tests associate stronger truncation with poorer candidates. The comparisons use specified, not computationally matched, sampling budgets and do not establish quantum advantage or classical simulation hardness. Repair is essential to the reported convergence. Cut edges may remain unsampled, routing costs depend strongly on local topology, and support selection remains combinatorial. Exact decomposition on general graphs additionally requires matching-polytope membership, not merely double substochasticity. Broader benchmarking, strong classical-solver comparisons, and comprehensive runtime accounting remain future work.

Little sign of AI-generated textIncrementalMissing comparisonOverclaims

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Boosting Sparsity in Graph Decompositions with QAOA Sampling

George Pennington, Naeimeh Mohseni, Oscar Wallis +5 more

We study the problem of decomposing a graph into a weighted sum of a small number of matchings, a task that arises in network resource allocation problems such as peer-to-peer energy exchange. Computing such decompositions is challenging for classical algorithms, even for small instances. To address this problem, we propose E-FCFW, a hybrid quantum-classical algorithm based on the Fully-Corrective Frank-Wolfe (FCFW) algorithm that incorporates a matching-sampling subroutine. We design a QAOA version of this subroutine and benchmark it against classical approaches (random sampling and simulated annealing) on demand graphs derived from complete, bipartite, and heavy-hex topologies. The quantum subroutine is executed using the Qiskit Aer state-vector and MPS simulators and on IBM Kingston hardware (7-111 qubits). On complete and bipartite graphs with 6-10 nodes, E-FCFW with QAOA yields consistently sparser decompositions than the classical baselines, and even beats the best-known solution for one instance. On heavy-hex graphs with 50, 70 and 100 nodes, E-FCFW with QAOA outperforms the other methods in terms of approximation error, demonstrating performance on utility-scale quantum hardware. For the largest graphs (100 nodes) E-FCFW with QAOA performs much better when using MPS circuit simulation, compared to using quantum hardware. This indicates that at this scale, the performance is severely impacted by hardware noise.

arXiv:2509.10657•Sep 12, 2025•3 citations

Large-scale portfolio optimization on a trapped-ion quantum computer

Alejandro Gomez Cadavid, Ananth Kaushik, Pranav Chandarana +10 more

We present an end-to-end pipeline for large-scale portfolio selection with cardinality constraints and experimentally demonstrate it on trapped-ion quantum processors using hardware-aware decomposition. Building on RMT-based correlation-matrix denoising and community detection, we identify correlated asset groups and introduce a correlation-guided greedy splitting scheme that caps each cluster by the executable qubit budget. Each cluster defines a hardware-embeddable QUBO subproblem that we solve using bias-field digitized counterdiabatic quantum optimization (BF-DCQO), a non-variational method that avoids classical parameter-training loops. We recombine low-energy candidates into global portfolios and enforce feasibility with a two-stage post-processing routine: fast repair followed by a cardinality-preserving swap local search. We benchmark the workflow on a 250-asset universe taken from the S&P 500 and execute subproblems on a 64-qubit Barium development system similar to the forthcoming IonQ Tempo line. We observe that larger executable subproblem sizes reduce decomposition error and systematically improve final objective values and risk-return trade-offs relative to randomized baselines under identical post-processing. Overall, the results establish a hardware-tested route for scaling financial optimization problems, defined by a trade space in which executable problem size and circuit cost are balanced against the resulting solution quality.

quant-pharXiv:2602.23976•Mar 2, 2026•2 citations

Integrated error-suppressed pipeline for quantum optimization of nontrivial binary combinatorial optimization problems on gate-model hardware at the 156-qubit scale

Natasha Sachdeva, Gavin S. Hartnett, Smarak Maity +12 more

Abstract We introduce a novel hybrid quantum–classical variational optimization method for unconstrained binary combinatorial optimization problems on gate-model quantum computers, integrating a custom variational ansatz, staged feedback-based dual variational parameter update strategies, efficient parametric compilation, automated error suppression during hardware execution, and scalable O( n ) classical post-processing to correct for bitflip errors. Without this integrated approach, we show that standard circuit execution at scale produces output indistinguishable from random sampling, establishing the necessity of each pipeline component. We benchmark the method on IBM superconducting quantum computers for several optimization problems drawn from NP-hard problem classes, where the optimization is conducted on hardware with no use of classical simulation or prior knowledge of the solution. For Max-Cut on random regular graphs with topologies not matched to device connectivity, the method achieves approximation ratios (AR) of 100% for unweighted 3-regular graphs up to 156 nodes, weighted regular graphs up to 80 nodes, and weighted 7-regular graphs up 50 nodes. Applied to higher-order binary optimization, the method finds the ground state energy of 127- and 156-qubit spin-glass models matched to device topology with linear, quadratic, and cubic interaction terms, achieving ARs of at least 99.5% across all instances tested. The method consistently outperforms a classical local solver across all problems. Where published results on identical problem instances are available, our method demonstrates competitive or superior performance. These results demonstrate that an appropriately engineered variational approach enables gate-model quantum computers to produce high-quality solutions for binary optimization problems drawn from NP-hard problem classes at the 156-qubit scale, where naïve implementations are insufficient for good performance.

arXiv:2406.01743•New Journal of Physics•May 21, 2026•53 citations

Evaluating pVSQA for Large-Sized Constrained Optimization on Quantum Simulator

Takeru Ota, Tatsuhiko Shirai, Mikio Morita +3 more

This study investigates the graph partitioning problem as a constrained combinatorial optimization problem and evaluates the effectiveness of the Postprocessing Variationally Scheduled Quantum Algorithm$(\mathbf{p V S Q A})$on the instances of up to 30 qubits. We executed pVSQA using Fujitsu's highperformance quantum simulator in a single-node configuration and compared its performance with the conventional Quantum Approximate Optimization Algorithm (QAOA). Experimental results on various instances show that pVSQA consistently outperforms QAOA in terms of feasibility and optimality, successfully obtaining optimal solutions even for$\mathbf{3 0}$-qubit instances. The study also demonstrates that Fujitsu's quantum simulator is effective for the stable execution of large-scale quantum circuits.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Quantum Optimization Methods for the Generalized Traveling Salesman Problem

Maximilian Zorn, Melinda Braun, Michael Ertl +4 more

This paper studies quantum optimization baselines for the Generalized Traveling Salesman Problem (GTSP), a clustered routing problem that naturally models variant selection and sequencing problems under discrete alternatives. We propose a novel GTSP QUBO formulation focused on maintaining feasible solutions for quantum annealing, as well as a hardware-executable gate-based pipeline utilizing the Quantum Approximate Optimization Algorithm (QAOA). We implement a constrained QAOA variant using an XY-mixer, which preserves the stepwise Hamming weight in the ideal circuit model, while feasibility with respect to the full GTSP constraints is tracked explicitly during post-processing. We compare the two quantum optimization paradigms on problem instances from GTSPLIB, an established benchmark dataset, and validate against classical state-of-the-art solvers. To mitigate current quantum hardware size limitations, we further extend a preprocessing method to reduce the node count in instance clusters, constructing new NISQ-friendly instances from reduced subsets. Across all tested instances, quantum solvers often produce competitive solution quality when tested on smaller graphs, but exhibit higher runtimes and a sharp degradation in feasibility and scalability as instance size grows. Our evaluation highlights where quantum optimizers can already succeed and which algorithmic bottlenecks, like sampling rates, runtime issues, and other practical failure modes, remain as open problems.

quant-pharXiv:2604.25531•Apr 29, 2026•0 citations

SPLIT-Q: A Scalable Sequential Quantum Computing Framework for Coherent Controlled Islanding

Yuqi Jiang, Zhiding Liang, Qiang Guan +2 more

Growing integration of distributed energy resources increases power-system variability and uncertainty. During disturbances, these effects can intensify generation-load imbalances and cascading failures. Controlled islanding limits their propagation by partitioning a compromised grid into connected, electrically sustainable islands. However, classical methods face rapidly growing computational costs as network size and island count increase. Quantum optimization offers an alternative for exploring this combinatorial partition space. Yet monolithic quantum formulations encode all assignment decisions in one circuit, causing qubit demand and circuit complexity to scale with network size. In this study, a qubit-bounded sequential distributed quantum approximate optimization algorithm (QAOA) framework is proposed to tackle coherent controlled islanding under limited quantum resources. It formulates the optimization as boundary-conditioned regional quadratic unconstrained binary optimization (QUBO) subproblems that are solved sequentially within a fixed qubit budget. Thus, circuit width remains independent of network size, with aggregate quantum workload scaling linearly on bounded-degree networks. Evaluation covers eleven IEEE systems from 9 to 300 buses using IBM quantum computing resources, with Gurobi and monolithic QAOA as references. Across all systems, the framework recovers feasible Gurobi-optimal partitions under noise, confirming the resilience of its solution quality. The results further show that the proposed method substantially reduces quantum-resource demand and circuit complexity relative to monolithic QAOA, allowing large islanding problems to be addressed within current hardware limits. The proposed framework provides a feasible and scalable pathway for quantum optimization in large-scale power systems.

quant-pharXiv:2608.12711•Aug 14, 2026•0 citations
The Minimum Birkhoff Decomposition (MBD) seeks a sparse weighted sum of matchings and is a challenging optimization problem with applications in network scheduling and energy trading. We scale a quantum-assisted decomposition method by combining single-layer QAOA sampling with Extended Fully-Corrective Frank-Wolfe (E-FCFW) optimization, spectral graph partitioning, and greedy feasibility repair. We demonstrate the pipeline on the 1,354-node PEGASE bus test case (representing a 1,354-bus transmission grid with 1,710 transmission lines), whose 1,710 edges define a native 1,710-variable matching optimization problem requiring 1,710 qubits in the unpartitioned encoding. Partitioning enables distributed execution on IBM superconducting quantum processors. The best reported hardware result uses a 50-qubit partition bound, while reducing partitions to 20 qubits degrades convergence in the partition-size comparison. Larger partitions are more demanding for matrix product state (MPS) simulation, and bond-dimension tests show that truncating quantum correlations reduces candidate quality. The results therefore motivate retaining a substantive quantum sampling task within each partition as the overall problem scales. On the PEGASE-1354 benchmark, repaired QAOA samples achieve lower residual decomposition error than both simulated annealing and uniform random sampling baselines, while spatial circuit packing reduces hardware execution time by approximately a factor of three. These results demonstrate that combining spectral partitioning, spatial circuit packing, and classical feasibility repair provides an executable path for deploying gate-based quantum sampling on thousand-variable constrained optimization problems on current hardware.
The paper asks whether partitioned quantum sampling can support sparse matching decompositions beyond a single processor’s width. It studies Minimum Birkhoff Decomposition: approximating a weighted graph by a small weighted sum of matchings. An Extended Fully-Corrective Frank–Wolfe solver combines a classical maximum-weight matching oracle with candidates from fixed-angle, single-layer QAOA. Spectral partitioning limits circuit width; local samples are stitched, greedily pruned into feasible matchings, and passed to cardinality-constrained classical weight optimization. Independent circuits are spatially packed on IBM Heron processors.
Experiments use a synthetic 132-edge graph and the PEGASE-1354 transmission network, with 1,354 vertices and 1,710 edges—the latter requiring 1,710 qubits under the unpartitioned encoding. A 50-qubit partition bound produces 41 subgraphs. On PEGASE, unpacked hardware reaches normalized squared reconstruction error 1.11×10−61.11\times10^{-6}1.11×10−6 after 20 rounds; packed execution stops after 17 rounds at 1.58×10−61.58\times10^{-6}1.58×10−6 while reducing measured execution time approximately threefold. Repaired QAOA samples outperform the tested simulated-annealing and repaired-uniform baselines. Reducing partition width to 20 worsens convergence; MPS bond-dimension tests associate stronger truncation with poorer candidates.
The comparisons use specified, not computationally matched, sampling budgets and do not establish quantum advantage or classical simulation hardness. Repair is essential to the reported convergence. Cut edges may remain unsampled, routing costs depend strongly on local topology, and support selection remains combinatorial. Exact decomposition on general graphs additionally requires matching-polytope membership, not merely double substochasticity. Broader benchmarking, strong classical-solver comparisons, and comprehensive runtime accounting remain future work.
We study the problem of decomposing a graph into a weighted sum of a small number of matchings, a task that arises in network resource allocation problems such as peer-to-peer energy exchange. Computing such decompositions is challenging for classical algorithms, even for small instances. To address this problem, we propose E-FCFW, a hybrid quantum-classical algorithm based on the Fully-Corrective Frank-Wolfe (FCFW) algorithm that incorporates a matching-sampling subroutine. We design a QAOA version of this subroutine and benchmark it against classical approaches (random sampling and simulated annealing) on demand graphs derived from complete, bipartite, and heavy-hex topologies. The quantum subroutine is executed using the Qiskit Aer state-vector and MPS simulators and on IBM Kingston hardware (7-111 qubits). On complete and bipartite graphs with 6-10 nodes, E-FCFW with QAOA yields consistently sparser decompositions than the classical baselines, and even beats the best-known solution for one instance. On heavy-hex graphs with 50, 70 and 100 nodes, E-FCFW with QAOA outperforms the other methods in terms of approximation error, demonstrating performance on utility-scale quantum hardware. For the largest graphs (100 nodes) E-FCFW with QAOA performs much better when using MPS circuit simulation, compared to using quantum hardware. This indicates that at this scale, the performance is severely impacted by hardware noise.
We present an end-to-end pipeline for large-scale portfolio selection with cardinality constraints and experimentally demonstrate it on trapped-ion quantum processors using hardware-aware decomposition. Building on RMT-based correlation-matrix denoising and community detection, we identify correlated asset groups and introduce a correlation-guided greedy splitting scheme that caps each cluster by the executable qubit budget. Each cluster defines a hardware-embeddable QUBO subproblem that we solve using bias-field digitized counterdiabatic quantum optimization (BF-DCQO), a non-variational method that avoids classical parameter-training loops. We recombine low-energy candidates into global portfolios and enforce feasibility with a two-stage post-processing routine: fast repair followed by a cardinality-preserving swap local search. We benchmark the workflow on a 250-asset universe taken from the S&P 500 and execute subproblems on a 64-qubit Barium development system similar to the forthcoming IonQ Tempo line. We observe that larger executable subproblem sizes reduce decomposition error and systematically improve final objective values and risk-return trade-offs relative to randomized baselines under identical post-processing. Overall, the results establish a hardware-tested route for scaling financial optimization problems, defined by a trade space in which executable problem size and circuit cost are balanced against the resulting solution quality.
Abstract We introduce a novel hybrid quantum–classical variational optimization method for unconstrained binary combinatorial optimization problems on gate-model quantum computers, integrating a custom variational ansatz, staged feedback-based dual variational parameter update strategies, efficient parametric compilation, automated error suppression during hardware execution, and scalable O( n ) classical post-processing to correct for bitflip errors. Without this integrated approach, we show that standard circuit execution at scale produces output indistinguishable from random sampling, establishing the necessity of each pipeline component. We benchmark the method on IBM superconducting quantum computers for several optimization problems drawn from NP-hard problem classes, where the optimization is conducted on hardware with no use of classical simulation or prior knowledge of the solution. For Max-Cut on random regular graphs with topologies not matched to device connectivity, the method achieves approximation ratios (AR) of 100% for unweighted 3-regular graphs up to 156 nodes, weighted regular graphs up to 80 nodes, and weighted 7-regular graphs up 50 nodes. Applied to higher-order binary optimization, the method finds the ground state energy of 127- and 156-qubit spin-glass models matched to device topology with linear, quadratic, and cubic interaction terms, achieving ARs of at least 99.5% across all instances tested. The method consistently outperforms a classical local solver across all problems. Where published results on identical problem instances are available, our method demonstrates competitive or superior performance. These results demonstrate that an appropriately engineered variational approach enables gate-model quantum computers to produce high-quality solutions for binary optimization problems drawn from NP-hard problem classes at the 156-qubit scale, where naïve implementations are insufficient for good performance.
This study investigates the graph partitioning problem as a constrained combinatorial optimization problem and evaluates the effectiveness of the Postprocessing Variationally Scheduled Quantum Algorithm(pVSQA)(\mathbf{p V S Q A})(pVSQA)on the instances of up to 30 qubits. We executed pVSQA using Fujitsu's highperformance quantum simulator in a single-node configuration and compared its performance with the conventional Quantum Approximate Optimization Algorithm (QAOA). Experimental results on various instances show that pVSQA consistently outperforms QAOA in terms of feasibility and optimality, successfully obtaining optimal solutions even for30\mathbf{3 0}30-qubit instances. The study also demonstrates that Fujitsu's quantum simulator is effective for the stable execution of large-scale quantum circuits.
This paper studies quantum optimization baselines for the Generalized Traveling Salesman Problem (GTSP), a clustered routing problem that naturally models variant selection and sequencing problems under discrete alternatives. We propose a novel GTSP QUBO formulation focused on maintaining feasible solutions for quantum annealing, as well as a hardware-executable gate-based pipeline utilizing the Quantum Approximate Optimization Algorithm (QAOA). We implement a constrained QAOA variant using an XY-mixer, which preserves the stepwise Hamming weight in the ideal circuit model, while feasibility with respect to the full GTSP constraints is tracked explicitly during post-processing. We compare the two quantum optimization paradigms on problem instances from GTSPLIB, an established benchmark dataset, and validate against classical state-of-the-art solvers. To mitigate current quantum hardware size limitations, we further extend a preprocessing method to reduce the node count in instance clusters, constructing new NISQ-friendly instances from reduced subsets. Across all tested instances, quantum solvers often produce competitive solution quality when tested on smaller graphs, but exhibit higher runtimes and a sharp degradation in feasibility and scalability as instance size grows. Our evaluation highlights where quantum optimizers can already succeed and which algorithmic bottlenecks, like sampling rates, runtime issues, and other practical failure modes, remain as open problems.
Growing integration of distributed energy resources increases power-system variability and uncertainty. During disturbances, these effects can intensify generation-load imbalances and cascading failures. Controlled islanding limits their propagation by partitioning a compromised grid into connected, electrically sustainable islands. However, classical methods face rapidly growing computational costs as network size and island count increase. Quantum optimization offers an alternative for exploring this combinatorial partition space. Yet monolithic quantum formulations encode all assignment decisions in one circuit, causing qubit demand and circuit complexity to scale with network size. In this study, a qubit-bounded sequential distributed quantum approximate optimization algorithm (QAOA) framework is proposed to tackle coherent controlled islanding under limited quantum resources. It formulates the optimization as boundary-conditioned regional quadratic unconstrained binary optimization (QUBO) subproblems that are solved sequentially within a fixed qubit budget. Thus, circuit width remains independent of network size, with aggregate quantum workload scaling linearly on bounded-degree networks. Evaluation covers eleven IEEE systems from 9 to 300 buses using IBM quantum computing resources, with Gurobi and monolithic QAOA as references. Across all systems, the framework recovers feasible Gurobi-optimal partitions under noise, confirming the resilience of its solution quality. The results further show that the proposed method substantially reduces quantum-resource demand and circuit complexity relative to monolithic QAOA, allowing large islanding problems to be addressed within current hardware limits. The proposed framework provides a feasible and scalable pathway for quantum optimization in large-scale power systems.