It is hoped that quantum computers will offer advantages over classical computers for combinatorial optimization. Here, we introduce a feedback-based strategy for quantum optimization, where the results of qubit measurements are used to constructively assign values to quantum circuit parameters. We show that this procedure results in an estimate of the combinatorial optimization problem solution that improves monotonically with the depth of the quantum circuit. Importantly, the measurement-based feedback enables approximate solutions to the combinatorial optimization problem without the need for any classical optimization effort, as would be required for the quantum approximate optimization algorithm. We demonstrate this feedback-based protocol on a superconducting quantum processor for the graph-partitioning problem MaxCut, and present a series of numerical analyses that further investigate the protocol's performance.
It is hoped that quantum computers will offer advantages over classical computers for combinatorial optimization. Here, we introduce a feedback-based strategy for quantum optimization, where the results of qubit measurements are used to constructively assign values to quantum circuit parameters. We show that this procedure results in an estimate of the combinatorial optimization problem solution that improves monotonically with the depth of the quantum circuit. Importantly, the measurement-based feedback enables approximate solutions to the combinatorial optimization problem without the need for any classical optimization effort, as would be required for the quantum approximate optimization algorithm. We demonstrate this feedback-based protocol on a superconducting quantum processor for the graph-partitioning problem MaxCut, and present a series of numerical analyses that further investigate the protocol's performance.
The prospect of using quantum computers to solve combinatorial optimization problems via the quantum approximate optimization algorithm (QAOA) has attracted considerable interest in recent years. However, a key limitation associated with QAOA is the need to classically optimize over a set of quantum circuit parameters. This classical optimization can have significant associated costs and challenges. Here we provide an expanded description of Lyapunov control-inspired strategies for quantum optimization, as presented in [Magann et al., Phys. Rev. Lett. 129, 250502 (2022)], that do not require any classical optimization effort. Instead, these strategies utilize feedback from qubit measurements to assign values to the quantum circuit parameters in a deterministic manner, such that the combinatorial optimization problem solution improves monotonically with the quantum circuit depth. Numerical analyses are presented that investigate the utility of these strategies towards MaxCut on weighted and unweighted 3-regular graphs, both in ideal implementations and in the presence of measurement noise. We also discuss how how these strategies compare with QAOA and how they may be used to seed QAOA optimizations in order to improve performance for near-term applications, and we explore connections to quantum annealing.
Combinatorial optimization problems are one of the areas where near-term noisy quantum computers may have practical advantage against classical computers. Recently, a feedback-based quantum optimization algorithm has been proposed by Magann , . The method explicitly determines quantum circuit parameters by feeding back measurement results thus avoids classical parameter optimization that is known to cause significant trouble in quantum approximate optimization algorithm, the well-studied near-term algorithm. Meanwhile, a significant drawback of the feedback-based quantum optimization is that it requires deep circuits, rendering the method unsuitable to noisy quantum devices. In this study we propose a feedback law for parameter determination by introducing the second-order approximation with respect to time interval, a hyperparameter in the feedback-based quantum optimization. This allows one to take larger time interval, leading to acceleration of convergence to solutions. In numerical simulations on the maximum cut problem we demonstrate that our proposal significantly reduces circuit depth, with its linear scaling with the problem size smaller by more than an order of magnitude. We expect that the feedback law proposed in this work may pave the way for feedback-based quantum optimization with near-term noisy quantum computers.
Feedback-based ALgorithm for Quantum OptimizatioN (FALQON) is a hybrid quantum-classical algorithm for solving combinatorial optimization problems, which circumvents classical parameter optimization but requires a deep quantum circuit. To reduce circuit depth, Arai et al. proposed second-order FALQON (SO-FALQON), achieving the best depth reduction among existing approaches. However, SO-FALQON brings a 2.3 times per-step measurement overhead, as it needs to calculate an additional second-order control coefficient. In this paper, inspired by the Backtracking Line Search (BLS) theory, we propose another method called BLS-FALQON, which not only reduces circuit depth to a comparable extent, but also achieves fewer measurements than SO-FALQON. Numerical simulations on max-cut problem with 8 to 20 vertices demonstrate that BLS-FALQON reduces the total measurement count by 37.7% compared to SO-FALQON, while maintaining a comparable circuit depth. Furthermore, we conduct real quantum hardware experiments on the Tianyan-176 quantum computer, which uses the zuchongzhi2 superconducting quantum processor, confirming that BLS-FALQON remains effective under real quantum hardware conditions.
Improving the performance of quantum algorithms is a fundamental task to achieve quantum advantage. In many cases, extracting information from quantum systems poses an important challenge for practical implementations of real-world quantum computers, given the high resource cost of performing state tomography. In this scenario, randomized measurements have emerged as a promising tool. In particular, the classical shadow protocol allows one to retrieve expected values of low-weight Pauli observables by performing only local measurements. In this paper, we present an implementation of the recently introduced feedback-based algorithm for quantum optimization using the Ket quantum programming platform to solve the MaxCut optimization problem. We employ classical shadows for the feedback routine of parameter estimation and compare this approach with the direct estimation of observables. Our results show that depending on the graph geometry of the MaxCut problem, the number of measurements required to estimate expected values of observables with classical shadows can be up to 16 times lower than with direct-observable estimation. Furthermore, by analyzing complete graphs, we numerically confirm logarithmic growth in the required number of measurements relative to the number of observables, reinforcing that classical shadows can be a useful tool for estimating low-locality Pauli observables in quantum algorithms.
The feedback-based algorithm for quantum optimization (FALQON), which is an extension of the quantum approximate optimization algorithm (QAOA), is a promising approach for finding approximate solutions to combinatorial optimization problems. The FALQON avoids the optimization of variational parameters by using information derived from iterative measurements. To solve a constrained combinatorial optimization problem, it is sometimes more efficient to use an XY mixer rather than the conventional X mixer. We applied the FALQON with the XY mixer to graph coloring and investigated the expectation value of the problem Hamiltonian, success probability of graph coloring, and fair sampling for several small-scale problems. The FALQON with the XY mixer exhibited better performance than that with the X mixer.
We introduce a quantum algorithm that produces approximate solutions for combinatorial optimization problems. The algorithm depends on a positive integer p and the quality of the approximation improves as p is increased. The quantum circuit that implements the algorithm consists of unitary gates whose locality is at most the locality of the objective function whose optimum is sought. The depth of the circuit grows linearly with p times (at worst) the number of constraints. If p is fixed, that is, independent of the input size, the algorithm makes use of efficient classical preprocessing. If p grows with the input size a different strategy is proposed. We study the algorithm as applied to MaxCut on regular graphs and analyze its performance on 2-regular and 3-regular graphs for fixed p. For p = 1, on 3-regular graphs the quantum algorithm always finds a cut that is at least 0.6924 times the size of the optimal cut.