Feedback-based quantum optimization and its classical counterpart: quantum advantage and the power of classical algorithms

This paper introduces a classical counterpart to feedback-based quantum optimization (FALQON) to demonstrate that while quantum algorithms may offer superior solution quality, classical counterparts often achieve faster convergence and exhibit significant scalability for higher-order unconstrained binary optimization problems.

The Gist

Imagine you are trying to find the absolute lowest point in a vast, foggy, and mountainous landscape. This is what computers do when they try to solve "combinatorial optimization" problems—like figuring out the most efficient delivery route for a trucking company or the best way to arrange materials in a new battery. The goal is to find the "ground state," or the deepest valley, where the energy (or cost) is the lowest.

This paper introduces a new way to compare two different teams of explorers trying to find that valley: Quantum Explorers (using the strange laws of quantum physics) and Classical Explorers (using standard math and physics).

Here is a breakdown of their findings using simple analogies:

1. The Two Teams of Explorers

The paper focuses on a specific method called Feedback-Based Optimization. Think of this as a hiker who constantly checks their compass and adjusts their path based on the terrain they are currently standing on, rather than following a pre-written map.

• The Quantum Team (FALQON): These explorers use quantum mechanics. They can "feel" the entire landscape at once due to quantum weirdness (like being in multiple places at once).
• The Classical Team (CC-FALQON, CACAO, etc.): These explorers use standard physics. They move step-by-step, updating their position based on local clues.

2. The Big Discovery: Speed vs. Quality

The researchers ran simulations to see who wins. The results revealed a classic trade-off, like choosing between a sports car and a heavy-duty truck.

• The Quantum "Sports Car" (FALQON):

  • The Good: It is excellent at finding the absolute best solution (the deepest valley). In some tests, it found better answers than the classical team.
  • The Bad: It is slow. It takes a long time to get there because it has to constantly measure and adjust its path, which is computationally expensive.
  • The Analogy: It's like a high-tech drone that can see the whole map but burns a lot of battery and moves slowly to be precise.

• The Classical "Truck" (CACAO and its upgrades):

  • The Good: It is incredibly fast. It converges to a good solution much quicker than the quantum team.
  • The Bad: It sometimes settles for a "good enough" valley rather than the absolute deepest one.
  • The Analogy: It's like a heavy truck that drives straight and fast. It might not find the perfect spot, but it gets you there in record time.

3. The "Super-Truck" (HOT-CACAO)

The authors didn't just stop at the basic classical truck. They built a "Super-Truck" called HOT-CACAO (and an even more advanced version, HOT-CACAO+).

• How it works: They added "higher-order" tools to the truck. Imagine giving the truck not just a steering wheel, but also a suspension system that can adjust to the shape of the road before the wheels even hit it.
• The Result: This Super-Truck is the winner for large, complex problems. It is fast and it finds very deep valleys.
• The Scalability: When the problem got huge (like a map with 10,000 cities), the basic trucks and the quantum drone struggled or stayed the same. The Super-Truck, however, actually got better at finding low-energy solutions as the map got bigger.

4. The "Homogeneous vs. Inhomogeneous" Twist

One of the most interesting findings was how the two teams reacted to "noise" or uneven terrain (called inhomogeneity).

• Quantum Team: They worked best when the terrain was smooth and uniform (Homogeneous). If you made the terrain uneven, they got confused and performed worse.
• Classical Team: They actually loved the uneven terrain (Inhomogeneous). By treating each part of the problem differently, they could navigate the chaos better.
• The Analogy: The Quantum team is like a synchronized dance troupe; they need everyone to move in perfect unison to work. The Classical team is like a group of individual hikers; if the path gets rocky, they can each take their own unique shortcut to get around it.

5. Why This Matters (According to the Paper)

The paper concludes that we shouldn't just look at quantum computers as the "future" that will replace everything.

• Quantum Advantage: Quantum algorithms (like FALQON) show they have the potential to find higher-quality solutions that classical computers might miss, thanks to their ability to explore the whole landscape globally.
• Classical Power: However, classical algorithms (especially the new HOT-CACAO versions) are currently more practical. They are faster, don't require expensive quantum hardware, and can handle massive, complex problems (like "Higher-Order" problems) directly without needing to simplify them first.

In summary: The paper argues that while quantum computers are like precision instruments that might find the perfect answer eventually, classical computers have evolved into powerful, fast, and scalable tools that are currently very effective at solving real-world optimization problems. The "Super-Truck" (HOT-CACAO+) is currently the champion for large-scale, complex tasks.

Technical Summary

Technical Summary: Feedback-based Quantum Optimization and its Classical Counterpart

Problem Statement
Combinatorial optimization problems, ubiquitous in logistics, materials science, and finance, are generally classified as NP-hard, requiring exponential computational costs to solve exactly. While various quantum and classical solvers exist, including quantum annealers and variational quantum algorithms, there is a need to rigorously compare quantum approaches with their classical counterparts to assess the potential for quantum advantage. Specifically, the Feedback-based Algorithm for Quantum Optimization (FALQON) utilizes Lyapunov control theory to iteratively reduce a cost function without classical optimization loops. However, the computational cost of iterative feedback in quantum systems is substantial. Conversely, classical algorithms inspired by FALQON, such as CACAO (Counterdiabaticity-assisted Classical Algorithm for Optimization), offer faster convergence but may lack solution quality. Furthermore, Higher-order Unconstrained Binary Optimization (HUBO) problems are often inefficiently solved by reducing them to Quadratic Unconstrained Binary Optimization (QUBO) forms, which increases problem size. There is a gap in understanding the exact classical counterparts of feedback-based quantum algorithms and their ability to handle HUBO problems directly.

Methodology
The authors establish a theoretical framework based on the quantum-classical correspondence of spin systems. By replacing Pauli matrices $\{\hat{X}_i, \hat{Y}_i, \hat{Z}_i\}$ with classical unit spin vectors $\{m^X_i, m^Y_i, m^Z_i\}$ and utilizing canonical equations of motion, they derive exact classical counterparts to feedback-based quantum optimization.

1. Theoretical Derivation:

   • Quantum Side: The paper reviews FALQON and its inhomogeneous variant (iFALQON), where control parameters are determined by the expectation value of commutators between the problem Hamiltonian and driving terms.
   • Classical Side: The authors derive CC-FALQON and CC-iFALQON as the exact classical counterparts. Unlike the quantum version, these classical algorithms do not require an iterative feedback loop; the control parameters are calculated directly from the instantaneous state of the classical spins.
   • Higher-Order Extension: The framework is extended to develop HOT-CACAO (Higher-Order CACAO), which introduces second-order counterdiabatic terms, and HOT-CACAO+, which incorporates both the problem Hamiltonian and all discussed counterdiabatic terms (first and second-order).

2. Benchmarking:

   • Small-Scale: The authors perform benchmark tests on $N=12$ instances of the 2-SAT problem (formulated as QUBO) to compare the solution quality and convergence speed of quantum algorithms (FALQON, iFALQON) against their classical counterparts (CC-FALQON, CC-iFALQON) and other classical variants (CACAO, HOT-CACAO, HOT-CACAO+).
   • Large-Scale: The study evaluates the scalability of classical algorithms on $N=10,000$ instances of the 3-SAT problem (formulated directly as HUBO). The algorithms tested include CC-iFALQON, CACAO, HOT-CACAO, and HOT-CACAO+.
   • Dynamics Analysis: The paper analyzes the control parameter strengths and energy dynamics to understand the convergence behavior and the role of nonlocality versus locality.

Key Contributions

• Exact Classical Counterparts: The paper introduces CC-FALQON and CC-iFALQON, providing the first exact classical formulations of feedback-based quantum optimization algorithms derived from spin system correspondence.
• Higher-Order Classical Theory: It develops HOT-CACAO and HOT-CACAO+, extending the CACAO algorithm with higher-order counterdiabatic terms and the explicit inclusion of the problem Hamiltonian.
• Direct HUBO Solving: The proposed classical algorithms are demonstrated to solve HUBO problems directly without the need for order-reduction methods (which typically introduce auxiliary variables and degrade performance).
• Quantum vs. Classical Dynamics: The study elucidates the contrasting behaviors of quantum and classical dynamics regarding inhomogeneous driving, attributing differences to the global nature of quantum dynamics versus the local nature of classical updates.

Results

• Solution Quality vs. Convergence Speed:
  • Quantum Advantage in Quality: FALQON demonstrates superior solution quality (lower final energy density) compared to its classical counterpart CC-FALQON and other classical algorithms in small-scale instances, suggesting a potential quantum advantage in exploring the global optimization landscape.
  • Classical Advantage in Speed: Classical algorithms generally exhibit significantly faster convergence than quantum algorithms. Notably, CC-FALQON shows very slow convergence, while HOT-CACAO and HOT-CACAO+ converge rapidly.
• Inhomogeneity Effects:
  • In the quantum setting, homogeneous driving (FALQON) outperforms inhomogeneous driving (iFALQON).
  • In the classical setting, the trend is reversed: inhomogeneous driving (CC-iFALQON) achieves lower energy than homogeneous driving (CC-FALQON). This is attributed to the mismatch between global quantum dynamics and local parameters, versus the compatibility of inhomogeneous driving with local classical updates.
• Scalability and HUBO Performance:
  • In large-scale 3-SAT instances ($N=10,000$), HOT-CACAO+ achieves the lowest final energy density among all tested methods.
  • While HOT-CACAO+ converges slower than HOT-CACAO, it reaches lower energy states, indicating a trade-off between convergence speed and solution quality.
  • Scalability analysis reveals that HOT-CACAO+ is the only method that consistently improves energy density as the system size increases, whereas other methods plateau. This highlights the necessity of combining higher-order counterdiabatic terms with the problem Hamiltonian for large-scale, high-order optimization.

Significance and Claims
The paper claims that its findings highlight the distinct roles of "quantumness" and classical approaches. Feedback-based quantum optimization (FALQON) shows potential for achieving higher-quality solutions by leveraging global correlations, whereas classical algorithms, particularly those enhanced with higher-order counterdiabatic terms (HOT-CACAO+), offer rapid convergence and superior scalability for HUBO problems.

The authors assert that classical algorithms are highly promising for combinatorial optimization because they avoid the iterative overhead and intermediate state measurement costs associated with quantum implementations. Furthermore, the ability to directly handle higher-order interactions without order reduction makes these classical approaches particularly efficient for HUBO formulations. The paper concludes that while quantum algorithms may offer advantages in solution quality, classical algorithms provide a powerful, scalable alternative, and systematic comparisons under equal computational budgets remain a necessary direction for future work.