Methods to find the solution state for optimization problems encoded into Ising Hamiltonians are a very active area of current research. In this work we compare the quantum approximate optimization algorithm (QAOA) with multi-stage quantum walks (MSQW). Both can be used as variational quantum algorithms, where the control parameters are optimized classically. A fair comparison requires both quantum and classical resources to be assessed. Alternatively, parameters can be chosen heuristically, as we do in this work, providing a simpler setting for comparisons. Using both numerical and analytical methods, we obtain evidence that MSQW outperforms QAOA, using equivalent resources. We also show numerically for random spin glass ground state problems that MSQW performs well even for few stages and heuristic parameters, with no classical optimization.
Methods to find the solution state for optimization problems encoded into Ising Hamiltonians are a very active area of current research. In this work we compare the quantum approximate optimization algorithm (QAOA) with multi-stage quantum walks (MSQW). Both can be used as variational quantum algorithms, where the control parameters are optimized classically. A fair comparison requires both quantum and classical resources to be assessed. Alternatively, parameters can be chosen heuristically, as we do in this work, providing a simpler setting for comparisons. Using both numerical and analytical methods, we obtain evidence that MSQW outperforms QAOA, using equivalent resources. We also show numerically for random spin glass ground state problems that MSQW performs well even for few stages and heuristic parameters, with no classical optimization.
One way to approximate a quantum annealing schedule is to use multiple quantum walks chained together, without intermediate measurements, to produce a multi-stage quantum walk (MSQW). Previous work has shown that a MSQW is better than QAOA (quantum alternating operator ansatz) for solving optimization tasks using multiple stages [Gerblich et al, arXiv:2407.06663]. In this work, we develop an efficient heuristic for choosing the free parameters in MSQW, and use it to obtain improved scaling compared to single stage quantum walks. We show numerically that the heuristic works well for problems with a large minimum energy gap, giving a polynomial scaling in the number of stages, and leading to an overall algorithm that scales polynomially in time. For problems with a small minimum gap, the scaling breaks down such that adding more stages decreases the success probability, leading to an overall scaling that is exponential in time as expected. Our methods are general and can be applied to any optimization problem to obtain good annealing schedules.
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.
The quantum approximate optimization algorithm (QAOA) employs variational states generated by a parameterized quantum circuit to maximize the expected value of a Hamiltonian encoding a classical cost function. Whether or not the QAOA can outperform classical algorithms in some tasks is an actively debated question. Our work exposes fundamental limitations of the QAOA resulting from the symmetry and the locality of variational states. A surprising consequence of our results is that the classical Goemans-Williamson algorithm outperforms the QAOA for certain instances of MaxCut, at any constant level. To overcome these limitations, we propose a nonlocal version of the QAOA and give numerical evidence that it significantly outperforms the standard QAOA for frustrated Ising models.
Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.
The Quantum Approximate Optimization Algorithm with Quantum Walk Search (QAOA-QWS) is proposed as a hybrid quantum framework to address the ternary matching problem in rural cultural tourism resource allocation. The tripartite matching constraints and multi-objective optimization criteria are first encoded into an Ising-type cost Hamiltonian, where feasible allocations correspond to low-energy eigenstates. QAOA then executes parameterized quantum evolution to compress the exponential solution space into a high-quality approximate subspace dominated by low-energy matching states. Subsequently, QWS operates on the constraint-induced subgraph to directionally amplify the amplitudes of optimal ternary configurations through structured quantum walks, enabling efficient extraction of the global optimum via quantum measurement. Experimental validation across five progressively scaled instances ranging from 1,000 to 100,000 tourists demonstrates that QAOA-QWS achieves an expected objective value of 0.89, a tourist satisfaction rate of 0.87, an ICH coverage rate of 0.86, and an overall constraint satisfaction rate of 0.92 at the largest scale, significantly outperforming classical genetic and simulated annealing algorithms. Complexity analysis confirms that the proposed approach reduces the time complexity from exponential scaling with the problem size to a combination of polynomial and sub-linear square-root scaling relative to the feasible solution subspace, establishing a theoretical foundation for exponential acceleration in rural cultural tourism resource allocation. This framework establishes a theoretical foundation for exponentially accelerated quantum optimization in combinatorial resource allocation problems.
The Quantum Approximate Optimization Algorithm (QAOA) was developed to tackle combinatorial optimization problems, such as the Travelling Salesman Problem (TSP), by approximating solutions through quantum mechanics. QAOA utilizes a unitary transformation to prepare a quantum state that encodes a potential solution, with the parameters of the unitary optimized by a classical optimizer. This study evaluates QAOA's performance on the NP-hard TSP, comparing the standard version of the algorithm from Farhi \cite{qaoa} and an enhancement, Warm-Start QAOA \cite{warmstart}, to a classical solver. The TSP seeks the shortest possible route that visits a set of cities, a problem that is amenable to quantum formulation using platforms like Qiskit. Warm-Start QAOA initializes the algorithm's parameters based on a solution to a relaxed version of the problem, offering potential improvements in optimization efficiency. By comparing these quantum algorithms to a classical solver, we provide a comprehensive assessment of their performance across key metrics, including route quality, execution time, and scalability. Through this analysis, we highlight the relative strengths and weaknesses of QAOA and its warm-start variant for solving the TSP, alongside the classical approach, offering insights into their potential for route optimization and practical applications in realworld settings. We conclude that, while the classical solver significantly outperforms QAOA and warm-start QAOA at smaller-scale problem cases, warm-Start QAOA has the potential to yield advantages at a larger scale when run on NISQ-era noisy hardware.