Pith. sign in

REVIEW 3 major objections 4 minor 77 references

Deterministic quantum search on all Laplacian integral graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A quantum algorithm based on a controlled intermittent quantum walk finds a marked vertex with certainty on any Laplacian integral graph, in total evolution time and query complexity $O(1/\sqrt{\varepsilon})$ when the marked fraction is…

desk verdict Clean QPE-based deterministic search that genuinely extends the known graph class; the only real fix is to state the connectedness assumption. read the letter →

arxiv 2506.21108 v1 pith:T3MLXGEK submitted 2025-06-26 quant-ph

Guanzhong Li , Jingquan Luo , Shiguang Feng , Lvzhou Li This is my paper · ORCID
classification quant-ph
keywords quantumspatialsearchdeterministicalgorithmLaplacianintegralgraphscontrolledintermittentwalkphaseestimationGrover
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper claims that spatial search — finding an unknown marked vertex of a graph — can be made deterministic for every Laplacian integral graph, meaning every graph whose Laplacian eigenvalues are all integers. The proposed algorithm runs a controlled intermittent quantum walk (CIQW) in which quantum phase estimation is used to build the exact reflection around the uniform superposition state. Wrapping that reflection with the phase oracle in Long's deterministic Grover iteration yields the marked vertex with certainty whenever the proportion $\varepsilon$ of marked vertices is known in advance, with total evolution time and query count both $O(1/\sqrt{\varepsilon})$. This would be the largest class of graphs known to admit deterministic quantum search, and it unifies earlier results that required vertex-transitivity or a single marked vertex.

What carries the argument

The central object is the controlled intermittent quantum walk (CIQW), a sequence of controlled continuous-time quantum walks $\Lambda_s(e^{iLt_j})$ interleaved with unitaries on the control register. The load-bearing mechanism is exact quantum phase estimation of $e^{i t_0 L}$ with a time step chosen so that every integer Laplacian eigenvalue $\lambda_k$ appears as the exactly representable $s$-bit phase $2\pi\lambda_k/2^s$. Flipping a phase on the $|0\cdots0\rangle$ outcome of that phase estimate therefore acts as $e^{i\beta|\pi\rangle\langle\pi|}$ on the walk space, and inverting the phase estimation uncomputes the register at no extra cost. The per-reflection evolution time is bounded by $4\pi$, independent of the number of vertices.

What would settle it

Simulate Algorithm 1 on a disconnected Laplacian integral graph — the disjoint union of two complete graphs, say — with a known marked set; because the zero eigenspace has dimension two, the reflection built by phase estimation is not the reflection about the uniform state, and the measured success probability will be strictly below 1, contradicting the theorem as stated.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 1: for any Laplacian integral graph, a CIQW-based algorithm finds a marked vertex with certainty in total evolution time $O(1/\sqrt{\varepsilon})$ and query complexity $O(1/\sqrt{\varepsilon})$, where $\varepsilon = \|\Pi_M |\pi\rangle\|^2$ is the fraction of marked vertices and is known in advance. The construction implements the generalized Grover operator $G(\alpha,\beta) = e^{i\beta|\pi\rangle\langle\pi|} e^{i\alpha\Pi_M}$ exactly. The key step is that because every Laplacian eigenvalue is an integer, quantum phase estimation on the unitary $e^{i t_0 L}$ returns the eigenvalue exactly on an $s$-qubit register, so a single conditional phase gate can implement exactly the reflection $e^{i\beta|\pi\rangle\langle\pi|}$; reversing the phase estimation restores the register. Long's lemma then gives the precise parameters $\alpha = \beta = 2\arcsin(\sin(\pi/(4k+2))/\sqrt{\varepsilon})$ for which $k = O(1/\sqrt{\varepsilon})$ iterations succeed with probability one.

Load-bearing premise

The proof requires the graph to be connected so the zero Laplacian eigenspace is one-dimensional and spanned by the uniform state; on a disconnected Laplacian integral graph the phase-estimation gate no longer implements the reflection about $|\pi\rangle$, so the theorem's literal claim for 'any' such graph is stronger than what the construction demonstrates.

Editorial extensions

If this is right

  • A single unified algorithm now covers the known Laplacian integral graph families — complete, Johnson, Kneser, Hamming, hypercube, Grassmann, rook, star, cocktail-party, and complete $k$-partite graphs — with $O(1/\sqrt{\varepsilon})$ walk time and query count.
  • Multiple marked vertices are handled directly, as long as their fraction $\varepsilon$ is known; previous deterministic schemes were limited to exactly one marked vertex.
  • When the continuous-time quantum walk has a poly-logarithmic gate circuit, the total gate complexity is $O(\mathrm{poly}(\log N)/\sqrt{\varepsilon})$, so deterministic search on those graphs is efficient in both time and gates.
  • The vertex-transitivity requirement disappears, so graphs such as the antiregular graphs, which the earlier alternating-walk algorithm could not address, are covered.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The exactness mechanism is not specific to Laplacians: any Hermitian matrix whose spectrum is exactly representable by phase estimation (for instance integer or dyadic-rational eigenvalues) should admit the same reflection-based deterministic search, so the scope may extend to other graph-associated matrices.
  • If the requirement that the marked fraction $\varepsilon$ be known in advance is relaxed, combining the CIQW reflection with fixed-point or robust Grover iterations is a natural next step; whether certainty can be retained without exact $\varepsilon$ is left open by the paper.
  • For disconnected integral graphs, a plausible repair is to decompose into connected components and run the search component-wise, or to replace the single reflection by a reflection about the entire zero-eigenspace projector; this would turn the literal claim for disconnected graphs into a testable extension.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes a deterministic quantum spatial search algorithm for Laplacian integral graphs, based on the controlled intermittent quantum walk (CIQW) model. The key idea is to use exact quantum phase estimation on the unitary e^{i t0 L}, where L is the graph Laplacian, to implement the phase shift e^{i β |π⟩⟨π|} around the uniform state |π⟩. Since Laplacian integral graphs have integer eigenvalues, the phase estimation is exact. The paper then invokes Long's deterministic Grover iteration to search for any predetermined fraction ε of marked vertices with certainty, claiming total evolution time O(1/√ε) and query complexity O(1/√ε). It also compares its scope and costs with the earlier work of Wang et al. and gives gate-complexity estimates under different assumptions on simulating the continuous-time quantum walk.

Significance. For connected Laplacian integral graphs, the construction is elegant and conceptually clean: the exactness of QPE on an integer spectrum is used directly to turn the Laplacian evolution into a Grover diffusion operator, without fitting parameters to numerical data. This genuinely unifies and extends earlier deterministic search results to a large class of graphs, including non-vertex-transitive ones and multiple marked vertices, and the reduction to Long's deterministic Grover iteration is mathematically sound. The examples in Table I and Appendix A are useful concrete illustrations. However, the scope of the central claim as stated in the abstract and Theorem 1 is broader than what the proof supports, and there are several internal inconsistencies in the complexity accounting that need correction before the paper can be accepted.

major comments (3)
  1. [Abstract and Theorem 1; Section III B] The statement 'any Laplacian integral graph' is not supported by the proof. The proof in Section III B assumes the spectrum is 0 = λ1 < λ2 ≤ ... and that |ψ0⟩ = |π⟩, which is exactly the connectedness assumption that the zero eigenspace of L is one-dimensional. For a disconnected Laplacian integral graph, the zero eigenspace has dimension equal to the number of connected components, so the phase-estimation circuit of Fig. 5 applies the phase e^{iβ} to every zero eigenvector, implementing e^{iβ P0} rather than e^{iβ|π⟩⟨π|}. Lemma 1 then no longer applies. A concrete counterexample is G = K1 ∪ K1, for which L = 0, every state is a zero eigenvector, and the algorithm's effective diffusion is a global phase, leaving the success probability at 1/2. The theorem and abstract should be qualified to connected Laplacian integral graphs (or the proof extended to handle the degenerate zero eigenspace), and the standing assumption in Section II should be repeated in the theorem statement.
  2. [Section III B, Eq. (15); Section III C; Theorem 3] The count of calls to the controlled continuous-time quantum walk is inconsistent. The text states that 'the controlled CTQW c-e^{iLt} is called for 2^s = 2^{⌈log(λN + 1)⌉} < 2⌈log(N + 1)⌉ times', but with s = ⌈log(λN + 1)⌉ the quantity 2^s can be Θ(N), not O(log N), and the displayed inequality is false already for N = 8 (where 2^s = 16 > 8). If the intended count is 2s calls (s for the controlled-U^{2^j} operations in the forward QPE and s for their inverses in the uncomputation), then Eq. (15) should read O(log(N)/√ε) calls, and the total evolution-time calculation T < 4π is consistent. As written, the call count in Eq. (15) and the gate-complexity conclusions in Section III C and Theorem 3 rest on an erroneous intermediate statement and need to be corrected.
  3. [Algorithm 1, Step 2(a); Section III B] The description of how the phase gate e^{iβ|π⟩⟨π|} is implemented is internally inconsistent. Algorithm 1 says to perform 'a CIQW (Fig. 3) with m = 2 intermittent steps and s = ⌈log(λN)⌉ ancillary qubits', but the actual circuit in Fig. 5 is a QPE circuit with s controlled evolutions e^{i 2^j t0 L} for j = 0, ..., s−1 and their inverses; this is not a CIQW with m = 2 intermittent steps. Moreover, s must satisfy 2^s > λN, which for integer λN is s = ⌈log(λN + 1)⌉, not ⌈log(λN)⌉; for example, λN = 4 requires s = 3, whereas ⌈log 4⌉ = 2. The pseudo-code should be rewritten to describe the QPE-based construction accurately, since a reader implementing Algorithm 1 from the pseudo-code alone would build the wrong circuit.
minor comments (4)
  1. [Fig. 5 caption] The caption states t0 = π/2^{s+1}, but Eq. (10) in Section III B defines t0 = π/2^{s−1}; the latter is the value needed for the QPE eigenphases to be 2π λ_k / 2^s, so the caption should be corrected.
  2. [Algorithm 1] The symbol k is used both for the number of iterations of the outer loop and for the iteration-count parameter in Lemma 1, leading to statements such as 'Repeat ... for k = O(1/√ϵ) times, with parameters α, β, k set by Lemma 1.' Renaming one of these, for example using K for the loop count, would remove the ambiguity.
  3. [Section I A] There is a typo in 'alternating quantum walks model [32] can be seen as a mixtuire' — 'mixtuire' should be 'mixture'.
  4. [Introduction, paragraph after Theorem 1] The phrase '2dL = O(N)' appears to be missing superscript formatting; it should read '2^{d_L} = O(N)', consistent with the complexity expression O(2^{d_L}√N) in the comparison with Wang et al.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central QPE construction is self-contained, and the self-citations are not load-bearing.

full rationale

The paper's central derivation is the implementation of the phase shift e^{iβ|π><π|} using quantum phase estimation on the Laplacian evolution e^{itL}. This is a self-contained construction: Section III B shows that, for a connected Laplacian integral graph, the integer spectrum lets QPE recover the eigenvalues exactly, and applying a controlled phase only to the zero-eigenvalue register yields exactly e^{iβ|π><π|}. The parameters α and β are set by the external deterministic Grover lemma (Lemma 1, from Long [35]) using the known proportion ε, and are not fitted to any data or renamed predictions. The paper cites its own prior work — [42] for the CIQW model, [36] for deterministic search, and [7] for comparison — but none of these citations carries the proof of Theorem 1; the CIQW definition is restated in Section II B, and the deterministic search uses Long's external lemma. The proof does not assume its own conclusion. The main caveat is a domain-statement issue rather than circularity: Section II restricts to connected graphs and the proof in Section III B assumes the zero eigenspace is one-dimensional, while the abstract and Theorem 1 state 'any Laplacian integral graph' without repeating the connectedness condition; for disconnected graphs the construction implements e^{iβP_0} rather than e^{iβ|π><π|}. This is a correctness/scope gap, not a circularity, because it does not involve the derivation reducing to its inputs. Overall, no circular step is present.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fit to data; α and β are computed from the known proportion ε via Lemma 1, and the QPE register size s follows from the Laplacian eigenvalue bound. The proof rests on the integer-spectrum and connectedness assumptions, plus exact CTQW and QPE as primitives.

assumptions (5)
  • domain assumption The graph Laplacian L has only integer eigenvalues (Laplacian integral graph).
    Defines the graph class of Theorem 1; ensures s-qubit QPE resolves eigenvalues exactly (Section III B).
  • domain assumption The graph is connected, so 0 is a simple eigenvalue of L with eigenvector |π⟩.
    Used in Section III B to apply a phase only to the zero-eigenvalue register; without this, the construction fails.
  • domain assumption Controlled CTQW e^{iLt} is an exact primitive whose cost is the evolution time.
    The algorithm and proof treat c-e^{iLt} as exact (Section II B, Fig. 5); Hamiltonian simulation errors are only analyzed for gate complexity (Section III C).
  • standard math Quantum phase estimation on integer eigenvalues is exact.
    Invoked in Section III B via Kitaev QPE [46].
  • standard math Long's deterministic Grover lemma (Lemma 1) holds.
    External result [35] used to obtain certainty from exact diffusion and oracle.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Deterministic quantum search on all Laplacian integral graphs." pith.science (2026). https://pith.science/paper/T3MLXGEK

@misc{pith2026250621108,
  author       = {Pith},
  title        = {Pith review of: Deterministic quantum search on all Laplacian integral graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T3MLXGEK}},
  note         = {Machine review of arXiv:2506.21108}
}
abstract

Searching for an unknown marked vertex on a given graph (also known as spatial search) is an extensively discussed topic in the area of quantum algorithms, with a plethora of results based on different quantum walk models and targeting various types of graphs. Most of these algorithms have a non-zero probability of failure. In recent years, there have been some efforts to design quantum spatial search algorithms with $100\%$ success probability. However, these works either only work for very special graphs or only for the case where there is only one marked vertex. In this work, we propose a different and elegant approach to quantum spatial search, obtaining deterministic quantum search algorithms that can find a marked vertex with certainty on any Laplacian integral graph with any predetermined proportion of marked vertices. Thus, this work discovers the largest class of graphs so far that allow deterministic quantum search, making it easy to design deterministic quantum search algorithms for many graphs, including the different graphs discussed in previous works, in a unified framework.

Figures

Figures reproduced from arXiv: 2506.21108 by the authors.

Figure 1
Figure 1. FIG. 1. Iterative construction of the first few antiregular connected graphs. The number beside each vertex denotes its degree. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2. Quantum circuit implementation of the general [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3. Illustration of a CIQW [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: FIG. 4. Illustration of our CIQW-based algorithm. [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]
Figure 5
Figure 5. Figure 5: FIG. 5. Quantum circuit implementation of [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

77 extracted references · 69 canonical work pages

  1. [1]

    Thus, the complexity can be greater than O( √ N ) and therefore not optimal in certain cases

    The algorithm’s complexity is O(2dL √ N ) (see The- orem 2) and it is related to the depth dL of the graph Laplacian (see Definition 1), which may de- pend on N , as we will see later on some graphs. Thus, the complexity can be greater than O( √ N ) and therefore not optimal in certain cases

    work page

  2. [2]

    Only one marked vertex is allowed on the graph, and the algorithm fails when dealing with multiple marked vertices

    work page

  3. [3]

    We will later present an interesting type of Laplacian in- tegral graphs that are not vertex-transitive and 2dL = O(N )

    The graph has to be vertex-transitive, which lim- its the applicability of the algorithm. We will later present an interesting type of Laplacian in- tegral graphs that are not vertex-transitive and 2dL = O(N ). In this paper, we overcome all the above limitations by proposing a quantum search algorithm that can find a marked vertex with certainty on any L...

    work page

  4. [4]

    Prepare the uniform superposition of all vertices |π⟩ = 1√ N P v∈V |v⟩

    work page

  5. [5]

    (a) Perform a CIQW (Fig

    Repeat the following two steps for k = O(1/√ϵ) times, with parameters α, β, kset by Lemma 1. (a) Perform a CIQW (Fig. 3) with m = 2 intermittent steps and s = ⌈log(λN )⌉ ancillary qubits to implement exactly the relative phase shift eiβ|π⟩⟨π| as shown in Fig. 5. (b) Invoke the oracle eiαΠM shown in Fig. 2

    work page

  6. [6]

    We first show that the quantum circuit shown in Fig

    Measure the walking space. We first show that the quantum circuit shown in Fig. 5 implements exactly the relative phase shift of the state |π⟩, i.e. eiβ|π⟩⟨π| = I − (1 − eiβ) |π⟩ ⟨π| , (9) by applying quantum phase estimation (QPE) [46] to eiLt. Suppose the eigenvalues of the graph Laplacian L are 0 = λ1 < λ2 ≤ · · · ≤λN ≤ N , with corresponding eigenvect...

    work page

  7. [7]

    This graph has n vertices, and each vertex is connected to the other n − 1 vertices

    Complete graph Kn. This graph has n vertices, and each vertex is connected to the other n − 1 vertices. The Laplacian eigenvalues are 0 and n with corresponding multiplicities 1 and ( n − 1)

    work page

  8. [8]

    The vertex set consists of all subset S of [ n] := {1, 2,

    Johnson graph J(n, k) [58]. The vertex set consists of all subset S of [ n] := {1, 2, . . . , n} with size k, and two vertices S, S′ are adjacent if and only if |S ∩ S′| = k − 1. The Laplacian eigenvalues are i(n + 1 − i) for i ∈ {0, 1, . . . ,min(k, n− k)}, with corresponding multiplicities n i − n i−1 . We define n −1 = 0

    work page

Show all 77 references
  1. [9]

    The vertex set con- sists of all subset S of [n] := {1, 2,

    Kneser graph K(n, k) [58]. The vertex set con- sists of all subset S of [n] := {1, 2, . . . , n} with size k < n/2, and two vertices S, S′ are adjacent if and only if S ∩ S′ = ∅. The Laplacian eigenvalues aren−k k −(−1)in−k−i k−i for i ∈ {0, 1, . . . , k}, with cor- responding...

  2. [10]

    The vertex set con- sists of all d-tuples (x1,

    Hamming graph H(d, q) [58]. The vertex set con- sists of all d-tuples (x1, . . . , xd) ∈ [q]d, and two ver- tices x, x′ are adjacent if and only if they differ in exactly one coordinate. The Laplacian eigenvalues are qi for i ∈ {0, 1, . . . , d}, with corresponding mul- tiplic...

  3. [11]

    Grassmann graph Gq(n, k) [59]. The vertex set con- sists of all k-dimensional subspaces of Fn q , the n- dimensional space over the finite field Fq, and two vertices A, Bare adjacent if and only if dim( A ∩ B) = k − 1. There are n k q := (qn−1)···(qn−m+1−1) (qm−1)···(q−1) vert...

  4. [12]

    It is the Cartesian prod- uct Km□Kn of the m-vertex complete graph Km and the n-vertex complete graph Kn

    Rook graph R(m, n) [32]. It is the Cartesian prod- uct Km□Kn of the m-vertex complete graph Km and the n-vertex complete graph Kn. Specifically, there are mn vertices in total: V = {(u, v) : u ∈ V (Km), v∈ V (Kn)}, and two vertices ( u, v) and (u′, v′) are adjacent if and only...

  5. [13]

    It is the Cartesian product of an n-vertex complete graph Kn with a square graph Q2

    Complete-square graph Kn□Q2 [32]. It is the Cartesian product of an n-vertex complete graph Kn with a square graph Q2. All the vertices have the same degree ( n + 1). The Laplacian eigenval- ues are 0, 2, 4, n,(n + 2), (n + 4) with corresponding multiplicities 1, 2, 1, (n − 1)...

  6. [14]

    The vertex set is V = {(u, b) : u ∈ [n], b= 0, 1}, and each vertex (u, b) is connected to all the other (2 n − 2) ver- tices except the vertex ( u, 1 − b)

    Cocktail-party graph CP (n) [54]. The vertex set is V = {(u, b) : u ∈ [n], b= 0, 1}, and each vertex (u, b) is connected to all the other (2 n − 2) ver- tices except the vertex ( u, 1 − b). The Laplacian eigenvalues are 0 , (2n − 2), 2n with corresponding multiplicities 1, n,(n − 1)

  7. [15]

    The n vertices are equally divided into k classes, and each vertex v is connected to the other ( n − n/k) vertices that are not in the same class as v

    Complete k-partite graph Kn/k,n/k,...,n/k [54]. The n vertices are equally divided into k classes, and each vertex v is connected to the other ( n − n/k) vertices that are not in the same class as v. The Laplacian eigenvalues are 0 , (n − n/k), nwith cor- responding multiplici...

  8. [16]

    It is a tree with one node having degree n and the other n vertices having degree 1

    Star graph K1,n [54]. It is a tree with one node having degree n and the other n vertices having degree 1. The Laplacian eigenvalues are 0, 1, (n+1) with corresponding multiplicities 1 , (n − 1), 1. Appendix B: Hamiltonian Simulation Product formulas method [60] for the proble...

  9. [17]

    Ambainis, J

    A. Ambainis, J. Kempe, and A. Rivosh, Coins make quantum walks faster, in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’05 (Society for Industrial and Applied Mathe- matics, USA, 2005) p. 1099–1108

    2005

  10. [18]

    A. M. Childs and J. Goldstone, Spatial search by quan- tum walk, Phys. Rev. A 70, 022314 (2004)

    2004

  11. [19]

    Ambainis, A

    A. Ambainis, A. Gily´ en, S. Jeffery, and M. Kokainis, Quadratic speedup for finding marked vertices by quan- tum walks, in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 (Association for Computing Machinery, New York, NY, USA, 2020) p. 412–424

    2020

  12. [20]

    Apers, S

    S. Apers, S. Chakraborty, L. Novo, and J. Roland, Quadratic speedup for spatial search by continuous-time quantum walk, Phys. Rev. Lett. 129, 160502 (2022)

    2022

  13. [21]

    Apers, A

    S. Apers, A. Gily´ en, and S. Jeffery, A Unified Frame- work of Quantum Walk Search, in 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), Leibniz International Proceedings in In- formatics (LIPIcs), Vol. 187, edited by M. Bl¨ aser and B. Mon...

    2021

  14. [22]

    Y. Xu, D. Zhang, and L. Li, Robust quantum walk search without knowing the number of marked vertices, Phys. Rev. A 106, 052207 (2022)

    2022

  15. [23]

    Q. Wang, Y. Jiang, S. Feng, and L. Li, Unifying quantum spatial search, state transfer, and uniform sampling on graphs, Phys. Rev. A 111, 042608 (2025)

    2025

  16. [24]

    Ambainis, Quantum walk algorithm for element dis- tinctness, in 45th Annual IEEE Symposium on Founda- tions of Computer Science(2004) pp

    A. Ambainis, Quantum walk algorithm for element dis- tinctness, in 45th Annual IEEE Symposium on Founda- tions of Computer Science(2004) pp. 22–31

    2004

  17. [25]

    Buhrman and R

    H. Buhrman and R. ˇSpalek, Quantum verification of ma- trix products, in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA ’06 (Society for Industrial and Applied Mathematics, USA, 2006) p. 880–889

    2006

  18. [26]

    Magniez, M

    F. Magniez, M. Santha, and M. Szegedy, Quantum algo- rithms for the triangle problem, SIAM J. Comput. 37, 413 (2007)

    2007

  19. [27]

    Magniez and A

    F. Magniez and A. Nayak, Quantum complexity of test- ing group commutativity, Algorithmica 48, 221 (2007)

    2007

  20. [28]

    A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential algorithmic speedup by a quantum walk, in Proceedings of the Thirty-Fifth An- nual ACM Symposium on Theory of Computing, STOC ’03 (Association for Computing Machinery, New York, NY, USA, 2...

    2003

  21. [29]

    A. M. Childs, L. J. Schulman, and U. V. Vazirani, Quan- tum algorithms for hidden nonlinear structures, in 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07) (2007) pp. 395–404

    2007

  22. [30]

    Ambainis, E

    A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous, One-dimensional quantum walks, inProceed- ings of the 33rd ACM Symposium on Theory of Comput- ing (2001) pp. 37–49

    2001

  23. [31]

    Aharonov, A

    D. Aharonov, A. Ambainis, J. Kempe, and U. V. Vazi- rani, Quantum walks on graphs, in Proceedings of the 33rd ACM Symposium on Theory of Computing(2001) pp. 50–59

    2001

  24. [32]

    Szegedy, Quantum speed-up of markov chain based algorithms, in 45th Annual IEEE Symposium on Foun- dations of Computer Science(2004) pp

    M. Szegedy, Quantum speed-up of markov chain based algorithms, in 45th Annual IEEE Symposium on Foun- dations of Computer Science(2004) pp. 32–41

    2004

  25. [33]

    Magniez, A

    F. Magniez, A. Nayak, J. Roland, and M. Santha, Search via quantum walk, SIAM Journal on Computing 40, 142 (2011)

    2011

  26. [34]

    Belovs, Quantum walks and electric networks (2013), arXiv:1302.3143 [quant-ph]

    A. Belovs, Quantum walks and electric networks (2013), arXiv:1302.3143 [quant-ph]

    2013 arXiv

  27. [35]

    Krovi, F

    H. Krovi, F. Magniez, M. Ozols, and J. Roland, Quantum walks can find a marked element on any graph, Algorith- mica 74, 851 (2016)

    2016

  28. [36]

    Hein and G

    B. Hein and G. Tanner, Quantum search algorithms on the hypercube, Journal of Physics A: Mathematical and Theoretical 42, 085303 (2009)

    2009

  29. [37]

    Janmark, D

    J. Janmark, D. A. Meyer, and T. G. Wong, Global sym- metry is unnecessary for fast quantum search, Phys. Rev. Lett. 112, 210502 (2014)

    2014

  30. [38]

    M. L. Rhodes and T. G. Wong, Quantum walk search on the complete bipartite graph, Phys. Rev. A 99, 032301 (2019)

    2019

  31. [39]

    Philipp, L

    P. Philipp, L. Tarrataca, and S. Boettcher, Continuous- time quantum search on balanced trees, Phys. Rev. A93, 032305 (2016)

    2016

  32. [40]

    Tanaka, M

    H. Tanaka, M. Sabri, and R. Portugal, Spatial search on johnson graphs by continuous-time quantum walk, Quan- tum Information Processing 21, 74 (2022)

    2022

  33. [41]

    Tanaka, M

    H. Tanaka, M. Sabri, and R. Portugal, Spatial search on johnson graphs by discrete-time quantum walk, Journal of Physics A: Mathematical and Theoretical 55, 255304 (2022)

    2022

  34. [42]

    A. Chan, C. D. Godsil, C. Tamon, and W. Xie, Of shad- ows and gaps in spatial search, Quantum Inf. Comput. 22, 1110 (2022)

    2022

  35. [43]

    Chakraborty, L

    S. Chakraborty, L. Novo, A. Ambainis, and Y. Omar, 9 Spatial search by quantum walk is optimal for almost all graphs, Phys. Rev. Lett. 116, 100501 (2016)

    2016

  36. [44]

    Lin and Y

    H. Lin and Y. Shang, Deterministic Search on Complete Bipartite Graphs by Continuous Time Quantum Walk (2024), arXiv:2404.01640v2, 2404.01640

    2024 arXiv

  37. [45]

    F. Peng, M. Li, and X. Sun, Deterministic discrete-time quantum walk search on complete bipartite graphs, Phys. Rev. Res. 6, 033042 (2024)

    2024

  38. [46]

    Marsh and J

    S. Marsh and J. B. Wang, Deterministic spatial search us- ing alternating quantum walks, Phys. Rev. A104, 022216 (2021)

    2021

  39. [47]

    D. Qu, S. Marsh, K. Wang, L. Xiao, J. Wang, and P. Xue, Deterministic search on star graphs via quantum walks, Phys. Rev. Lett. 128, 050501 (2022)

    2022

  40. [48]

    Marsh and J

    S. Marsh and J. B. Wang, A framework for optimal quan- tum spatial search using alternating phase-walks, Quan- tum Science and Technology 6, 045029 (2021)

    2021

  41. [49]

    Brassard, P

    G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, Contemporary Mathematics 305, 53 (2002)

    2002

  42. [50]

    Hoyer, On arbitrary phases in quantum amplitude am- plification, Physical Review A 62 (2000)

    P. Hoyer, On arbitrary phases in quantum amplitude am- plification, Physical Review A 62 (2000)

    2000

  43. [51]

    G. L. Long, Grover algorithm with zero theoretical failure rate, Phys. Rev. A 64, 022307 (2001)

    2001

  44. [52]

    Li and L

    G. Li and L. Li, Deterministic quantum search with ad- justable parameters: Implementations and applications, Information and Computation 292, 105042 (2023)

    2023

  45. [53]

    Brassard and P

    G. Brassard and P. Hoyer, An exact quantum polynomial-time algorithm for simon’s problem, in Pro- ceedings of the Fifth Israeli Symposium on Theory of Computing and Systems(1997) pp. 12–23

    1997

  46. [54]

    Z. Ye, Y. Huang, L. Li, and Y. Wang, Query complexity of generalized simon’s problem, Information and Compu- tation 281, 104790 (2021)

    2021

  47. [55]

    Li and L

    G. Li and L. Li, Optimal deterministic quantum algo- rithm for the promised element distinctness problem, Theoretical Computer Science 999, 114551 (2024)

    2024

  48. [56]

    Li and L

    G. Li and L. Li, Derandomization of quantum algorithm for triangle finding, Information and Computation 304, 105295 (2025)

    2025

  49. [57]

    G. Li, L. Li, and J. Luo, Recovering the original sim- plicity: succinct and deterministic quantum algorithm for the welded tree problem, in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2454–2480

    2024

  50. [58]

    G. Li, L. Li, and J. Luo, Quantum phase discrimination with applications to quantum search on graphs (2025), arXiv:2504.15194, 2504.15194

    2025 arXiv

  51. [59]

    Ali, A survey of antiregular graphs, Contrib

    A. Ali, A survey of antiregular graphs, Contrib. Math 1, 67 (2020)

    2020

  52. [60]

    S. M. Fallat, S. J. Kirkland, J. J. Molitierno, and M. Neu- mann, On graphs whose laplacian matrices have distinct integer eigenvalues, Journal of Graph Theory 50, 162 (2005)

    2005

  53. [61]

    Grone, R

    R. Grone, R. Merris, and V. S. Sunder, The Laplacian Spectrum of a Graph, SIAM Journal on Matrix Analysis and Applications 11, 218 (1990)

    1990

  54. [62]

    A. Y. Kitaev, Quantum measurements and the abelian stabilizer problem (1995), arXiv:quant-ph/9511026 [quant-ph]

    1995 arXiv

  55. [63]

    M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition (Cambridge University Press, 2010)

    2010

  56. [64]

    Loke and J

    T. Loke and J. B. Wang, Efficient quantum circuits for continuous-time quantum walks on composite graphs, Journal of Physics A: Mathematical and Theoretical 50, 055303 (2017)

    2017

  57. [65]

    Xu, Exact analytical results for quantum walks on star graphs, Journal of Physics A: Mathematical and Theoretical 42, 115205 (2009)

    X.-P. Xu, Exact analytical results for quantum walks on star graphs, Journal of Physics A: Mathematical and Theoretical 42, 115205 (2009)

    2009

  58. [66]

    A. M. Childs, On the relationship between continuous- and discrete-time quantum walk, Communications in Mathematical Physics 294, 581 (2010)

    2010

  59. [67]

    Qiang, T

    X. Qiang, T. Loke, A. Montanaro, K. Aungskunsiri, X. Zhou, J. L. O’Brien, J. B. Wang, and J. C. Matthews, Efficient quantum walk on a quantum processor, Nature communications 7, 11511 (2016)

    2016

  60. [68]

    Z. Chen, G. Li, and L. Li, Implementation of a continuous-time quantum walk on a sparse graph, Phys. Rev. A 110, 052215 (2024)

    2024

  61. [69]

    Merris, Degree maximal graphs are laplacian integral, Linear Algebra and its Applications 199, 381 (1994), spe- cial Issue Honoring Ingram Olkin

    R. Merris, Degree maximal graphs are laplacian integral, Linear Algebra and its Applications 199, 381 (1994), spe- cial Issue Honoring Ingram Olkin

    1994

  62. [70]

    Bali´ nska, D

    K. Bali´ nska, D. Cvetkovi´ c, Z. Radosavljevi´ c, S. Simi´ c, and D. Stevanovi´ c, A survey on integral graphs, Pub- likacije Elektrotehniˇ ckog fakulteta. Serija Matematika , 42 (2002)

    2002

  63. [71]

    L. S. de Lima, N. M. Maia de Abreu, C. S. Oliveira, and M. A. Alvarez de Freitas, Laplacian integral graphs in s(a,b), Linear Algebra and its Applications 423, 136 (2007), special Issue devoted to papers presented at the Aveiro Workshop on Graph Spectra

    2007

  64. [72]

    Grone and R

    R. Grone and R. Merris, Indecomposable laplacian in- tegral graphs, Linear Algebra and its Applications 428, 1565 (2008)

    2008

  65. [73]

    R. R. Del-Vecchio and A. A. Jones, Laplacian integrality in p4-sparse and p4-extendible graphs, Applied Mathe- matics and Computation 330, 307 (2018)

    2018

  66. [74]

    A. E. Brouwer and W. H. Haemers, Distance-regular graphs, in Spectra of Graphs(Springer New York, New York, NY, 2012) pp. 177–185

    2012

  67. [75]

    A. E. Brouwer, A. M. Cohen, and A. Neumaier, The families of graphs with classical parameters, in Distance- Regular Graphs(Springer Berlin Heidelberg, Berlin, Hei- delberg, 1989) pp. 255–293

    1989

  68. [76]

    Lloyd, Universal quantum simulators, Science 273, 1073 (1996)

    S. Lloyd, Universal quantum simulators, Science 273, 1073 (1996)

    1996

  69. [77]

    D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, Ef- ficient quantum algorithms for simulating sparse hamil- tonians, Communications in Mathematical Physics 270, 359 (2007)

    2007

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.