betaFeedback

WorksPhysics and Astronomy

Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard

Abstract

In the welded trees problem, an algorithm navigates a randomly labeled graph formed from two binary trees joined at their leaves through a "weld" of connecting edges. A quantum walk can navigate from root to root exponentially faster than any classical algorithm. However, recording its path destroys the constructive interference responsible for the speedup, leaving open whether some quantum algorithm can efficiently find a path between the roots. We prove that, for trees of height nn, the quantum query complexity of finding a path between the roots with constant probability is Θ~(2n/3)\tildeΘ(2^{n/3}). This establishes an algorithmic wave-particle duality, adapting the double-slit experiment to the high-complexity regime: interference between many paths lets a quantum algorithm reach the exit efficiently, but finding a single path (the algorithmic analog of the route of a particle) requires exponentially many queries. Furthermore, the bound is tight, matching the cost of a quantum algorithm that finds collisions between paths from each root to the weld. Our proof uses the compressed permutation oracle to track the information about the graph that an algorithm retains and forgets. We show that the compressed database remains close to a space of states that do not record a path between the roots by bounding the error introduced by each compressed oracle query.

Introduction

Quantum computers can solve certain problems dramatically faster than classical ones, but the extent of this advantage remains poorly understood. Notable families of algorithms with superpolynomial speedup include those based on finding periodic structures using Fourier transforms [43] and simulating the dynamics of quantum systems [34]. Identifying other mechanisms for quantum speedup, and understanding their limitations, remain central challenges.

The welded trees problem provides an example of a different kind of speedup that is due to interference when coherently exploring a graph. The graph, illustrated in Figure 1, consists of two height-nn balanced binary trees whose leaves are joined by a random cycle alternating between the two trees (the “weld”). Vertices have random labels and an algorithm accesses the graph through an adjacency-list oracle. Given the label of one root, the entrance, a quantum walk finds the other root, the exit, in time polynomial in nn, whereas every classical algorithm requires exponentially many queries [15]. The quantum walk exploits the layered structure of the graph. Its evolution stays in the span of uniform superpositions over successive layers, effectively reducing the problem to traversal of a path of length O(n)O(n). On the other hand, after crossing the weld, a classical traversal has little information about which edges lead towards the exit. Reaching a previously visited node along an unexplored edge could help identify a way towards the exit, but even this task requires exponentially many queries.

An instance of a welded trees graph

Figure 1. An instance of a welded trees graph. The blue node is the entrance, the green node is the exit and the red nodes are the leaves. The edges between the leaves are the weld edges.

Beyond providing a new mechanism for quantum speedup, the welded trees problem has yielded insight into a variety of other questions pertaining to the power of quantum computation. It was used to show that some quantum speedups cannot be achieved with only logarithmic quantum depth [20], and was a building block for results on the power of adiabatic computation and optimization [25, 37], the quantum query complexity of graph property testing [7], and exponential separations for machine learning tasks [26]. Understanding what quantum algorithms can and cannot do on these graphs therefore informs a broader set of questions about quantum advantage.

The problem also suggests a striking distinction between reaching a destination and finding a route to it. A classical traversal can record its route at little additional cost, so in particular, exit finding and pathfinding have the same classical query complexity, which is Θ~(2n/2)\widetilde{\Theta}(2^{n/2}) [23, 6 AA18]. On the other hand, the quantum walk traverses many paths in superposition without outputting any one of them. Retaining distinguishable records of these paths suppresses the interference responsible for the speedup, similarly to how recording which slit a particle passes through destroys interference in the double-slit experiment. This explains why simply recording the quantum walk eliminates the speedup, but leaves open whether a different quantum algorithm could find a path efficiently. This has been a longstanding open problem, alluded to in the original paper [15] and highlighted in a list of open problems in quantum query complexity [2].

Prior work ruled out efficient pathfinding algorithms that are both rooted and genuine [CCGZ23]. Informally, a genuine algorithm is restricted to only query the oracle at (superpositions of) known vertex labels, and a rooted algorithm always retains a path from the entrance to every vertex it records. These conditions capture natural approaches, including versions of the quantum snake walk [41], whose state describes a polynomially long path in the graph. However, general algorithms need not satisfy either condition. We combine and strengthen our independent preliminary works [40, 14] in order to obtain a quantum query lower bound for pathfinding on the welded trees graph that is tight up to logarithmic factors.

Theorem 1.1 (Informal version of Theorem 4.1). For any quantum algorithm A\mathcal{A} making q≥1q \ge1 queries to a welded trees graph oracle,

Pr⁡[A outputs an entrance-exit path]=O(q2n/3+n⋅q32n),\Pr[\mathcal{A}\text{ outputs an entrance-exit path}] = O\left(\frac{q}{2^{n/3}}+\frac{n\cdot q^{3}}{2^{n}}\right),

with the oracle sampled from a distribution over welded trees graphs with a single cycle.

Hence in order to achieve constant success probability, an algorithm must make Ω~(2n/3)\widetilde{\Omega}(2^{n/3}) queries. This lower bound is nearly tight since an algorithm can find a path in O(n⋅2n/3)O(n\cdot2^{n/3}) queries, as follows. First, run the quantum walk algorithm to find the exit. Then observe that a nonbacktracking walk of length nn from the entrance finds a leaf on the left side of the weld, and a nonbacktracking walk of length nn from the exit finds a leaf on the right side of the weld. Furthermore, we can determine with two queries whether a given left leaf is connected to a given right leaf. Using the collision algorithm of [10], with each root-to-leaf evaluation costing O(n)O(n) queries, we can then find a pair of connected leaves in O(n⋅2n/3)O(n\cdot2^{n/3}) queries. Therefore, in both classical and quantum settings, pathfinding reduces to collision finding. Furthermore, the pathfinding algorithm produces a shortest entrance-exit path by joining two root-to-leaf paths across a single weld edge. While in principle it might be easier to find a non-shortest path, our lower bound shows that finding any entrance-exit path is just as difficult as finding a shortest one up to factors polynomial in nn.

Our proof uses the compressed permutation oracle of [13, 21], which provides a method for showing quantum lower bounds when querying an oracle that implements a random permutation. Conceptually, we use several compressed permutations as building blocks by implementing the welded trees oracle using separate permutations for the labels of vertices and edges between two adjacent columns. The compressed oracle method provides a way of reversibly recording an algorithm’s queries in a certain database state. Intuitively, this database provides a similar representation of the algorithm’s knowledge of the graph as in the genuine algorithms of [16], but in a way that applies to general algorithms.

Technical overview

Briefly, the structure of the proof is as follows. The key idea is to track the information an algorithm retains about the structure of the graph during computation. In § 3, we construct two compressed versions of the welded trees oracle and relate successful pathfinding to recording a path across the graph. In § 4.1, we define the good space, which is a collection of states that do not record such a path. The key step is showing in § 4.2 and § 4.3 that a single query can move the state only slightly outside the good space. As the computation starts with an empty record, it starts in the good space and hence we find that Ω~(2n/3)\widetilde{\Omega}(2^{n/3}) queries are necessary to find a path with constant probability.

Recording graph information. In order to record what an algorithm knows about the graph, we use the compressed oracle framework of [Zha19]. Introduced as a technique for proving quantum indifferentiability (i.e., showing that some cryptographic construction is essentially as good as an ideal object), it has found a variety of other uses [18, 30, 11, 39, 3, 9, 28, 13]. For an introduction, see [29]. Intuitively, the technique represents the information an algorithm retains about a random oracle using a database of input-output records. Note that the database is itself quantum, with records stored in superposition. These records can also be erased when the algorithm uncomputes queries, reflecting its ability to forget information.

We apply this framework to welded trees using the recent construction of compressed permutation oracles [13, 21]. Specifically, we consider access to the graph via a neighbor oracle O(wt)O^{(\mathrm{wt})} that takes a vertex label ll and color α\alpha as input and returns the label l′l' of the corresponding neighbor, if it exists. By revealing an edge coloring, this oracle gives the algorithm more information than the original adjacency-list oracle (so in particular, a lower bound in the model with colors implies a lower bound for the standard adjacency-list model).1 On the other hand, the coloring gives us a natural way to randomize the graph using permutations. We instantiate this oracle by fixing a welded trees graph along with a proper edge coloring and applying two independent families of permutations. The first, σlabel\sigma_{\mathrm{label}}, assigns random labels to vertices. The second, σedge\sigma_{\mathrm{edge}}, permutes edges within each column and color in a certain region around the weld. To answer the query, the oracle identifies the corresponding vertex via v=σlabel−1(l)v = \sigma_{\mathrm{label}}^{-1}(l), follows its edge of color α\alpha using σedge\sigma_{\mathrm{edge}} to node ww and then returns the label of the neighboring vertex, outputting l′=σlabel(w)l' = \sigma_{\mathrm{label}}(w). This computation is illustrated in Figure 2.

Answer to the query diagram

Figure 2. Answer to the query (l,α)(l,\alpha). The oracle maps the label ll to vertex vv, follows its edge using σedge\sigma_{\mathrm{edge}} to vertex ww and outputs the label l′l' of ww. The algorithm only receives l′l'.

The algorithm never directly receives the vertices vv or ww. The edge permutation σedge\sigma_{\mathrm{edge}} (illustrated in Figure 3) consists of independent permutations, each acting on edges of the same color α\alpha between two adjacent columns cc and c+1c+1, which we call an edge class. Within each such class, we keep the endpoints in one column fixed and permute their partners in the other column. We apply these edge permutations only in a region around the weld extending to approximately n/3n/3 edges away from each root, leaving the edges closer to the roots fixed. As this assignment is a bijection, every vertex retains the same number of edges of each color to each adjacent column. Thus the two binary trees retain their structure and the edge coloring remains proper.

An example of an application of sigma edge on the welded trees graph

Figure 3. An example of an application of σedge\sigma_{\mathrm{edge}} on the welded trees graph.

We define this formally in § 3.1. Replacing σlabel\sigma_{\mathrm{label}} and σedge\sigma_{\mathrm{edge}} with compressed permutation oracles gives us two databases, a label database LL that maps vertices to labels and an edge-color database CC for the edge permutations. In § 3.2, we construct the ordinary compressed welded trees oracle cpWT, which we use to understand what information is tracked. For some fixed input xx, let pC denote an operator that swaps partial injective database states ∣I⟩|I\rangle in which xx is not recorded with the uniform superposition over extensions of II where xx maps to some unused output yy. We can write each step of the computation in O(wt)O(wt) described above using a corresponding pC operator. Specifically, pClabinv_{\mathrm{lab}}^{\mathrm{inv}} associates some vertex v=L−1(l)v=L^{-1}(l) to the label ll, pCedge_{\mathrm{edge}} handles recording an edge from vv to ww in the database CC and pClabfor_{\mathrm{lab}}^{\mathrm{for}} assigns the label L(w)L(w) to the vertex ww. Lastly, we define PP to be the operation that XORs L(w)L(w) into the output register, assuming all of the corresponding database values are in LL and CC, otherwise acting as the identity. Combining these gives

cpWT:=plabinv⋅pedgeinv⋅plabfor⋅P⋅plabfor⋅pedge⋅plabinv.(1)\mathrm{cpWT} := p_{\mathrm{lab}}^{\mathrm{inv}} \cdot p_{\mathrm{edge}}^{\mathrm{inv}} \cdot p_{\mathrm{lab}}^{\mathrm{for}} \cdot P \cdot p_{\mathrm{lab}}^{\mathrm{for}} \cdot p_{\mathrm{edge}} \cdot p_{\mathrm{lab}}^{\mathrm{inv}}. \tag*{(1)}

We also construct the exact compressed welded trees oracle cpWT‾\overline{\mathrm{cpWT}}, which can be viewed as an intermediate step between O(wt)O^{(\mathrm{wt})} and cpWT\mathrm{cpWT}: it uses the same database states as cpWT\mathrm{cpWT}, but exactly preserves the success probability of the original oracle O(wt)O^{(\mathrm{wt})}.

In § 3.3, we compare these oracles. First, we characterize the relationship between cpWT\mathrm{cpWT} and cpWT‾\overline{\mathrm{cpWT}}, which allows us to transfer our bounds between them. Second, we show that the success probability of an algorithm using O(wt)O^{(\mathrm{wt})} is bounded by the probability that a path across the region with permuted edges is recorded in the database CC when using cpWT‾\overline{\mathrm{cpWT}}, with an additive error growing linearly with the number of queries.

Quantum walk speedup. Before turning to the proof of Theorem 1.1, we explain how the databases L,CL,C develop during the quantum walk that finds the exit vertex exponentially faster than any classical algorithm [15]. We analyze this process in more detail in Section A.

The quantum walk algorithm evolves with a Hamiltonian given by the adjacency matrix of the graph. As described above, starting at the entrance, the walk remains in the span of uniform superpositions over columns, so its evolution reduces to a continuous-time quantum walk on a weighted path of length O(n)O(n).

For welded tree instances obtained by sampling σlabel\sigma_{\mathrm{label}} and σedge\sigma_{\mathrm{edge}} uniformly (as described in § 3.1), the evolution of the database during a run of the walk is especially simple. At any evolution time, CC is empty and LL has at most one record. Moreover, up to norm error O(2−n/2)O(2^{-n/2}), this is the current vertex-label record (except that no label is needed at the entrance since its label is fixed). This follows because the amplitude at a given vertex depends only on its column, independently of the edge permutations. The purified state therefore has no dependence on those permutations and depends on the label permutation only through the current label. More precisely, the compression isometry produces an empty edge database and at most one label record. This record can be identified with the current vertex-label pair up to a small normalization correction, as described in detail in Section A. Since the database record does not distinguish different routes by which the quantum walk reached its current state, contributions from different routes can interfere.

A simulation of the continuous-time dynamics using a finite number of queries introduces bounded simulation error, and intermediate queries can temporarily create additional records. However, this does not change the fundamental conclusion that the database does not store information about the algorithm’s history and is compatible with producing the exit label without recording a path.

Good space. Returning to the hardness of pathfinding, the goal is to show that recording a path in the databases (L,C)(L,C) is difficult. In § 4.1, we define the good space, which is a space of states that have not recorded such a path. As mentioned above, the pair of databases (L,C)(L,C) can be viewed as a representation of the known graph, where LL represents the retained labels and CC the edges. However, an algorithm only interacts with (L,C)(L,C) through cpWT\mathrm{cpWT}. Each query takes in a label-color pair and outputs another label that represents its neighbor, meaning the query does not directly reveal vertex positions in the graph. We describe the labels and edges the algorithm retains by an abstract forest HH, whose connected components are trees HiH_i. Note that HH does not explicitly specify vertex positions. Instead, the actual vertices are written down using the map ϕ\phi from abstract vertices in HH to vertices on the welded trees graph. We call the vertices of the welded trees graph structural vertices.

While HH accurately represents the labels and the connections the algorithm retains, knowing where the exploration began can help the algorithm infer the vertices’ positions. For example, suppose that the algorithm randomly walks from the root. Until it crosses the weld, we know which column each node is in. However, after crossing the weld, the labels and edge colors along the abstract path may no longer tell the algorithm whether its subsequent steps move towards or away from the other root (unless they hit previously explored nodes or a root). To represent this information, for each connected component HiH_i of HH, we define the partial assignment WifixW_i^{\mathrm{fix}} on ϕ\phi. Fix an assignment ϕ\phi and a vertex vv in HiH_i. Starting from vv, follow every path in HiH_i until just after crossing the first weld edge under ϕ\phi or reaching a leaf. The vertices encountered and their positions form the fixed data WfixW^{\mathrm{fix}}. We call these vertices fixed and the remaining vertices in HiH_i free.

Under some fixed HiH_i and WifixW_i^{\mathrm{fix}}, we assign the free vertices to structural vertices on the welded trees graph as follows. Starting from a leaf in the fixed data WifixW_i^{\mathrm{fix}}, we assign successive vertices along the edges of HiH_i. At each step, the edge color and preceding vertex’s position determine the next column and the allowed positions in it, from which we choose uniformly. Let μ\mu denote the distribution over assignments ϕ\phi according to this rule restricted to assignments that remain in the permuted region.

Finally, we define the boundary BB to have two parts, one at each end of the permuted region, each of which is approximately n/3n/3 steps away from each root. Notice that any entrance-to-exit path must cross through this permuted region, so we solely focus on recording a path between the two boundary columns.

An abstract tree $H_i$ consisting of the blue vertices and edges, and the nodes labeled $a$, $b$

Figure 4. An abstract tree HiH_i consisting of the blue vertices and edges, and the nodes labeled aa, bb. The solid vertices denote WifixW_i^{\mathrm{fix}}, while dashed vertices are free, assigned according to μ\mu. Blue assignments to aa, bb are good, while the red assignment is bad. The boundary BB is represented by the shaded region. In general, the boundary on each side consists of two columns of vertices, which happen to include the roots in this small example.

An assignment to the variable ϕ\phi is good if it is in the support of μ\mu, is injective and does not hit the boundary BB outside the fixed part WfixW^{\mathrm{fix}}. Since each WifixW_i^{\mathrm{fix}} of each HiH_i can meet BB only on one side of the weld, a path between the two boundary columns would have to hit BB at a free vertex. This means that if ϕ\phi is good, it cannot contain a path across the region with permuted edges, meaning the corresponding database (L,C)(L,C) it represents cannot contain an entrance-exit path. For each choice of HH and fixed data, we form a superposition over good assignments with amplitudes weighted by μ\sqrt{\mu}. The good space is the span of these states.

Remaining in the good space. In § 4.2, we show that each application of cpWT keeps us in the good space up to a small error by analyzing each operator in its decomposition in Eq. (1). The main difficulty lies in the edge compression operator pCedgep_{C_{\mathrm{edge}}}, where we have to consider adding, deleting and replacing edge records. Adding an edge may violate goodness by hitting the boundary BB outside of the fixed nodes, creating a cycle or joining two trees in the forest HH outside of their fixed parts. We use the distribution μ\mu over assignments to bound these events. Deletion requires a separate argument because databases that differ only in the erased record become identical, which means their amplitudes add. As we saw above, erasing records allows different paths of the quantum walk to interfere. Nonetheless, we show that the resulting state remains in the good space, up to a small error. Finally, controlling both addition and deletion lets us control replacing an edge record.

First, fix some abstract forest HH and data WfixW^{\mathrm{fix}}, and consider the assignments under μ\mu. The first free vertex after the fixed weld edge is assigned randomly among Ω(N)\Omega(N) possible positions, where N=2nN=2^n. Each subsequent step averages over possible assignments, which cannot increase the maximum probability of assignment to a particular vertex. Thus any free vertex has probability O(1/N)O(1/N) of being assigned to a particular structural vertex. Furthermore, even though the positions of any two distinct vertices are not necessarily independent, we show that the probability they are assigned to the same value is O(n/N)O(n/N) when at least one of them is free. After qq queries, we only have O(q)O(q) recorded vertices, so

Pr⁡μ[new vertex hits B or another recorded vertex]=O(∣B∣N+nqN).(2)\Pr_{\mu}[\text{new vertex hits } B \text{ or another recorded vertex}] = O\left(\frac{|B|}{N}+\frac{nq}{N}\right). \tag*{(2)}

For an edge permutation over a column containing ss nodes where s≪Ns \ll N, using the O(q/s)O(q/s) collision estimate at every query would only give an Ω(s1/3)\Omega(s^{1/3}) query lower bound which could not be improved using this estimate alone due to the collision lower bound [4]. However, a free queried vertex is unlikely to lie in this column in the first place, which is why instead we average over its position, allowing us to obtain the Θ~(N1/3)\widetilde{\Theta}(N^{1/3}) bound instead. Fix some queried color and let sbs_b be the size of the permutation for an edge class bb between adjacent columns. By the argument above, if the queried vertex is free, it lies in class bb with probability O(sb/N)O(s_b/N). When this occurs, it will hit one of the O(q)O(q) recorded vertices with probability at most O(q/sb)O(q/s_b). Averaging over all O(n)O(n) edge classes,

∑bO(sbN)⋅O(qsb)=O(nqN),(3)\sum_b O\left(\frac{s_b}{N}\right) \cdot O\left(\frac{q}{s_b}\right) = O\left(\frac{nq}{N}\right), \tag*{(3)}

which gives us the O(nq/N)O(nq/N) term in Eq. (2). Intuitively, a smaller permutation increases the chance of collision, but this is counteracted by the decreasing probability a random walker moving according to μ\mu gets this far up the tree. Otherwise, if the queried vertex is fixed, the same bound applies as the events that violate goodness are either coinciding with another assignment or creating a cycle.

References

  1. [2]Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4), December 2021. doi:10.1145/3488559.DOI
  2. [3]Gorjan Alagic, Joseph Carolan, Christian Majenz, and Saliha Tokat. The sponge is quantum indifferentiable. In Proceedings of the 66th Annual IEEE Symposium on Foundations of Computer Science, pages 2591–2630. IEEE, December 2025. doi:10.1109/FOCS63196.2025.00135.DOI
  3. [4]Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM, 51(4):595–605, July 2004. doi:10.1145/1008731.1008735.DOI
  4. [5]Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510–1523, 1997. doi:10.1137/S0097539796300933.DOI
  5. [6]Shalev Ben-David. Answer to “The randomized query complexity of the conjoined trees problem”. Theoretical Computer Science Stack Exchange, 2014. Posted July 20, 2014. URL: https://cstheory.stackexchange.com/a/25286.
  6. [7]Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, and Daochen Wang. Symmetries, graph properties, and quantum speedups. SIAM Journal on Computing, 53(6):FOCS20–368–FOCS20–415, December 2024. doi:10.1137/23M1573975.
  7. [8]Rajendra Bhatia. Matrix analysis, volume 169 of Graduate Texts in Mathematics. Springer, November 1996.
  8. [9]John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, and Mark Zhandry. Separating QMA from QCMA with a classical oracle. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC ’26, page 595–606. Association for Computing Machinery, 2026. doi:10.1145/3798129.3800776.DOI
  9. [10]Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum cryptanalysis of hash and claw-free functions, page 163–169. Springer, 1998. URL: http://dx.doi.org/10.1007/BFb0054319, doi:10.1007/bfb0054319.
  10. [11]Paul Beame, Niels Kornerup, and Michael Whitmeyer. Quantum time-space tradeoffs for matrix problems. SIAM Journal on Computing, 55(3):469–519, June 2026.
  11. [12]Shankar Balasubramanian, Tongyang Li, and Aram W. Harrow. Exponential speedups for quantum walks in random hierarchical graphs. Communications in Mathematical Physics, 406(9):209, August 2025. doi:10.1007/s00220-025-05370-x.
  12. [13]Joseph Carolan. Compressed permutation oracles. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC ’26, page 150–161. Association for Computing Machinery, 2026. doi:10.1145/3798129.3800736.DOI
  13. [14]Joseph Carolan, Andrew M. Childs, Matthew Coudron, and Amin Shiraz Gilani. A quantum lower bound for path finding in welded trees, 2026. arXiv:2609.26712.arxiv.org/abs/2609.26712
  14. [15]Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC ’03, page 59–68. ACM, June 2003. doi:10.1145/780542.780552.
  15. [16]Andrew M. Childs, Matthew Coudron, and Amin Shiraz Gilani. Quantum Algorithms and the Power of Forgetting. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 37:1–37:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. arXiv:2211.12447v1, doi:10.4230/LIPIcs.ITCS.2023.37.
  16. [17]Yan Mei Chen, Xiao Shan Chen, and Wen Li. On perturbation bounds for orthogonal projections. Numerical Algorithms, 73(2):433–444, 2016. doi:10.1007/s11075-016-0102-2.DOI
  17. [18]Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, and Tai-Ning Liao. On the compressed-oracle technique, and post-quantum security of proofs of sequential work. In Advances in Cryptology – EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, page 598–629. Springer-Verlag, 2021. doi: 10.1007/978–3–030–77886–6_21.arxiv.org/abs/2010.11658
  18. [19]Denis X. Charles, Kristin E. Lauter, and Eyal Z. Goren. Cryptographic hash functions from expander graphs. Journal of Cryptology, 22(1):93–113, 2009. doi:10.1007/s00145–007–9002–x.
  19. [20]Matthew Coudron and Sanketh Menda. Computations with greater quantum depth are strictly more powerful (relative to an oracle). In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing, STOC ’20, page 889–901, 2020. doi:10.1145/3357713.3384269.DOI
  20. [21]Joseph Carolan and Christian Majenz. Compressed permutation oracles revisited, 2026. arXiv: 2609.28469.arxiv.org/abs/2609.28469
  21. [23]Stephen A. Fenner and Yong Zhang. A note on the classical lower bound for a quantum walk algorithm, 2003. arXiv:quant-ph/0312230.DOI
  22. [25]András Gilyén, Matthew B. Hastings, and Umesh Vazirani. (Sub)exponential advantage of adiabatic quantum computation with no sign problem. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing, pages 1357–1369, 2021. arXiv:2011.09495.arxiv.org/abs/2011.09495
  23. [26]Allan Grøn­lund and Kasper Green Larsen. An exponential separation between quantum and quantum-inspired classical algorithms for machine learning, 2024. arXiv:2411.02087.
  24. [28]Amin Shiraz Gilani, Daochen Wang, Pei Wu, and Xingyu Zhou. Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding. In Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis, editors, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), volume 374 of Leibniz International Proceedings in Informatics (LIPIcs), pages 97:1–97:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. doi:10.4230/LIPIcs.ICALP.2026.97.
  25. [29]Yassine Hamoudi. A brief introduction to quantum query complexity, 2025. arXiv:2508.08852.arxiv.org/abs/2508.08852
  26. [30]Yassine Hamoudi and Frédéric Magniez. Quantum time-space tradeoff for finding multiple collision pairs. ACM Trans. Comput. Theory, 15(1–2), June 2023. doi:10.1145/3589986.DOI
  27. [32]Ren-Cang Li. New perturbation bounds for the unitary polar factor. SIAM Journal on Matrix Analysis and Applications, 16(1):327–332, 1995. doi:10.1137/S0895479893256359.
  28. [33]Jianqiang Li. Exponential speedup of quantum algorithms for the pathfinding problem. Quantum Information Processing, 24(3):67, February 2025. doi:10.1007/s11128–025–04689–7.arxiv.org/abs/2307.12492
  29. [34]Seth Lloyd. Universal quantum simulators. Science, 273(5278):1073–1078, 1996. doi:10.1126/science.273.5278.1073.DOI
  30. [35]Yvan Le Borgne and Shrinidhi Teganahally Sridhara. Time-space tradeoffs in searching for a path in welded trees, classically or quantumly, 2025. URL: https://hal.science/hal-04685710v2.
  31. [36]Jianqiang Li and Yu Tong. Exponential quantum advantage for pathfinding in regular sunflower graphs, 2024. arXiv:2407.14398.arxiv.org/abs/2407.14398
  32. [37]Jiaqi Leng, Kewen Wu, Xiaodi Wu, and Yufan Zheng. (Sub)exponential quantum speedup for optimization, 2025. arXiv:2504.14841.arxiv.org/abs/2504.14841
  33. [38]Jianqiang Li and Sebastian Zur. Multidimensional electrical networks and their application to exponential speedups for graph problems. Quantum, 9:1733, 2025. doi:10.22331/q-2025-05-06-1733.DOI
  34. [39]Fermi Ma and Hsin-Yuan Huang. How to construct random unitaries. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 806–809. Association for Computing Machinery, 2025. doi:10.1145/3717823.3718254.DOI
  35. [40]David Miloschewsky and Supartha Podder. Hardness of pathfinding in a welded tree, 2026. arXiv:2609.20651.arxiv.org/abs/2609.20651
  36. [41]Ansis Rosmanis. Quantum snake walk on graphs. Physical Review A, 83(2):022304, February 2011. doi:10.1103/physreva.83.022304.DOI
  37. [42]Ansis Rosmanis. Tight bounds for inverting permutations via compressed oracle arguments, 2022. arXiv:2103.08975.arxiv.org/abs/2103.08975
  38. [43]Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997. doi:10.1137/S0097539795293172.DOI
  39. [45]Takashi Yamakawa and Mark Zhandry. Verifiable quantum advantage without structure. Journal of the ACM, 71(3), June 2024. doi:10.1145/3658665.DOI

Paper details

vlnc:W_hfdhdxax
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

ChatGPT 6 Astra, GPT-6

View statement
Looking for related papers…
Contents