⚛️ quantum physics

Feedback-based quantum optimization with low depth and measurement

This paper introduces BLS-FALQON, a hybrid quantum-classical optimization algorithm inspired by Backtracking Line Search that significantly reduces measurement overhead compared to SO-FALQON while maintaining low circuit depth, as validated through numerical simulations and real-world experiments on the Tianyan-176 quantum computer.

Original authors: Zi-Wen Huang, Jia-Cheng Fan, Xiao-Hui Ni, Su-Juan Qin, Xiao-Kai Hou, Wei Huang, Bing-Jie Xu, Fei Gao

Published 2026-09-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zi-Wen Huang, Jia-Cheng Fan, Xiao-Hui Ni, Su-Juan Qin, Xiao-Kai Hou, Wei Huang, Bing-Jie Xu, Fei Gao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the race to build useful quantum computers, scientists are currently working with machines that are powerful but fragile. These devices, known as noisy intermediate-scale quantum computers, can perform complex calculations, but they are easily disturbed by their environment, causing errors to creep in before a calculation finishes. To solve difficult problems like organizing data or finding the most efficient route through a network, researchers use hybrid algorithms that combine the strengths of classical computers with these new quantum processors. One such method, called FALQON, acts like a guided search. It starts with a random guess and repeatedly adjusts the quantum state, using feedback from measurements to nudge the system closer to the best possible answer. The problem is that this guidance requires the quantum computer to run a very long sequence of operations. Because the machines are so fragile, running a long sequence often means the signal gets lost in the noise before the answer is found.

To fix this, researchers previously developed a faster version of the search that could reach the solution in fewer steps. However, this speed came with a heavy price: the machine had to take many more measurements at every single step to ensure it didn't go off course. This flood of measurements slowed the process down and introduced even more errors. A new study by a team at Beijing University of Posts and Telecommunications and other institutions proposes a different solution. They introduced a method called BLS-FALQON, which manages to keep the search short without demanding an excessive number of measurements. By using a strategy borrowed from mathematical optimization, the team created a system that can take large, confident steps toward the solution while only checking its progress occasionally. When the system does check and finds it has drifted, it simply reverses direction and tries a smaller step, rather than recalculating complex values from scratch.

The researchers tested this new approach on a classic puzzle known as the max-cut problem, which involves dividing a network into two groups to maximize the connections between them. In computer simulations involving networks with up to twenty nodes, the new method proved highly effective. It reduced the total number of measurements required by nearly thirty-eight percent compared to the previous fastest method, while keeping the length of the quantum circuit roughly the same. This is a significant improvement because, in the current generation of quantum hardware, the time spent measuring and the time spent running the circuit are the two biggest bottlenecks. By cutting down the measurements, the team effectively reduced the total time the quantum computer needed to solve the problem.

To verify that these results held up in the real world, the team ran their experiments on a physical quantum computer located in China, which uses a superconducting processor with 176 qubits. They tested the algorithm on small networks with four, six, and eight nodes. The results confirmed that the new method was not just a simulation success but a practical reality. On the actual hardware, the new approach reduced the estimated execution time by forty-three percent compared to the previous best method. The system remained stable even in the presence of the noise and errors that plague current machines. While the new method did not completely eliminate the gap between the noisy hardware results and the perfect theoretical ideal, it performed better than the alternatives and showed that it could find good solutions without overwhelming the fragile quantum processor with too many checks.

The success of this work lies in its simplicity. Instead of trying to calculate a perfect, complex correction at every step, the new algorithm uses a heuristic approach. It takes a large step, checks if the result improved, and if not, it simply flips the direction of the next step and tries again. This back-and-forth adjustment allows the system to stay on track without needing to gather extra data that would slow it down. The researchers found that this strategy works well even when the quantum computer is making mistakes, because the method naturally corrects for those mistakes by reversing direction when things go wrong. This suggests that for the current generation of quantum computers, the most efficient path forward may not be to make the machines more complex, but to make the instructions they follow smarter and more efficient.

The study also highlights the importance of how data is grouped during measurement. In quantum computing, measuring one part of the system can disturb another, so scientists must group related measurements together to minimize disruption. The team showed that their new method could be combined with existing grouping techniques to further reduce the workload. This means that the savings in time and resources are not just theoretical but are directly applicable to the way these machines are currently programmed. The findings suggest that by refining the feedback loop, researchers can squeeze more performance out of the quantum hardware they already have, potentially bringing practical applications for these machines closer to reality.

Ultimately, the work demonstrates that efficiency in quantum computing is not just about building bigger processors, but about designing algorithms that respect the physical limits of the hardware. The new method achieves a balance between speed and accuracy that previous approaches could not. It offers a way to navigate the noisy landscape of current quantum devices without getting lost in the errors. As the field moves forward, techniques like this will likely become essential for solving real-world problems, proving that sometimes the best way to move forward is to know exactly when to step back and try again.

Technical Summary: Feedback-based Quantum Optimization with Low Depth and Measurement

Problem Statement

Feedback-based Algorithm for Quantum OptimizatioN (FALQON) is a hybrid quantum-classical algorithm designed to solve combinatorial optimization problems without classical parameter optimization. While it avoids the training difficulties inherent in Variational Quantum Algorithms (VQAs), standard FALQON suffers from prohibitive circuit depth. This depth arises because the algorithm requires a small discrete time step ( $\Delta t$ ) to ensure the monotonic decrease of the problem Hamiltonian's expectation value; larger steps introduce Trotter decomposition errors that cause oscillations and prevent convergence.

To address this, Arai et al. proposed Second-order FALQON (SO-FALQON), which utilizes a second-order Taylor expansion of the cost function difference. This allows for a larger $\Delta t$ , significantly reducing circuit depth. However, SO-FALQON introduces a substantial measurement overhead, requiring the estimation of two additional complex Hamiltonians ( $B_k$ and $C_k$ ) at every layer. This increases the per-step measurement count by approximately 2.3 times compared to the original FALQON, creating a new bottleneck for resource-constrained Noisy Intermediate-Scale Quantum (NISQ) devices.

Methodology: BLS-FALQON

The authors propose BLS-FALQON (Backtracking Line Search FALQON), a heuristic variant inspired by the Backtracking Line Search (BLS) theory. The method aims to achieve the low circuit depth of SO-FALQON while avoiding its high measurement overhead.

Core Mechanism

Unlike SO-FALQON, which calculates a second-order control coefficient $\beta^{(SO)}$ requiring complex Hamiltonian measurements, BLS-FALQON retains the first-order control coefficient $\beta^{(FO)}$ but dynamically adjusts it using a backtracking mechanism:

Initial Step: The algorithm computes the standard first-order coefficient $\beta^{(FO)}_{k+1} = -A_k$ , where $A_k$ is the expectation value of the commutator $[H_d, H_p]$ .
Monitoring: At each step, the algorithm also estimates the problem Hamiltonian's expectation value, $E_k = \langle H_p \rangle$ .
Backtracking Trigger: If $E_k$ fails to decrease monotonically (i.e., $E_k > E_{k-1}$ ), indicating a potential misdirection due to Trotter errors or noise, the algorithm triggers a backtracking loop.
Correction: The control coefficient is iteratively scaled by a negative factor $\tau \in (-1, 0)$ :
$\beta^{(FO)}_k \leftarrow \tau \beta^{(FO)}_k$
The negative sign reverses the control direction to correct misdirection, while the magnitude reduction suppresses oscillations. The state is re-prepared and $E_k$ is re-evaluated until a monotonic decrease is observed.

Measurement Efficiency

A key theoretical advantage is that BLS-FALQON does not require estimating the complex Hamiltonians $B_k$ and $C_k$ . For problems like Max-Cut where the problem Hamiltonian $H_p$ consists of 2-local $ZZ$ Pauli strings, the estimation of $E_k$ can be absorbed into the existing qubit-wise commuting subsets used for $A_k$ . Consequently, for graph sizes $n \ge 12$ , the per-step measurement bases for BLS-FALQON are identical to those of the original FALQON, avoiding the 2.3x overhead of SO-FALQON.

Key Contributions

Algorithmic Innovation: Introduction of BLS-FALQON, which integrates a modified backtracking line search strategy to heuristically adjust the first-order control coefficient, eliminating the need for second-order Hamiltonian estimation.
Theoretical Analysis:
- Error Bounds: Proof that the backtracking mechanism terminates within a finite number of steps, guaranteeing that a valid descent step exists even if the initial direction is incorrect due to Trotter errors.
- Quadratic Landscapes: Analysis showing that while the heuristic coefficient may not be the exact optimal vertex (as in SO-FALQON), it satisfies the descent condition, ensuring convergence stability.
Resource Reduction: Demonstration that the method achieves a significant reduction in total measurement counts while maintaining circuit depths comparable to the state-of-the-art SO-FALQON.

Experimental Results

Numerical Simulations

Simulations were conducted on unweighted 3-regular graphs with $n \in \{8, \dots, 20\}$ vertices using the Qiskit framework. The target was an approximation ratio of $r_{GW} = 0.932$ (the Goemans-Williamson bound).

Measurement Overhead: BLS-FALQON reduced the total measurement count by 37.7% compared to SO-FALQON and by 88.1% compared to standard FALQON.
Circuit Depth: BLS-FALQON required approximately 2.5% more layers than SO-FALQON to reach the target approximation ratio, a marginal increase attributed to the heuristic nature of the backtracking coefficient. However, this depth was still approximately 11 times lower than that of standard FALQON.
Scalability: The measurement savings remained consistent as the problem scale increased.

Real Quantum Hardware Experiments

Experiments were performed on the Tianyan-176 quantum computer, utilizing the Zuchongzhi2 superconducting quantum processor. Tests were limited to small-scale instances ( $n \in \{4, 6, 8\}$ ) with a maximum of $L=10$ layers due to coherence time constraints.

Execution Time: BLS-FALQON reduced the estimated average hardware execution time by 43% relative to SO-FALQON. This reduction is directly attributed to the decreased number of measurement bases required per step.
Robustness: Under realistic hardware noise, BLS-FALQON achieved the highest average approximation ratio among the three algorithms and exhibited the narrowest convergence bands for $n=4$ and $n=6$ .
Noise Impact: The backtracking mechanism provided a corrective effect against hardware-induced noise. When noise caused a spurious increase in $E_k$ , the alternating sign scaling of $\beta$ identified a valid descent coefficient without requiring additional Hamiltonian measurements, partially compensating for control direction misdirection.

Significance and Claims

The paper claims that BLS-FALQON successfully addresses the trade-off between circuit depth and measurement overhead in feedback-based quantum optimization. By leveraging the backtracking line search theory, the method:

Maintains Low Depth: It achieves circuit depths comparable to the best existing approach (SO-FALQON), making it viable for NISQ devices where coherence time is limited.
Reduces Measurement Cost: It significantly lowers the total measurement count compared to SO-FALQON, which is critical for reducing the total time complexity on real hardware where measurement operations are time-consuming.
Enhances Stability: The backtracking mechanism acts as a stabilizer against both Trotter decomposition errors and hardware noise, ensuring monotonic convergence where standard first-order methods might oscillate.

The authors conclude that BLS-FALQON is a practical and effective algorithm for small-scale combinatorial optimization problems on current NISQ hardware, offering a balanced improvement in both circuit depth and measurement efficiency. They note that while a gap remains between hardware results and ideal simulations due to current device limitations, the algorithm's design is robust and scalable.