We present benchmarking results for the non-variational Quantum Walk Optimisation Algorithm (non-variational QWOA) applied to the weighted maxcut problem, using classical simulations for problem sizes up to $n = 31$ . The amplified quantum state, prepared using a quadratic number of alternating unitaries, achieves a constant average-case measurement probability for globally optimal solutions across these problem sizes. This behaviour contrasts with that of classical heuristics, which, for NP-hard optimisation problems, typically exhibit solve probabilities that decay as problem size increases. Performance comparisons with two local-search heuristics on the same benchmark instances suggest that the non-variational QWOA may offer a meaningful advantage by scaling more favourably with problem size. These results provide supporting evidence for the potential of this quantum heuristic to achieve quantum advantage, though further work is needed to assess whether the observed performance scaling persists at larger problem sizes, and to confirm whether similar performance trends are observed for the other problem classes to which the non-variational QWOA is designed to generalise.We present benchmarking results for the non-variational Quantum Walk Optimisation Algorithm (non-variational QWOA) applied to the weighted maxcut problem, using classical simulations for problem sizes up to $n = 31$. The amplified quantum state, prepared using a quadratic number of alternating unitaries, achieves a constant average-case measurement probability for globally optimal solutions across these problem sizes. This behaviour contrasts with that of classical heuristics, which, for NP-hard optimisation problems, typically exhibit solve probabilities that decay as problem size increases. Performance comparisons with two local-search heuristics on the same benchmark instances suggest that the non-variational QWOA may offer a meaningful advantage by scaling more favourably with problem size. These results provide supporting evidence for the potential of this quantum heuristic to achieve quantum advantage, though further work is needed to assess whether the observed performance scaling persists at larger problem sizes, and to confirm whether similar performance trends are observed for the other problem classes to which the non-variational QWOA is designed to generalise.

arXiv:2505.24191May 30, 20250 citations

Discrete-time quantum walk-based optimization algorithm

Ioannis Liliopoulos, Georgios D. Varsamis, Ioannis G. Karafyllidis

Quantum Information ProcessingJan 17, 20247 citations

Approximate optimization of the MaxCut problem with a local spin algorithm

Aniruddha Bapat, Stephen P. Jordan

Local tensor methods are a class of optimization algorithms introduced in [Hastings, arXiv:1905.07047v2] as a classical analogue of the quantum approximate optimization algorithm. These algorithms treat the cost function as a Hamiltonian on spin degrees of freedom and simulate the relaxation of the system to a low-energy configuration using local update rules on the spins. Whereas the emphasis in Hastings' work was on theoretical worst-case analysis, we here investigate the underlying dynamics of the algorithm, and find that the local tensor method closely follows discretized, imaginary-time dynamics of the system under the problem Hamiltonian. Then, we study practical performance through benchmarking experiments on instances of the MaxCut problem. Through heuristic arguments we propose formulas for choosing the hyperparameters of the algorithm which are found to be in good agreement with the optimal choices determined from experiment. We observe that the local tensor method is closely related to gradient descent on a relaxation of MaxCut to continuous variables but consistently outperforms gradient descent in all instances tested. We find that time to solution achieved by the local tensor method is highly uncorrelated with that achieved by a widely used commercial optimization package; on some MaxCut instances the local tensor method beats the commercial solver in time to solution by up to two orders of magnitude and vice versa.Local tensor methods are a class of optimization algorithms introduced in [Hastings, arXiv:1905.07047v2] as a classical analogue of the quantum approximate optimization algorithm. These algorithms treat the cost function as a Hamiltonian on spin degrees of freedom and simulate the relaxation of the system to a low-energy configuration using local update rules on the spins. Whereas the emphasis in Hastings' work was on theoretical worst-case analysis, we here investigate the underlying dynamics of the algorithm, and find that the local tensor method closely follows discretized, imaginary-time dynamics of the system under the problem Hamiltonian. Then, we study practical performance through benchmarking experiments on instances of the MaxCut problem. Through heuristic arguments we propose formulas for choosing the hyperparameters of the algorithm which are found to be in good agreement with the optimal choices determined from experiment. We observe that the local tensor method is closely related to gradient descent on a relaxation of MaxCut to continuous variables but consistently outperforms gradient descent in all instances tested. We find that time to solution achieved by the local tensor method is highly uncorrelated with that achieved by a widely used commercial optimization package; on some MaxCut instances the local tensor method beats the commercial solver in time to solution by up to two orders of magnitude and vice versa.

arXiv:2008.06054Physical Review AMay 12, 20214 citations

Parameter Setting in Quantum Approximate Optimization of Weighted Problems

Shree Hari Sureshbabu, Dylan Herman, Ruslan Shaydulin +4 more

Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate algorithm for solving combinatorial optimization problems on quantum computers. However, in many cases QAOA requires computationally intensive parameter optimization. The challenge of parameter optimization is particularly acute in the case of weighted problems, for which the eigenvalues of the phase operator are non-integer and the QAOA energy landscape is not periodic. In this work, we develop parameter setting heuristics for QAOA applied to a general class of weighted problems. First, we derive optimal parameters for QAOA with depth p=1 applied to the weighted MaxCut problem under different assumptions on the weights. In particular, we rigorously prove the conventional wisdom that in the average case the first local optimum near zero gives globally-optimal QAOA parameters. Second, for p≥1 we prove that the QAOA energy landscape for weighted MaxCut approaches that for the unweighted case under a simple rescaling of parameters. Therefore, we can use parameters previously obtained for unweighted MaxCut for weighted problems. Finally, we prove that for p=1 the QAOA objective sharply concentrates around its expectation, which means that our parameter setting rules hold with high probability for a random weighted instance. We numerically validate this approach on general weighted graphs and show that on average the QAOA energy with the proposed fixed parameters is only 1.1 percentage points away from that with optimized parameters. Third, we propose a general heuristic rescaling scheme inspired by the analytical results for weighted MaxCut and demonstrate its effectiveness using QAOA with the XY Hamming-weight-preserving mixer applied to the portfolio optimization problem. Our heuristic improves the convergence of local optimizers, reducing the number of iterations by 7.4x on average.Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate algorithm for solving combinatorial optimization problems on quantum computers. However, in many cases QAOA requires computationally intensive parameter optimization. The challenge of parameter optimization is particularly acute in the case of weighted problems, for which the eigenvalues of the phase operator are non-integer and the QAOA energy landscape is not periodic. In this work, we develop parameter setting heuristics for QAOA applied to a general class of weighted problems. First, we derive optimal parameters for QAOA with depth p=1 applied to the weighted MaxCut problem under different assumptions on the weights. In particular, we rigorously prove the conventional wisdom that in the average case the first local optimum near zero gives globally-optimal QAOA parameters. Second, for p≥1 we prove that the QAOA energy landscape for weighted MaxCut approaches that for the unweighted case under a simple rescaling of parameters. Therefore, we can use parameters previously obtained for unweighted MaxCut for weighted problems. Finally, we prove that for p=1 the QAOA objective sharply concentrates around its expectation, which means that our parameter setting rules hold with high probability for a random weighted instance. We numerically validate this approach on general weighted graphs and show that on average the QAOA energy with the proposed fixed parameters is only 1.1 percentage points away from that with optimized parameters. Third, we propose a general heuristic rescaling scheme inspired by the analytical results for weighted MaxCut and demonstrate its effectiveness using QAOA with the XY Hamming-weight-preserving mixer applied to the portfolio optimization problem. Our heuristic improves the convergence of local optimizers, reducing the number of iterations by 7.4x on average.

arXiv:2305.15201QuantumJan 18, 202441 citations

Benchmarking the quantum approximate optimization algorithm

Madita Willsch, Dennis Willsch, Fengping Jin +2 more

Jan 1, 2020109 citations

n = 31

. The amplified quantum state, prepared using a quadratic number of alternating unitaries, achieves a constant average-case measurement probability for globally optimal solutions across these problem sizes. This behaviour contrasts with that of classical heuristics, which, for NP-hard optimisation problems, typically exhibit solve probabilities that decay as problem size increases. Performance comparisons with two local-search heuristics on the same benchmark instances suggest that the non-variational QWOA may offer a meaningful advantage by scaling more favourably with problem size. These results provide supporting evidence for the potential of this quantum heuristic to achieve quantum advantage, though further work is needed to assess whether the observed performance scaling persists at larger problem sizes, and to confirm whether similar performance trends are observed for the other problem classes to which the non-variational QWOA is designed to generalise.