arXiv:2506.04223 · Journal of Chemical Theory and Computation

Bridging Quantum Chemistry and MaxCut: Classical Performance Guarantees and Quantum Algorithms for the Hartree–Fock Method

Alexis Ralli, Tim Weaving, Peter V. Coveney, Peter J. Love

Published Sep 23, 2025• 2 citations

Abstract

In quantum chemistry, self-consistent field (SCF) algorithms define a nonlinear optimization problem, with both continuous and discrete components. In this work, we derive Hartree–Fock-inspired SCF algorithms that can be exactly written as a sequence of Quadratic Unconstrained Spin/Binary Optimization problems (QUSO/QUBO). We reformulate the optimization problem as a series of MaxCut graph problems, which can be efficiently solved using semidefinite programming techniques. This procedure provides performance guarantees at each SCF step, irrespective of the complexity of the optimization landscape. We numerically demonstrate the QUBO-SCF and MaxCut-SCF methods by studying the hydroxide anion OH – and molecular Nitrogen N 2 . The largest problem addressed in this study involves a system comprised of 220 qubits (equivalently, spin–orbitals). Our results show that QUBO-SCF and MaxCut-SCF suffer much less from internal instabilities compared with conventional SCF calculations. Additionally, we show that the new SCF algorithms can enhance single-reference methods, such as configuration interaction. Finally, we explore how quantum algorithms for optimization can be applied to the QUSO problems arising from the Hartree–Fock method. Four distinct hybrid-quantum classical approaches are introduced: GAS-SCF, QAOA-SCF, QA-SCF and DQI-SCF.

DOI: 10.1021/acs.jctc.5c00948

Related papers

Quantum-Accelerated Self-Consistent Field: A Hybrid Algorithm

Alexis Ralli, Tim Weaving, Thomas M. Bickley +2 more

We present the Grover adaptive search self-consistent field (GAS-SCF) algorithm. GAS-SCF leverages quantum arithmetic to construct an efficient oracle that marks target states (Fock states) which improve upon some initial classical energy estimate. Amplitude amplification then increases the probability of measuring these states. This approach offers a theoretical quadratic speed-up for the optimization problem encountered in SCF quantum chemistry and establishes a baseline against which structured optimization algorithms, such as QAOA and DQI may be compared. In this work, we classically simulate three examples as proofs of concept of the algorithm, the largest consisting of 26 qubits. We then extend our analysis to two larger systems, with O3 representing the largest case at 330 qubits. These examples are chosen to probe classically challenging SCF regimes. Achieving chemically relevant applications of GAS-SCF will require large-scale, fault-tolerant quantum hardware.

quant-pharXiv:2606.20176Jun 19, 20260 citations

Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms

Gian Giacomo Guerreschi

Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.

arXiv:2101.07813Jan 19, 202112 citations

Hybrid Quantum Branch-and-Bound Method for Quadratic Unconstrained Binary Optimization

Zedong Peng, Daniel de Roux, David E. Bernal

Quantum algorithms have shown promise in solving Quadratic Unconstrained Binary Optimization (QUBO) problems, benefiting from their connection to the transverse field Ising model.Various Ising solvers, both classical and quantum, have emerged to tackle such problems efficiently but lack global optimality guarantees and oftentimes sufer from hardware limitations such as limited qubit availability.In this work, we propose a hybrid branch-andbound (B&B) framework that integrates Ising solvers as heuristics within a classical B&B algorithm.Unlike prior theoretical studies, our work presents a practical implementation, available as open-source at GitHub.We explore when and where to apply Ising solvers in the search tree, and introduce a custom branching rule optimized QUBO embedding.Our method is evaluated on hundreds of QUBO instances from QUBOLib.jl using Gurobi and the D-Wave quantum annealer.Our Results show up to 11% less solution time and 17% fewer nodes compared to default Gurobi, an off-the-shelf commercial optimization solver.These findings demonstrate the value of hybrid quantum-classical strategies for enhancing exact optimization.

arXiv:2509.11040Computer Science Research NotesJan 1, 20250 citations

An Efficient Hybrid Classical Quantum Algorithm for Mixed-Integer Constrained Optimization

Amit Surana

Widely used quantum optimization algorithms such as quantum annealing and quantum approximate optimization algorithm (QAOA) for quadratically unconstrained binary optimization (QUBO) problems cannot systematically and efficiently handle constraints and mixed discrete and continuous decision variables. To address this, we present a novel hybrid classicalquantum approach which combines classical alternating direction method of multipliers (ADMM) with QAOA. Compared to conventional penalty-based method, this approach avoids quantization of continuous variables, eliminates the need for additional qubits to capture constraints on a quantum device and leads to reduced QAOA circuit depth suitable for near term implementation. We illustrate the efficacy of our approach on several constrained mixed integer optimization problems.

IEEE International Conference on Quantum Computing and Engineering (QCE)Aug 30, 20250 citations

Faster exact solution of sparse MaxCut and QUBO problems

Daniel Rehfeldt, Thorsten Koch, Yuji Shinano

The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems -- by using mathematical programming techniques on digital computers. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse MaxCut and QUBO instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.

arXiv:2202.02305Feb 4, 20221 citation

A Use-Case-Oriented Benchmark Framework for Classical, Quantum, Hybrid, and Quantum-Inspired Optimization

Dominik Leib, Tobias Seidel, Sebastian Velten +1 more

Abstract As interest in quantum and related optimization paradigms continues to grow, fairly and systematically comparing their performance across practical problem settings remains challenging. This challenge arises because these approaches often target different problem classes, use different mathematical representations, and are affected differently by modeling choices. As a result, observed performance depends not only on the solver itself, but also on how a problem is formulated, reformulated, and translated into a solver-specific input language. This work presents a publicly available and extensible benchmarking framework that unifies advances in quantum, quantum-hybrid, quantum-inspired, and classical optimization by enabling consistent comparison across use cases, solvers, and models. We address the diversity of solver “languages”—from mixed-integer programming (MIP) formulations for branch-and-bound methods over quadratic unconstrained binary optimization (QUBO) models for quantum annealers to constrained quadratic models (CQM) for hybrid approaches — as well as the influence of modeling choices, such as binary encodings and penalty formulations, on both performance and solution fidelity. By supporting systematic variation across the three dimensions of use case, solver, and model, the framework reveals trade-offs that single-dimension benchmarks overlook, clarifies when native formulations are preferable, and enables rigorous evaluation of practical combinatorial optimization problems. The two case studies, vehicle routing and maximum cut, illustrate this principle: their contrasting outcomes show that the effectiveness of a solver depends strongly on how well the chosen model representation matches the solver backend and the use case.

Jun 15, 20260 citations