A universal quantum algorithm for weighted maximum cut and Ising problems

DOI10.1007/S11128-023-04025-XMaRDI QIDQ6171439zbMATH OpenFDO

Authors Natacha Kuete Meli, Florian Mannel, Jan Lellmann

Publication date 11 August 2023

Published in Quantum Information Processing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2306.06539

zbMATH Keywords

hybrid quantum circuitsIsing modelquantum algorithmsvariational quantum circuitsweighted maximum cut

Mathematics Subject Classification ID

Quantum computation (81P68)

Abstract: We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary combinatorial problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system. The system is enforced to evolve towards the ground state of the problem Hamiltonian by optimizing a set of angles using normalized gradient descent. Experimentally, our algorithm outperforms the state-of-the-art quantum approximate optimization algorithm on random fully connected graphs and challenges D-Wave quantum annealers by producing good approximate solutions. Source code and data files are publicly available.

Recommendations

• Solving MaxCut with quantum imaginary time evolution
• Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs
• scientific article; zbMATH DE number 7651034
• Faster exact solution of sparse maxcut and QUBO problems

Cites work

• A universal quantum algorithm for weighted maximum cut and Ising problems
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Benchmarking the quantum approximate optimization algorithm
• Bounds for the adiabatic approximation with applications to quantum computation
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• scientific article; zbMATH DE number 5899272 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 653035 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Logical Reversibility of Computation
• Lower bounds on circuit depth of the quantum approximate optimization algorithm
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum computation and quantum information. 10th anniversary edition
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Revisiting Normalized Gradient Descent: Fast Evasion of Saddle Points
• Spectral gap amplification
• The two-dimensional Ising model

Cited in

(4)

• Optimality proofs of quantum weight decision algorithms
• A universal quantum algorithm for weighted maximum cut and Ising problems
• Solving MaxCut with quantum imaginary time evolution
• A copositive framework for analysis of hybrid Ising-classical algorithms

This page was built for publication: A universal quantum algorithm for weighted maximum cut and Ising problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6171439)