Depth analysis of the Quantum Approximate Optimization Algorithm with a Grover mixer
Abstract
We study the Quantum Approximate Optimization Algorithm with a Grover mixer and independently sampled cost and mixing angles. Under a lattice condition on the cost values carried by the initial state, we prove a depth-independent lower bound for the variance of the loss at every depth, together with the same bound for the derivative with respect to the final mixing angle. The estimate is instance-dependent and, for fixed locality, is inverse polynomial in the number of qubits for integer-valued local objective functions with uniformly bounded local terms, in particular for MaxCut. We also establish Grover-type reachability bounds showing that the depth required to approximate a prescribed carried eigenspace is bounded below by a constant multiple of the inverse square root of its initial probability.
Related
- Harmonic Reduction of Spin-Coupled Grover Walks on Hypercubes via Quantum Bernoulli Noises
- A new algorithm for topology optimization using a level-set method
- High-Rank Encoding Can Improve Approximate Quantum Error Correction
- Approximate Synthetic Spectra of Quantum Systems Associated with Compact Lie Groups
- Optimization of Quadratic Sieve Algorithm Implementation for Large Integer Factorization
BibTeX
@misc{bakalov2026depth,
title = {{Depth analysis of the Quantum Approximate Optimization Algorithm with a Grover mixer}},
author = {Bojko N. Bakalov and Dimitar Grantcharov},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17835},
eprint = {2609.17835},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17835},
}
RIS
TY - UNPB
TI - Depth analysis of the Quantum Approximate Optimization Algorithm with a Grover mixer
AU - Bojko N. Bakalov
AU - Dimitar Grantcharov
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17835
UR - https://arxiv.org/abs/2609.17835
AB - We study the Quantum Approximate Optimization Algorithm with a Grover mixer and independently sampled cost and mixing angles. Under a lattice condition on the cost values carried by the initial state, we prove a depth-independent lower bound for the variance of the loss at every depth, together with the same bound for the derivative with respect to the final mixing angle. The estimate is instance-dependent and, for fixed locality, is inverse polynomial in the number of qubits for integer-valued local objective functions with uniformly bounded local terms, in particular for MaxCut. We also establish Grover-type reachability bounds showing that the depth required to approximate a prescribed carried eigenspace is bounded below by a constant multiple of the inverse square root of its initial probability.
ER -