Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1912.00978 · Quantum Information Processing

Efficient and scalable quantum walk algorithms via the quantum Fourier transform

Asif Shakeel

Published Aug 31, 2020• 22 citations
arXivHTMLPDF
DOI
10.1007/s11128-020-02834-y

Related papers

Generalized Quantum Fast Transformations via Femtosecond Laser Writing Technique

Fulvio Flamini, Niko Viggianiello, Marco Bentivegna +6 more

Quantum computers promise to be able to solve tasks beyond the reach of standard computational platforms.Among the others, photonic quantum walks prove to be great candidates for their implementation, since single photon sources, passive linear optics and photo-detectors are sufficient for universal quantum computation.To this aim, a device performing the quantum Fourier transform represents a fundamental building block for quantum algorithms, whose applications are not limited to the field of quantum computation.Recently, an algorithm has been developed to efficiently realize a quantum Fourier transform of an input photonic state by using a quantum walk on elementary linear-optical components.Here we provide a simple operative description of the algorithm, introducing a whole class of quantum transformations achievable through a generalization of this procedure.We finally discuss how femtosecond laser writing technology well represents an efficient and scalable platform for the implementation of this class of photonic quantum walks.

Interdisciplinary Information Sciences•Jan 1, 2017•3 citations

Quantum Algorithms Using Quantum Fourier Transform

이두영

•Jan 1, 2018•0 citations

Applications of quantum walk algorithms

de Jan Vos

•Aug 1, 2006•0 citations

Exponential algorithmic speedup by a quantum walk

Andrew M. Childs, Richard Cleve, E. Deotto +3 more

We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2003•134 citations

Quantum Walks and Search Algorithms

Renato Portugal

Springer eBooks•Jan 1, 2013•478 citations

Exponential algorithmic speedup by a quantum walk

Andrew M. Childs, Richard Cleve, E. Deotto +3 more

We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time.

arXiv:quant-ph/0209131•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2003•822 citations
Quantum computers promise to be able to solve tasks beyond the reach of standard computational platforms.Among the others, photonic quantum walks prove to be great candidates for their implementation, since single photon sources, passive linear optics and photo-detectors are sufficient for universal quantum computation.To this aim, a device performing the quantum Fourier transform represents a fundamental building block for quantum algorithms, whose applications are not limited to the field of quantum computation.Recently, an algorithm has been developed to efficiently realize a quantum Fourier transform of an input photonic state by using a quantum walk on elementary linear-optical components.Here we provide a simple operative description of the algorithm, introducing a whole class of quantum transformations achievable through a generalization of this procedure.We finally discuss how femtosecond laser writing technology well represents an efficient and scalable platform for the implementation of this class of photonic quantum walks.
We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time.
We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time.