RECORD
Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem
Quantum Physics · Submitted 30 Apr 2024
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim In this paper, we give a very short proof of the optimal linear hitting time for this problem by a discrete-time quantum walk, which is based on a simple modification of the electric quantum walk framework.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Up to now, relatively few exponential quantum speed-ups have been achieved. Out of them, the welded tree problem (Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman'2003) is one of the unusual examples, as the exponential speed-up is attained by a quantum walk. In this paper, we give a very short proof of the optimal linear hitting time for this problem by a discrete-time quantum walk, which is based on a simple modification of the electric quantum walk framework. The same technique can be applied to other 1-dimensional hierarchical graphs, yielding results similar to (Balasubramanian, Li, and Harrow'2023).
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Up to now, relatively few exponential quantum speed-ups have been achieved. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | Out of them, the welded tree problem (Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman'2003) is one of the unusual examples, as the exponential speed-up is attained by a quantum walk. | background 1.00 | 0.04 | 0.05 | asserted 1.00 |
| s2 | In this paper, we give a very short proof of the optimal linear hitting time for this problem by a discrete-time quantum walk, which is based on a simple modification of the electric quantum walk framework. | contribution 0.93 | 0.96 | 0.74 | asserted 1.00 |
| s3 | The same technique can be applied to other 1-dimensional hierarchical graphs, yielding results similar to (Balasubramanian, Li, and Harrow'2023). | contribution 0.53 | 0.78 | 0.09 | asserted 0.94 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Up to now, relatively few exponential quantum speed-ups have been achieved. Out of them, the welded tree problem (Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman'2003) is one of the unusual examples, as the exponential speed-up is attained by a quantum walk. In this paper, we give a very short proof of the optimal linear hitting time for this problem by a discrete-time quantum walk, which is based on a simple modification of the electric quantum walk framework. The same technique can be applied to other 1-dimensional hierarchical graphs, yielding results similar to (Balasubramanian, Li, and Harrow'2023).
Human review
References
How the literature uses it
2 arXiv papers cite this in 2 sentences
What it cites · 24 sentences without a confident label
Builds on 3 papers
-
In this section, we give a simple extension of the electric quantum walk from [ref] that finds a marked vertex provided it is unique.
Quantum Walks and Electric Networks · Simple Search Using Electric Quantum Walks · 0.99
-
Balasubramanian, Li, and Harrow [ref] generalised the continuous-time quantum walk of [ref] to other types of hierarchical graphs.
2307.15062 · Introduction · 0.90
-
Balasubramanian, Li, and Harrow [ref] generalised the continuous-time quantum walk of [ref] to other types of hierarchical graphs.
Exponential algorithmic speedup by quantum walk · Introduction · 0.90
Uses the method or tool of 2 papers
-
We make use of a novel approach to quantum walks using transducers [ref] .
Taming Quantum Time Complexity · Introduction · 1.00
-
[ The edge $ss'$ is adopted from [ref] .
Quantum Walks and Electric Networks · Electric quantum walks · 0.96
Compares with 4 papers
-
Unlike Jeffery and Zur [ref] , and similarly to Li, Li, and Luo [ref] , we use the conventional version of discrete-time quantum walk on this graph.
Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem · Introduction · 1.00
-
Unlike Jeffery and Zur [ref] , and similarly to Li, Li, and Luo [ref] , we use the conventional version of discrete-time quantum walk on this graph.
Multidimensional Quantum Walks, with Application to $k$-Distinctness · Introduction · 1.00
-
The main result of this section is the following theorem, which is comparable to a similar result in [ref] .
2307.15062 · Hierarchical 1-Dimensional Graphs · 1.00
Cites as background 4 papers
-
In early 2000s, this observation was used by Kempe [ref] and Childs, Farhi, and Gutmann [ref] to construct quantum walks exponentially outperforming their random counterparts.
An example of the difference between quantum and classical random walks · Introduction · 0.97
-
In early 2000s, this observation was used by Kempe [ref] and Childs, Farhi, and Gutmann [ref] to construct quantum walks exponentially outperforming their random counterparts.
Quantum Random Walks Hit Exponentially Faster · Introduction · 0.97
-
This case was later resolved by Krovi, Magniez, Ozols, and Roland [ref] using so-called interpolating quantum walk.
Quantum walks can find a marked element on any graph · Introduction · 0.83
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.