Finding problems that allow for superpolynomial quantum speedup is one of the most important tasks in quantum computation. A key challenge is identifying problem structures that can only be exploited by quantum mechanics. In this paper, we find a class of graphs that allows for exponential quantum-classical separation for the pathfinding problem with the adjacency list oracle, and this class of graphs is named regular sunflower graphs. We prove that, with high probability, a regular sunflower graph of degree at least
7 is a mild expander graph, that is, the spectral gap of the graph Laplacian is at least inverse polylogarithmic in the graph size. We provide an efficient quantum algorithm to find an
s-
t path in the regular sunflower graph while any classical algorithm takes exponential time. This quantum advantage is achieved by efficiently preparing a
0-eigenstate of the adjacency matrix of the regular sunflower graph as a quantum superposition state over the vertices, and this quantum state contains enough information to help us efficiently find an
s-
t path in the regular sunflower graph. Because the security of an isogeny-based cryptosystem depends on the hardness of finding an
s-
t path in an expander graph \cite{Charles2009}, a quantum speedup of the pathfinding problem on an expander graph is of significance. Our result represents a step towards this goal as the first provable exponential speedup for pathfinding in a mild expander graph.
Recently, Apers and Piddock [TQC '23] strengthened the connection between quantum walks and electrical networks via Kirchhoff's Law and Ohm's Law. In this work, we develop a new multidimensional electrical network by defining Alternative Kirchhoff's Law and Alternative Ohm's Law based on the multidimensional quantum walk framework by Jeffery and Zur [STOC '23]. In analogy to the connection between the incidence matrix of a graph and Kirchhoff's Law and Ohm's Law in an electrical network, we rebuild the connection between the alternative incidence matrix and Alternative Kirchhoff's Law and Alternative Ohm's Law. This new framework enables generating an alternative electrical flow over the edges on graphs, which has the potential to be applied to a broader range of graph problems, benefiting both quantum and classical algorithm design. We first use this framework to generate quantum alternative electrical flow states and use it to find a marked vertex in one-dimensional random hierarchical graphs as defined by Balasubramanian, Li, and Harrow [arXiv '23]. In this work, they generalised the exponential quantum-classical separation of the welded tree graph by Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman [STOC '03] to random hierarchical graphs. Our result partially recovers their results with an arguably simpler analysis. Furthermore, this framework also allows us to demonstrate an exponential quantum speedup for the pathfinding problem in a type of regular graph, which we name the welded tree circuit graph. The exponential quantum advantage is obtained by efficiently generating quantum alternative electrical flow states and then sampling from them to find an s-t path in the welded tree circuit graph. By comparison, Li [arXiv '23] constructed a non-regular graph based on welded trees and used the degree information to achieve a similar speedup.
Simon’s problem is to find a hidden period (a bitstring) encoded into an unknown 2-to-1 function. It is one of the earliest problems for which an exponential quantum speedup was proven for ideal, noiseless quantum computers, albeit in the oracle model. Here, using two different 127-qubit IBM Quantum superconducting processors, we demonstrate an algorithmic quantum speedup for a variant of Simon’s problem where the hidden period has a restricted Hamming weight w . For sufficiently small values of w and for circuits involving up to 58 qubits, we demonstrate an exponential speedup, albeit of a lower quality than the speedup predicted for the noiseless algorithm. The speedup exponent and the range of w values for which an exponential speedup exists are significantly enhanced when the computation is protected by dynamical decoupling. Further enhancement is achieved with measurement error mitigation. This case constitutes a demonstration of a bona fide quantum advantage for an Abelian hidden subgroup problem.