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:1412.2357 · Optics Express

Linear optical demonstration of quantum speed-up with a single qudit

Xiang Zhan, Jian Li, Hao Qin, Zhihao Bian, Peng Xue

Published Jul 7, 2015• 15 citations
arXivHTMLPDF

Abstract

Quantum algorithm acts as an important role in quantum computation science, not only for providing a great vision for solving classically unsolvable problems, but also due to the fact that it gives a potential way of understanding quantum physics. We experimentally realize a quantum speed-up algorithm with a single qudit via linear optics and prove that even a single qudit is enough for designing an oracle-based algorithm which can solve a certain problem twice faster than any classical algorithm. The algorithm can be generalized to higher-dimensional systems with the same two-to-one speed-up ratio.

DOI
10.1364/oe.23.018422

Related papers

Computational speed-up with a single qudit

Z. Gedik, I. A. Silva, Barış Çakmak +5 more

Quantum algorithms are known for providing more efficient solutions to certain computational tasks than any corresponding classical algorithm. Here we show that a single qudit is sufficient to implement an oracle based quantum algorithm, which can solve a black-box problem faster than any classical algorithm. For 2d permutation functions defined on a set of d elements, deciding whether a given permutation is even or odd, requires evaluation of the function for at least two elements. We demonstrate that a quantum circuit with a single qudit can determine the parity of the permutation with only one evaluation of the function. Our algorithm provides an example for quantum computation without entanglement since it makes use of the pure state of a qudit. We also present an experimental realization of the proposed quantum algorithm with a quadrupolar nuclear magnetic resonance using a single four-level quantum system, i.e., a ququart.

arXiv:1403.5861•Scientific Reports•Oct 8, 2015•124 citations

Experimental realization of quantum algorithm for solving linear systems of equations

Jian Pan, Yudong Cao, Xiwei Yao +6 more

Many important problems in science and engineering can be reduced to the problem of solving linear equations. The quantum algorithm discovered recently indicates that one can solve an $N$-dimensional linear equation in $O(logN)$ time, which provides an exponential speedup over the classical counterpart. Here we report an experimental demonstration of the quantum algorithm when the scale of the linear equation is $2\ifmmode\times\else\texttimes\fi{}2$ using a nuclear magnetic resonance quantum information processor. For all sets of experiments, the fidelities of the final four-qubit states are all above 96%. This experiment gives the possibility of solving a series of practical problems related to linear systems of equations and can serve as the basis to realize many potential quantum algorithms.

arXiv:1302.1946•Physical Review A•Feb 12, 2014•121 citations

Simplified experimental scheme of quantum algorithm for solving linear equations with single photons

Xiong Zhang, Zhenwei Yang, Xiangdong Zhang

Linear equations play an important role in nearly all fields of research in science and engineering. Recent studies have shown that quantum algorithms for solving linear systems of algebraic equations provide exponential speedups over their classical counterparts. Here, we present a simplified experimental scheme for implementing the quantum algorithm for solving linear equations with multiple degrees of freedom (DoF) of single photon. Compared with the previous studies, our scheme not only presents excellent efficiency, it requires fewer photons to solve the same problem. Our work highlights the potential applications of multiple DoFs of single photon in quantum information processes.

Optics Express•Jan 31, 2019•1 citation

Introduction to quantum algorithms

Peter W. Shor

These notes discuss the quantum algorithms we know of that can solve problems significantly faster than the corresponding classical algorithms.So far, we have only discovered a few techniques which can produce speed up versus classical algorithms.It is not clear yet whether the reason for this is that we do not have enough intuition to discover more techniques, or that there are only a few problems for which quantum computers can significantly speed up the solution.In the first section of these notes, I try to explain why the recent results about quantum computing have been so surprising.This section comes from a talk I have been giving for several years now, and discusses the history of quantum computing and its relation to the mathematical foundations of computer science.In Sections 2 and 3, I talk about the quantum computing model and its relationship to physics.These sections rely heavily on two of my papers [SIAM J. Comp.26 (1997), 1484-1509; Doc.Math.Extra Vol.ICM I (1998), 467-486].Sections 4 and 5 illustrate the general technique of using quantum Fourier transforms to find periodicity.Section 4 contains an algorithm of Dan Simon showing that quantum computers are likely to be exponentially faster than classical computers for some problems.Section 5 discusses my factoring algorithm, which was inspired in part by Dan Simon's paper.In the final section, I discuss Lov Grover's search algorithm, which illustrates a different technique for speeding up classical algorithms.These techniques for constructing faster algorithms for classical problems on quantum computers are the only two significant ones which have been discovered so far.

Proceedings of symposia in applied mathematics•Jan 1, 2002•56 citations

Theory of the quantum speed-up

Giuseppe Castagnoli, David Ritz Finkelstein

We analyse the quantum speed-up: the fact that some quantum algorithms are faster than their classical counterparts. The classical formulation of problem solving must be modified. In general a problem statement defines the solution only implicitly, giving a property that a solution must possess, and does not represent a process that constructs the solution explicitly. A solution algorithm must then specify explicitly a finite step-by-step procedure that constructs the solution through a dynamical development. In the quantum speed-up, however, an implicit definition directly determines the solution through an extra-dynamical irreversible non-algorithmic quantum measurement. While in an algorithmic solution, the initial conditions determine the solution in a one-way manner, in a solution by measurement, the initial conditions and a final condition influence the solution jointly. The quantum computation is as implicit as the problem statement. Implicit determination with joint influence is richer than explicit one-way dynamical determination, as it yields the speed-up. Quantum problem solving with speed-up is essentially extra-dynamical and irreversible. Other forms of implicit quantum problem solving may exploit extra-dynamical projections for speed-up.

arXiv:quant-ph/0010081•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jul 8, 2001•20 citations

Demonstration of quantum permutation parity determine algorithm in a superconducting qutrit

Kunzhe Dai, Peng Zhao, Mengmeng Li +3 more

A quantum algorithm provides a new way in solving certain computing problems and usually faster than classical algorithms. Here we report an implementation of a quantum algorithm to determine the parity of permutation in a single three-dimensional (3D) superconducting transmon qutrit system. The experiment shows the capacity to speed up in a qutrit, which can also be extended to a multi-level system for solving high-dimensional permutation parity determination problem.

Chinese Physics B•Jun 1, 2018•7 citations
Quantum algorithm acts as an important role in quantum computation science, not only for providing a great vision for solving classically unsolvable problems, but also due to the fact that it gives a potential way of understanding quantum physics. We experimentally realize a quantum speed-up algorithm with a single qudit via linear optics and prove that even a single qudit is enough for designing an oracle-based algorithm which can solve a certain problem twice faster than any classical algorithm. The algorithm can be generalized to higher-dimensional systems with the same two-to-one speed-up ratio.
Quantum algorithms are known for providing more efficient solutions to certain computational tasks than any corresponding classical algorithm. Here we show that a single qudit is sufficient to implement an oracle based quantum algorithm, which can solve a black-box problem faster than any classical algorithm. For 2d permutation functions defined on a set of d elements, deciding whether a given permutation is even or odd, requires evaluation of the function for at least two elements. We demonstrate that a quantum circuit with a single qudit can determine the parity of the permutation with only one evaluation of the function. Our algorithm provides an example for quantum computation without entanglement since it makes use of the pure state of a qudit. We also present an experimental realization of the proposed quantum algorithm with a quadrupolar nuclear magnetic resonance using a single four-level quantum system, i.e., a ququart.
Many important problems in science and engineering can be reduced to the problem of solving linear equations. The quantum algorithm discovered recently indicates that one can solve an NNN-dimensional linear equation in O(logN)O(logN)O(logN) time, which provides an exponential speedup over the classical counterpart. Here we report an experimental demonstration of the quantum algorithm when the scale of the linear equation is $2\ifmmode\times\else\texttimes\fi{}2$ using a nuclear magnetic resonance quantum information processor. For all sets of experiments, the fidelities of the final four-qubit states are all above 96%. This experiment gives the possibility of solving a series of practical problems related to linear systems of equations and can serve as the basis to realize many potential quantum algorithms.
Linear equations play an important role in nearly all fields of research in science and engineering. Recent studies have shown that quantum algorithms for solving linear systems of algebraic equations provide exponential speedups over their classical counterparts. Here, we present a simplified experimental scheme for implementing the quantum algorithm for solving linear equations with multiple degrees of freedom (DoF) of single photon. Compared with the previous studies, our scheme not only presents excellent efficiency, it requires fewer photons to solve the same problem. Our work highlights the potential applications of multiple DoFs of single photon in quantum information processes.
These notes discuss the quantum algorithms we know of that can solve problems significantly faster than the corresponding classical algorithms.So far, we have only discovered a few techniques which can produce speed up versus classical algorithms.It is not clear yet whether the reason for this is that we do not have enough intuition to discover more techniques, or that there are only a few problems for which quantum computers can significantly speed up the solution.In the first section of these notes, I try to explain why the recent results about quantum computing have been so surprising.This section comes from a talk I have been giving for several years now, and discusses the history of quantum computing and its relation to the mathematical foundations of computer science.In Sections 2 and 3, I talk about the quantum computing model and its relationship to physics.These sections rely heavily on two of my papers [SIAM J. Comp.26 (1997), 1484-1509; Doc.Math.Extra Vol.ICM I (1998), 467-486].Sections 4 and 5 illustrate the general technique of using quantum Fourier transforms to find periodicity.Section 4 contains an algorithm of Dan Simon showing that quantum computers are likely to be exponentially faster than classical computers for some problems.Section 5 discusses my factoring algorithm, which was inspired in part by Dan Simon's paper.In the final section, I discuss Lov Grover's search algorithm, which illustrates a different technique for speeding up classical algorithms.These techniques for constructing faster algorithms for classical problems on quantum computers are the only two significant ones which have been discovered so far.
We analyse the quantum speed-up: the fact that some quantum algorithms are faster than their classical counterparts. The classical formulation of problem solving must be modified. In general a problem statement defines the solution only implicitly, giving a property that a solution must possess, and does not represent a process that constructs the solution explicitly. A solution algorithm must then specify explicitly a finite step-by-step procedure that constructs the solution through a dynamical development. In the quantum speed-up, however, an implicit definition directly determines the solution through an extra-dynamical irreversible non-algorithmic quantum measurement. While in an algorithmic solution, the initial conditions determine the solution in a one-way manner, in a solution by measurement, the initial conditions and a final condition influence the solution jointly. The quantum computation is as implicit as the problem statement. Implicit determination with joint influence is richer than explicit one-way dynamical determination, as it yields the speed-up. Quantum problem solving with speed-up is essentially extra-dynamical and irreversible. Other forms of implicit quantum problem solving may exploit extra-dynamical projections for speed-up.