Empirical Evaluation of the Approximation Ratio in Scalable Fixed-Point QAOA
Andrey Yu. Chernyavskiy 1, Denis A. Kulikov 1,2, Boris I. Bantysh 1;
1 Russian Quantum Center, Skolkovo, Moscow 121205, Russia
2 Moscow Institute of Physics and Technology, Dolgoprudny 141700, Russia
Abstract
A fixed-parameter approach to the Quantum Approximate Optimization Algorithm (QAOA) is considered, based on three modifications: targeting approximate solutions, scaling the circuit depth proportionally to the problem size, and normalizing the QUBO matrices to unit Frobenius norm. Taken together, these modifications make the required number of quantum-circuit executions (shots) effectively independent of the problem size.
A detailed numerical analysis is performed to investigate the relationship between the problem size, the approximation ratio, and the average number of quantum-circuit executions required to obtain a solution of a prescribed quality. For random QUBO instances with up to 30 variables, the dependence of the approximation ratio on the number of shots is studied. Across the entire range considered, increasing the number of shots is shown to improve the approximation ratio, followed by saturation. A three-parameter model is proposed to describe the observed dependencies.
Speaker
Andrey Yu. Chernyavskiy
Russian Quantum Center
Russia
Discussion
Ask question
