QAOA achieves the conjectured optimal (2p+1)/(2p+2) edge-cut fraction on cycle graphs at depth p by equivalence to Laurent polynomial optimization using quantum signal processing.
arXiv:quant-ph/9901059 , Title =
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
We consider the problem of inserting one item into a list of N-1 ordered items. We previously showed that no quantum algorithm could solve this problem in fewer than log N/(2 log log N) queries, for N large. We transform the problem into a "translationally invariant" problem and restrict attention to invariant algorithms. We construct the "greedy" invariant algorithm and show numerically that it outperforms the best classical algorithm for various N. We also find invariant algorithms that succeed exactly in fewer queries than is classically possible, and iterating one of them shows that the insertion problem can be solved in fewer than 0.53 log N quantum queries for large N (where log N is the classical lower bound). We don't know whether a o(log N) algorithm exists.
fields
quant-ph 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
New combinatorial proofs and circuit designs for quantum error correction reduce physical qubit overhead by up to 10x and time overhead by 2-6x for codes including Steane, Golay, and surface codes.
citing papers explorer
-
The QAOA on the ring of disagrees
QAOA achieves the conjectured optimal (2p+1)/(2p+2) edge-cut fraction on cycle graphs at depth p by equivalence to Laurent polynomial optimization using quantum signal processing.
-
Lower overhead fault-tolerant building blocks for noisy quantum computers
New combinatorial proofs and circuit designs for quantum error correction reduce physical qubit overhead by up to 10x and time overhead by 2-6x for codes including Steane, Golay, and surface codes.