Linear-depth quantum oracles for clique problems from edge colorings and graph states, with linear non-Clifford cost and a provably bounded-error k-clique search

Abstract:Quantum algorithms for clique problems are usually analyzed in the query model, where the graph is accessed through an oracle of unit cost. When the oracle must itself be compiled into gates, published $k$-clique circuits have depth quadratic in the number $n$ of vertices, and every oracle that counts edges spends at least one non-Clifford gate per edge. We first show that scheduling the commuting edge gates by a proper edge coloring yields adjacency-type oracles, including an exact $k$-clique oracle, whose depth and width are linear in $n$, within a logarithmic factor of a depth--width lower bound. Our central result is a $k$-clique oracle in which the graph enters only through the Clifford gate that prepares a graph state, so that its non-Clifford cost is linear in $n$ for every graph. We analyze this oracle exactly: on a candidate vertex set it acts as a reflection whose overlap is $-1$ for cliques and, as we prove, at most $5/8$ in modulus otherwise, a tight bound that tends to $1/2$ as the candidate set grows. A two-qubit phase-estimation filter turns the reflection into a one-sided bounded-error phase oracle, and amplitude amplification then finds a $k$-clique with $O(\sqrt{\binom nk})$ oracle calls, each of depth $O(\Delta+\log n)$ for maximum degree $\Delta$. The guarantee holds for two or more estimation registers; exact simulations on $312$ induced subgraphs of two brain networks confirm it and show that the cheaper single-register variant performs nearly as well.

arXiv:2308.16827 [quant-ph]

(or arXiv:2308.16827v3 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2308.16827 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.