pith. sign in

arxiv: 1907.00529 · v1 · pith:OR2MQFIWnew · submitted 2019-07-01 · 💻 cs.DS · quant-ph

Exponential-time quantum algorithms for graph coloring problems

Kazuya Shimizu , Ryuhei Mori This is my paper

Pith reviewed 2026-05-25 11:55 UTC · model grok-4.3

classification 💻 cs.DS quant-ph
keywords quantum algorithmsgraph coloringchromatic numberGrover searchdynamic programmingexponential timebranching algorithmsQRAM
0
0 comments X

The pith

A quantum algorithm computes the chromatic number of an n-vertex graph in O(1.9140^n) time using QRAM.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a quantum algorithm that finds the chromatic number of an n-vertex graph in O(1.9140^n) time with exponential space. It applies Grover search inside a quantum dynamic programming framework to speed up classical branching algorithms for colorability. A second result gives a polynomial-space quantum algorithm for the 20-coloring problem that runs in O(1.9575^n) time without QRAM. These bounds improve on the classical requirement of at least 2^n time for k-colorability when k is at least 5. The work shows how certain classical exponential-time procedures can be quadratically accelerated by quantum search when QRAM is available.

Core claim

The authors construct an exponential-space quantum algorithm for the chromatic number that runs in O(1.9140^n) time by combining Ambainis-style quantum dynamic programming with Grover search over the branches of classical k-colorability algorithms; they also exhibit a polynomial-space quantum algorithm for 20-coloring that achieves O(1.9575^n) time by showing that certain classical (4-ε)^n procedures admit a quadratic Grover speedup.

What carries the argument

Quantum dynamic programming that applies Grover search to the branching steps of classical k-colorability algorithms.

If this is right

  • The chromatic number can be decided in time strictly below 2^n on a quantum computer with QRAM.
  • For the fixed parameter k=20, graph 20-colorability admits a polynomial-space quantum algorithm with time O(1.9575^n).
  • Any classical branching algorithm whose work per node is polynomial can be quadratically accelerated by Grover search inside the quantum DP framework.
  • The same technique extends the quantum speedup previously shown for other NP-hard problems to the full chromatic-number computation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the same embedding works for other graph problems whose classical solutions rely on branching, quantum quadratic speedups could appear across a wider family of exponential-time algorithms.
  • Practical deployment would still require large-scale QRAM whose construction cost is not analyzed here.
  • The polynomial-space result suggests that even without QRAM, modest constant-factor improvements over 2^n remain possible for specific coloring thresholds.

Load-bearing premise

The overhead of embedding the branching algorithms inside quantum dynamic programming does not erase the quadratic improvement promised by Grover search.

What would settle it

An explicit calculation or implementation on small n that shows the total quantum runtime exceeds O(1.9140^n) because the dynamic-programming embedding cost dominates the Grover gain.

read the original abstract

The fastest known classical algorithm deciding the $k$-colorability of $n$-vertex graph requires running time $\Omega(2^n)$ for $k\ge 5$. In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time $O(1.9140^n)$ using quantum random access memory (QRAM). Our approach is based on Ambainis et al's quantum dynamic programming with applications of Grover's search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph $20$-coloring problem with running time $O(1.9575^n)$. In the polynomial-space quantum algorithm, we essentially show $(4-\epsilon)^n$-time classical algorithms that can be improved quadratically by Grover's search.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript claims an exponential-space quantum algorithm for computing the chromatic number of an n-vertex graph in O(1.9140^n) time using QRAM, obtained by extending Ambainis et al.'s quantum dynamic programming framework with applications of Grover search to classical branching algorithms for k-colorability. It further claims a polynomial-space quantum algorithm (no QRAM) for deciding 20-colorability with running time O(1.9575^n), by first establishing classical (4-ε)^n algorithms that admit a quadratic Grover improvement.

Significance. If the stated bounds hold, the work would supply the first quantum exponential-time algorithms for chromatic number that improve quadratically on the classical Ω(2^n) barrier for k≥5. The explicit recurrences, Grover iteration counts, and overhead analysis folded into the final bases (1.9140 and 1.9575) constitute a concrete, verifiable contribution that extends an existing quantum-DP technique to a new family of problems.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'the graph 20-coloring problem' is slightly imprecise; it should read 'deciding whether a graph is 20-colorable' to match the decision-problem formulation used elsewhere.
  2. The QRAM access-cost model is stated explicitly, but a short sentence clarifying how the QRAM cost is charged in the recurrence (per query or per block) would remove any residual ambiguity for readers unfamiliar with the model.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript, the positive summary of our contributions, and the recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper extends Ambainis et al.'s external quantum DP framework (non-overlapping authors) to chromatic number via explicit Grover applications on known classical branching recurrences for k-colorability, with QRAM costs folded into the final exponent 1.9140. The polynomial-space claim similarly derives from showing independent classical (4-ε)^n algorithms that admit quadratic Grover speedup. No equation reduces the output bound to a quantity defined by the authors' own prior equations, no self-citation is load-bearing, and no fitted parameter is relabeled as a prediction. The central result therefore stands on independent classical branching literature plus the cited quantum technique.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based on abstract only; the central claim rests on the applicability of Ambainis et al.'s quantum dynamic programming to coloring branching algorithms and on the existence of QRAM. No free parameters or invented entities are visible; the numerical bases are presumably obtained by solving recurrences but details are unavailable.

axioms (2)
  • domain assumption Quantum random access memory (QRAM) is available and can be used without additional asymptotic cost in the exponential-space algorithm.
    Explicitly invoked for the O(1.9140^n) bound in the abstract.
  • domain assumption Grover search yields a quadratic speedup on the classical (4-ε)^n branching algorithms for 20-coloring without hidden overheads that would invalidate the O(1.9575^n) bound.
    Stated as the basis for the polynomial-space result in the abstract.

pith-pipeline@v0.9.0 · 5653 in / 1501 out tokens · 48553 ms · 2026-05-25T11:55:29.736289+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages · 1 internal anchor

  1. [1]

    Quantum speedups for exponential-time dynamic program ming algorithms

    Andris Ambainis, Kaspars Balodis, J¯ anis Iraids, Martins Kokainis, Kriˇ sj¯ anis Pr¯ usis, and Jevg¯ enijs Vihrovs. Quantum speedups for exponential-time dynamic program ming algorithms. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algo rithms (SODA’19) , pages 1783–1793. SIAM, 2019

    work page 2019

  2. [2]

    3-coloring in time O(1

    Richard Beigel and David Eppstein. 3-coloring in time O(1. 3289n). Journal of Algorithms , 54(2):168– 204, 2005

    work page 2005

  3. [3]

    Inclusion–exclusion alg orithms for counting set partitions

    Andreas Bj¨ orklund and Thore Husfeldt. Inclusion–exclusion alg orithms for counting set partitions. In Proceedings of the Forty-seventh Annual IEEE Symposium on F oundations of Computer Science (FOCS’06), pages 575–582. IEEE, 2006

    work page 2006

  4. [4]

    Exact algorithms for e xact satisfiability and number of perfect matchings

    Andreas Bj¨ orklund and Thore Husfeldt. Exact algorithms for e xact satisfiability and number of perfect matchings. Algorithmica, 52(2):226–249, 2008

    work page 2008

  5. [5]

    Set pa rtitioning via inclusion-exclusion

    Andreas Bj¨ orklund, Thore Husfeldt, and Mikko Koivisto. Set pa rtitioning via inclusion-exclusion. SIAM Journal on Computing , 39(2):546–563, 2009

    work page 2009

  6. [6]

    Tight bounds on quantum searching

    Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics , 46(4-5):493–505, 1998

    work page 1998

  7. [7]

    Jesper M. Byskov. Enumerating maximal independent sets with a pplications to graph colouring. Oper- ations Research Letters , 32(6):547–556, 2004

    work page 2004

  8. [8]

    On prob lems as hard as CNF-SAT

    Marek Cygan, Holger Dell, Daniel Lokshtanov, D´ aniel Marx, Jes per Nederlof, Yoshio Okamoto, Ra- mamohan Paturi, Saket Saurabh, and Magnus Wahlstr¨ om. On prob lems as hard as CNF-SAT. ACM Transactions on Algorithms (TALG) , 12(3):41, 2016

    work page 2016

  9. [9]

    A Quantum Algorithm for Finding the Minimum

    Christoph D¨ urr and Peter Høyer. A quantum algorithm for findin g the minimum. arXiv preprint quant-ph/9607014, 1996. 10 Table 2: Precise values of f ∗ k . k f ∗ k 2f ∗ k k′ 3 0.2050919796 1.1527598391 4 0.4038189847 1.3230054317 1 5 0.5552479972 1.4694212030 1 6 0.6098104848 1.5260587298 3 7 0.7233677736 1.6510316464 3 8 0.7298058730 1.6584159226 4 9 0.8...

    work page internal anchor Pith review Pith/arXiv arXiv 1996

  10. [10]

    Fomin, Serge Gaspers, and Saket Saurabh

    Fedor V. Fomin, Serge Gaspers, and Saket Saurabh. Improve d exact algorithms for counting 3-and 4-colorings. In Proceedings of the Thirteenth Annual International Comput ing and Combinatorics Con- ference (COCOON’07), pages 65–74. Springer, 2007

    work page 2007

  11. [11]

    Fomin and Dieter Kratsch

    Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms . Springer-Verlag, 2010

    work page 2010

  12. [12]

    Solving NP-complete problems with quantum sear ch

    Martin F¨ urer. Solving NP-complete problems with quantum sear ch. In Latin American Symposium on Theoretical Informatics (LATIN’08), pages 784–792. Springer, 2008

    work page 2008

  13. [13]

    Faster graph coloring in polyn omial space

    Serge Gaspers and Edward J Lee. Faster graph coloring in polyn omial space. In Proceedings of the Twenty-third Annual International Computing and Combinat orics Conference (COCOON’17) , pages 371–383. Springer, 2017

    work page 2017

  14. [14]

    Quant um random access memory

    Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quant um random access memory. Physical Review Letters, 100(16):160501, 2008

    work page 2008

  15. [15]

    Lov K. Grover. A fast quantum mechanical algorithm for datab ase search. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing ( STOC’96), pages 212–219. ACM, 1996

    work page 1996

  16. [16]

    An O∗ (2n) algorithm for graph coloring and other partitioning problems via inclu sion– exclusion

    Mikko Koivisto. An O∗ (2n) algorithm for graph coloring and other partitioning problems via inclu sion– exclusion. In Proceedings of the Forty-seventh Annual IEEE Symposium on F oundations of Computer Science (FOCS’06), pages 583–590. IEEE, 2006

    work page 2006

  17. [17]

    Eugene L. Lawler. A note on the complexity of the chromatic num ber problem. Inf. Proc. Lett., 5:66–67, 1976. A Calculations of the exponents f∗ k Here, we consider calculations of the exponents f ∗ k . This problem was not dealt in [1]. Fortunately, the calculation of f ∗ k is not difficult. Non-trivial part is the calculation of max { max δ∈ [k′/k, 1] {h(...

    work page 1976