Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) requires that circuit parameters are determined that allow one to sample from high-quality solutions to combinatorial optimization problems. Such parameters can be obtained using either costly outer-loop optimization procedures and repeated calls to a quantum computer or, alternatively, via analytical means. In this work we demonstrate that if one knows the probability density function describing how the objective function of a problem is distributed, that the calculation of the expectation of such a problem Hamiltonian under a Grover-driven, QAOA-prepared state can be performed independently of system size. Such calculations can help deliver insights into the performance of and predictability of angles in QAOA in the limit of large problem sizes, in particular, for the number partitioning problem.

arXiv comment13 pages, 7 figures

References in corpus (19)

• Quantum Computing in the NISQ era and beyond
• Elementary gates for quantum computation
• Barren plateaus in quantum neural network training landscapes
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Grover's quantum searching algorithm is optimal
• Quantum Search by Local Adiabatic Evolution
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Reachability Deficits in Quantum Approximate Optimization
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Parameter Concentration in Quantum Approximate Optimization
• Random Costs in Combinatorial Optimization
• On the Universality of the Quantum Approximate Optimization Algorithm
• Linear-Depth Quantum Circuits for n-qubit Toffoli gates with no Ancilla
• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
• Finding spin-glass ground states using quantum walks
• Quantum Algorithms for Scientific Computing and Approximate Optimization
• Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian
• Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size
• Progress towards analytically optimal angles in quantum approximate optimisation

Cited by in corpus (3)

• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios