Abstract Combinatorial optimization plays a crucial role in many industrial applications. While classical computing often struggles with complex instances, quantum optimization emerges as a promising alternative. Here, we present an enhanced bias-field digitized counterdiabatic quantum optimization (BF-DCQO) algorithm to address higher-order unconstrained binary optimization (HUBO). We apply BF-DCQO to a HUBO problem featuring three-local terms in the Ising spin-glass model, validated experimentally using 156 qubits on an IBM quantum processor. In the studied instances, our results outperform standard methods such as the quantum approximate optimization algorithm, quantum annealing, simulated annealing, and Tabu search. Furthermore, we provide numerical evidence of the feasibility of a similar HUBO problem on a 433-qubit Osprey-like quantum processor. Finally, we solve denser instances of the MAX 3-SAT problem in an IonQ emulator. Our results show that BF-DCQO offers an effective path for solving large-scale HUBO problems on current and near-term quantum processors.
Abstract Combinatorial optimization plays a crucial role in many industrial applications. While classical computing often struggles with complex instances, quantum optimization emerges as a promising alternative. Here, we present an enhanced bias-field digitized counterdiabatic quantum optimization (BF-DCQO) algorithm to address higher-order unconstrained binary optimization (HUBO). We apply BF-DCQO to a HUBO problem featuring three-local terms in the Ising spin-glass model, validated experimentally using 156 qubits on an IBM quantum processor. In the studied instances, our results outperform standard methods such as the quantum approximate optimization algorithm, quantum annealing, simulated annealing, and Tabu search. Furthermore, we provide numerical evidence of the feasibility of a similar HUBO problem on a 433-qubit Osprey-like quantum processor. Finally, we solve denser instances of the MAX 3-SAT problem in an IonQ emulator. Our results show that BF-DCQO offers an effective path for solving large-scale HUBO problems on current and near-term quantum processors.
Branch-and-bound algorithms effectively solve combinatorial optimization problems, relying on the relaxation of the objective function to obtain tight lower bounds. While this is straightforward for convex objective functions, higher-order formulations pose challenges due to their inherent non-convexity. In this work, we propose branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO), a quantum algorithm that addresses the relaxation difficulties in higher-order unconstrained binary optimization (HUBO) problems. By employing bias fields as approximate solutions to the relaxed problem, we iteratively enhance the quality of the results compared to the bare bias-field digitized counterdiabatic quantum optimization (BF-DCQO) algorithm. We refer to this enhanced method as BBB-DCQO. In order to benchmark it against simulated annealing (SA), we apply it on sparse HUBO instances with up to 156 qubits using tensor network simulations. To explore regimes that are less tractable for classical simulations, we experimentally apply BBB-DCQO to denser problems using up to 100 qubits on IBM quantum hardware. We compare our results with SA and a greedy-tuned quantum annealing baseline. In both simulations and experiments, BBB-DCQO consistently achieved higher-quality solutions with significantly reduced computational overhead, showcasing the effectiveness of integrating counterdiabatic quantum methods into branch-and-bound to address hard non-convex optimization tasks.
We experimentally demonstrate that the bias-field digitized counterdiabatic quantum optimization (BF-DCQO) algorithm, implemented on IonQ's fully connected trapped-ion quantum processors, offers an efficient approach to solving dense higher-order unconstrained binary optimization (HUBO) problems. Specifically, we tackle protein folding on a tetrahedral lattice for up to 12 amino acids, representing the largest quantum hardware implementations of protein folding problems reported to date. Additionally, we address MAX 4-SAT instances at the computational phase transition and fully connected spin-glass problems using all 36 available qubits. Across all considered cases, our method consistently achieves optimal solutions, highlighting the powerful synergy between non-variational quantum optimization approaches and the intrinsic all-to-all connectivity of trapped-ion architectures. Given the expected scalability of trapped-ion quantum systems, BF-DCQO represents a promising pathway toward practical quantum advantage for dense HUBO problems with significant industrial and scientific relevance.
The increasing complexity of industrial scheduling and transport routing problems motivates the study of alternative optimization formulations and computational paradigms. In this work, we study how higher-order unconstrained binary optimization (HUBO) formulations of such problems map onto quantum optimization workflows in both noisy and fault-tolerant regimes. We consider three representative logistics and manufacturing use cases and formulate each as a HUBO problem. This captures process intricacies, such as highly correlated assembly-line scheduling rules, which are difficult to express faithfully with the standard quadratic (QUBO) form, while at the same time reducing the number of binary variables required in the quantum mapping, thus lowering qubit demand. We compare the HUBO formulations with corresponding QUBO encodings, highlighting a key trade-off: while HUBO reduces qubit requirements through compact binary encoding, it introduces higher-order interaction terms that increase circuit depth, limiting feasibility on current quantum hardware. The proposed formulations are validated using classical solvers across several problem instances and benchmark small routing problem instances using bias-field digitized counterdiabatic quantum optimization in classical simulation. We complement these results with a resource and scalability analysis, focusing on the capacitated vehicle routing problem as a representative large-scale industrial use case. Our analysis indicates that while HUBO formulations offer advantages in qubit scaling compared to QUBO encodings, their practical implementation is constrained by gate fidelity, coherence, and circuit depth, making hybrid quantum-classical workflows and early fault-tolerant quantum hardware the most plausible settings for their practical use.
We introduce a method for solving combinatorial optimization problems on digital quantum computers, where we incorporate auxiliary counterdiabatic (CD) terms into the adiabatic Hamiltonian, while integrating bias terms derived from an iterative digitized counterdiabatic quantum algorithm. We call this protocol bias-field digitized counterdiabatic quantum optimization (BF-DCQO). Designed to effectively tackle large-scale combinatorial optimization problems, BF-DCQO demonstrates resilience against the limitations posed by the restricted coherence times of current quantum processors and shows clear enhancement even in the presence of noise. Additionally, our purely quantum approach eliminates the dependency on classical optimization required in hybrid classical-quantum schemes, thereby circumventing the trainability issues often associated with variational quantum algorithms. Through the analysis of an all-to-all connected general Ising spin-glass problem, we exhibit a polynomial scaling enhancement in ground-state success probability compared to traditional DCQO and finite-time adiabatic quantum optimization methods. Furthermore, it achieves scaling improvements in ground-state success probabilities, increasing by up to two orders of magnitude, and offers an average 1.3 × better approximation ratio than the quantum approximate optimization algorithm for the problem sizes studied. We validate these findings through experimental implementations on both trapped-ion quantum computers and superconducting processors, tackling a maximum weighted independent set problem with 36 qubits and a spin glass on a heavy-hexagonal lattice with 100 qubits, respectively. These results mark a significant advancement in gate-based quantum computing, employing a fully quantum algorithmic approach.
We report the largest trapped-ion hardware demonstration of lattice protein-folding optimization to date, using bias-field digitized counterdiabatic quantum optimization (BF-DCQO) on a fully connected 64-qubit Barium development system similar to the forthcoming IonQ Tempo line. Six peptide sequences with 14-16 amino-acid residues are encoded using a coarse-grained tetrahedral lattice model, yielding higher-order spin-glass Hamiltonians with long-range interactions involving up to five-body terms and mapped to 46-61 qubits. The resulting instances are demanding for near-term quantum hardware because low-energy configurations must satisfy backbone-geometry constraints while optimizing dense residue-contact interactions. BF-DCQO uses a non-variational bias-feedback mechanism, where low-energy samples from each round define longitudinal fields that guide subsequent quantum evolutions. Across the studied instances, BF-DCQO shifts raw sampled energy distributions toward lower energies than uniform random sampling, with the strongest improvements appearing in residue-contact variables. To preserve this signal, we introduce a consensus-based post-processing pipeline that combines quantum-learned contact information with feasible backbone geometries. The resulting hybrid workflow reaches the classical reference energy in multiple instances and improves over the corresponding random-seeded pipeline. These results show that BF-DCQO can generate structured samples for dense protein-folding Hamiltonians at previously unexplored trapped-ion scales.
We introduce hybrid sequential quantum computing (HSQC), a paradigm for combinatorial optimization that systematically integrates classical and quantum methods within a structured, stage-wise workflow. HSQC may involve an arbitrary sequence of classical and quantum processes, as long as the global result outperforms the standalone components. Our testbed begins with classical optimizers to explore the solution landscape, followed by quantum optimization to refine candidate solutions, and concludes with classical solvers to recover nearby or exact-optimal states. We demonstrate two instantiations: (i) a pipeline combining simulated annealing (SA), bias-field digitized counterdiabatic quantum optimization (BF-DCQO), and memetic tabu search (MTS); and (ii) a variant combining SA, BF-DCQO, and a second round of SA. This workflow design is motivated by the complementary strengths of each component. Classical heuristics efficiently find low-energy configurations, but often get trapped in local minima. BF-DCQO exploits quantum resources to tunnel through these barriers and improve solution quality. Due to decoherence and approximations, BF-DCQO may not always yield optimal results. Thus, the best quantum-enhanced state is used to continue with a final classical refinement stage. Applied to challenging higher-order unconstrained binary optimization (HUBO) problems on a 156-qubit heavy-hexagonal superconducting quantum processor, we show that HSQC consistently recovers ground-state solutions in just a few seconds. Compared to standalone classical solvers, HSQC achieves a speedup of up to 700 times over SA and up to 9 times over MTS in estimated runtimes. These results demonstrate that HSQC provides a flexible and scalable framework capable of delivering up to two orders of magnitude improvement at runtime quantum-advantage level on advanced commercial quantum processors.