Lune

SODA2024Top-tier venue

Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem

Guanzhong Li, Lvzhou Li, Jingquan Luo

Abstract

This work revisits quantum algorithms for the well-known welded tree problem, proposing a very succinct quantum algorithm based on the simplest coined quantum walks. It simply iterates the naturally defined coined quantum walk operator for a predetermined time and finally measure, where the predetermined time can be efficiently computed on classical computers. Then, the algorithm returns the correct answer deterministically, and achieves exponential speedups over any classical algorithm. The significance of the results may be seen as follows. (i) Our algorithm is rather simple compared with the one in (Jeffery and Zur, STOC’2023), which not only breaks the stereotype that coined quantum walks can only achieve quadratic speedups over classical algorithms, but also demonstrates the power of the simplest quantum walk model. (ii) Our algorithm theoretically achieves certainty of success, which is not possible with existing methods. Thus, it becomes one of the few examples that exhibit exponential separation between deterministic (exact) quantum and randomized query complexities, which may also change people's perception that since quantum mechanics is inherently probabilistic, it impossible to have a deterministic quantum algorithm with exponential speedups for the welded tree problem.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on2

  1. Symmetries, Graph Properties, and Quantum SpeedupsShalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer et al.FOCS 2020 · 15 citations
  2. Multidimensional Quantum WalksStacey Jeffery, Sebastian ZurSTOC 2023 · 8 citations

Related papers

  1. Quadratic speedup for finding marked vertices by quantum walksAndris Ambainis, András Gilyén, Stacey Jeffery, Martins KokainisSTOC 2020 · 4 citations
  2. Design of a Quantum Walk Circuit to Solve the Subset-Sum ProblemGiacomo Lancellotti, Simone Perriello, Alessandro Barenghi, Gerardo PelosiDAC 2024 · 4 citations
  3. (Sub)Exponential advantage of adiabatic Quantum computation with no sign problemAndrás Gilyén, Matthew B. Hastings, Umesh V. VaziraniSTOC 2021 · 3 citations
  4. Computations with greater quantum depth are strictly more powerful (relative to an oracle)Matthew Coudron, Sanketh MendaSTOC 2020 · 25 citations
  5. Finding Many Collisions via Reusable Quantum Walks - Application to Lattice SievingXavier Bonnetain, André Chailloux, André Schrottenloher, Yixin ShenEUROCRYPT 2023 · 22 citations
Dusk over the sea between two cliffs drawn in fine vertical lines