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• 16 citations

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, B. Çakmak +5 more

arXiv:1403.5861Scientific ReportsOct 8, 2015110 citations

Computational speed-up with a single qudit

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

Oct 8, 201531 citations

Experimental realization of quantum algorithm for solving linear systems of equations

Jian Pan, Yudong Cao, Xiwei Yao +6 more

arXiv:1302.1946Physical Review AFeb 12, 2014110 citations

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

Xiong Zhang, Zhenwei Yang, Xiangdong Zhang

Optics ExpressJan 31, 20191 citation

Theory of the quantum speed-up

Giuseppe Castagnoli, David Ritz Finkelstein

arXiv:quant-ph/0010081Proceedings of the Royal Society A Mathematical Physical and Engineering SciencesJul 8, 200116 citations

Quantum algorithms know in advance 50 % of the solution they will find in the future

Jan 1, 20091 citation

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• 16 citations

arXiv HTML PDF

Abstract

DOI: 10.1364/oe.23.018422

Related papers

Computational speed-up with a single qudit

Z. Gedik, I. A. Silva, B. Ç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.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.5861Scientific ReportsOct 8, 2015110 citations

Computational speed-up with a single qudit

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

Oct 8, 201531 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.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.1946Physical Review AFeb 12, 2014110 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.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 ExpressJan 31, 20191 citation

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.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/0010081Proceedings of the Royal Society A Mathematical Physical and Engineering SciencesJul 8, 200116 citations

Quantum algorithms know in advance 50 % of the solution they will find in the future

Quantum algorithms require less operations than classical algorithms. The exact reason of this has not been pinpointed until now. Our explanation is that quantum algorithms know in advance 50 % of the solution of the problem they will find in the future. In fact they can be represented as the sum of all the possible histories of a respective ”advanced information classical algorithm”. This algorithm, given the advanced information (50 % of the bits encoding the problem solution), performs the operations (oracle’s queries) still required to identify the solution. Each history corresponds to a possible way of getting the advanced information and a possible result of computing the missing information. This explanation of the quantum speed up has an immediate practical consequence: the speed up comes from comparing two classical algorithms, with and without advanced information, with no physics involved. This simplification could open the way to a systematic exploration of the possibilities of speed up. 1Quantum algorithms require less operations than classical algorithms. The exact reason of this has not been pinpointed until now. Our explanation is that quantum algorithms know in advance 50 % of the solution of the problem they will find in the future. In fact they can be represented as the sum of all the possible histories of a respective ”advanced information classical algorithm”. This algorithm, given the advanced information (50 % of the bits encoding the problem solution), performs the operations (oracle’s queries) still required to identify the solution. Each history corresponds to a possible way of getting the advanced information and a possible result of computing the missing information. This explanation of the quantum speed up has an immediate practical consequence: the speed up comes from comparing two classical algorithms, with and without advanced information, with no physics involved. This simplification could open the way to a systematic exploration of the possibilities of speed up. 1

Jan 1, 20091 citation

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.