Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2412.13345 · Information Processing Letters

On quantum lower bounds for local search via congestion and expansion

Simina Brânzei, Nicholas Recker

Published Oct 1, 2026• 0 citations
arXivHTMLPDF
DOI
10.1016/j.ipl.2026.106676

Related papers

Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs

Hang Dinh, Alexander C. Russell

Lecture notes in computer science•Aug 27, 2008•22 citations

A lower bound for quantum search of an ordered list

Harry Buhrman, Ronald de Wolf

Information Processing Letters•Jun 1, 1999•18 citations

Congestion-free routing on quantum chips

Mithilesh Kumar, Yusuf Tahir, Varun Daiya +2 more

Limited connectivity makes nonlocal quantum gates expensive on near-neighbor hardware, where compilation typically relies on SWAP transport, inheriting both depth overhead and path congestion. We present a swap-free routing framework in which higher levels of a qudit act as orthogonal spectral buses that transport control information without moving the computational state. We show that exact congestion relief in nearest-neighbor architectures requires local Hilbert-space expansion. In this model, a nonlocal operation over a path of length $L$ requires $2L+1$ logical routing primitives, compared to the $3L$ baseline. Overlapping routes remain distinguishable through bus labels encoded in the same physical qudits. This routing algebra extends to Boolean fan-in at a common target: multiple controls arriving on distinct buses trigger a local unitary based on an arbitrary Boolean function of bus digits, yielding multi-control operations of depth $2L + D_g + O(1)$ for fan-in size $K$ and target-synthesis cost $D_g$. We prove decodability, reversibility, and correctness for CNOT and Boolean fan-in, along with a state-count lower bound $d \geq 2^{K+1}$ for exact overlap routing. Cirq simulations confirm single-control correctness and zero crosstalk. Compiler-level benchmarks on QFT, QAOA, and mirror-interaction circuits verify the predicted congestion law and transport reduction. Noisy QuTiP simulations show that the architectural advantage depends on higher-level coherence and speed. These results identify spectral qudit routing as a congestion-relief architecture that separates nonlocal control delivery from local target-side aggregation, providing a minimal mechanism for overcoming qubit routing limitations.

quant-pharXiv:2604.27015•Physical Review A•Apr 30, 2026•0 citations

Optimal Quantum Adversary Lower Bounds for Ordered Search

Andrew M. Childs, Troy Lee

arXiv:0708.3396•Lecture notes in computer science•Jan 1, 2008•20 citations

On the Quantum Query Complexity of Local Search in Two and Three Dimensions

Xiaoming Sun, Andrew Chi-Chih Yao

Algorithmica•Jan 28, 2008•8 citations

Quantum and randomized lower bounds for local search on vertex-transitive graphs

Hang Dinh, Alexander C. Russell

We study the problem of \emph{local search} on a graph. Given a real-valued black-box function $f$ on the graph's vertices, this is the problem of determining a local minimum of $f$---a vertex $v$ for which $f(v)$ is no more than $f$ evaluated at any of $v$'s neighbors. In 1983, Aldous gave the first strong lower bounds for the problem, showing that any randomized algorithm requires $\Omega(2^{n/2 - o(n)} )$ queries to determine a local minima on the $n$-dimensional hypercube. The next major step forward was not until 2004 when Aaronson, introducing a new method for query complexity bounds, both strengthened this lower bound to $\Omega(2^{n/2}/n^2)$ and gave an analogous lower bound on the quantum query complexity. While these bounds are very strong, they are known only for narrow families of graphs (hypercubes and grids). We show how to generalize Aaronson's techniques in order to give randomized (and quantum) lower bounds on the query complexity of local search for the family of vertex-transitive graphs. In particular, we show that for any vertex-transitive graph $G$ of $N$ vertices and diameter $d$, the randomized and quantum query complexities for local search on $G$ are $\Omega\left({\sqrt{N}}/{d\log N}\right)$ and $\Omega\left({\sqrt[4]{N}}/{\sqrt{d\log N}}\right)$, respectively.

arXiv:0806.3437•Quantum Information and Computation•Jul 1, 2010•1 citation
Limited connectivity makes nonlocal quantum gates expensive on near-neighbor hardware, where compilation typically relies on SWAP transport, inheriting both depth overhead and path congestion. We present a swap-free routing framework in which higher levels of a qudit act as orthogonal spectral buses that transport control information without moving the computational state. We show that exact congestion relief in nearest-neighbor architectures requires local Hilbert-space expansion. In this model, a nonlocal operation over a path of length LLL requires 2L+12L+12L+1 logical routing primitives, compared to the 3L3L3L baseline. Overlapping routes remain distinguishable through bus labels encoded in the same physical qudits. This routing algebra extends to Boolean fan-in at a common target: multiple controls arriving on distinct buses trigger a local unitary based on an arbitrary Boolean function of bus digits, yielding multi-control operations of depth 2L+Dg+O(1)2L + D_g + O(1)2L+Dg​+O(1) for fan-in size KKK and target-synthesis cost DgD_gDg​. We prove decodability, reversibility, and correctness for CNOT and Boolean fan-in, along with a state-count lower bound d≥2K+1d \geq 2^{K+1}d≥2K+1 for exact overlap routing. Cirq simulations confirm single-control correctness and zero crosstalk. Compiler-level benchmarks on QFT, QAOA, and mirror-interaction circuits verify the predicted congestion law and transport reduction. Noisy QuTiP simulations show that the architectural advantage depends on higher-level coherence and speed. These results identify spectral qudit routing as a congestion-relief architecture that separates nonlocal control delivery from local target-side aggregation, providing a minimal mechanism for overcoming qubit routing limitations.
We study the problem of \emph{local search} on a graph. Given a real-valued black-box function fff on the graph's vertices, this is the problem of determining a local minimum of fff---a vertex vvv for which f(v)f(v)f(v) is no more than fff evaluated at any of vvv's neighbors. In 1983, Aldous gave the first strong lower bounds for the problem, showing that any randomized algorithm requires Ω(2n/2−o(n))\Omega(2^{n/2 - o(n)} )Ω(2n/2−o(n)) queries to determine a local minima on the nnn-dimensional hypercube. The next major step forward was not until 2004 when Aaronson, introducing a new method for query complexity bounds, both strengthened this lower bound to Ω(2n/2/n2)\Omega(2^{n/2}/n^2)Ω(2n/2/n2) and gave an analogous lower bound on the quantum query complexity. While these bounds are very strong, they are known only for narrow families of graphs (hypercubes and grids). We show how to generalize Aaronson's techniques in order to give randomized (and quantum) lower bounds on the query complexity of local search for the family of vertex-transitive graphs. In particular, we show that for any vertex-transitive graph GGG of NNN vertices and diameter ddd, the randomized and quantum query complexities for local search on GGG are Ω(N/dlog⁡N)\Omega\left({\sqrt{N}}/{d\log N}\right)Ω(N​/dlogN) and Ω(N4/dlog⁡N)\Omega\left({\sqrt[4]{N}}/{\sqrt{d\log N}}\right)Ω(4N​/dlogN​), respectively.