Experimental Demonstration
of a Quantum Algorithm
for a Set of Linear Equations
Quantum computers exploit the
properties of quantum physics, such
as, the quantum superposition principle,
quantum entanglement and
so on, to process information. These
computer offer significant speedup
compared to their classical counterpart,
for instance in factorizing a
large integer [1], or finding a target
in an unsorted database [2]. These
quantum algorithms are not only
important mathematically, but also
important in practice because they
pose a deadly threat to existing cryptography.
The development of quantum algorithms
follows three directions. One
develops from the Shor algorithm,
and grows into the phase estimation
and related algorithms. Another
follows from the Grover algorithm,
which develops into the quantum
amplitude amplification and related
quantum algorithms. The third direction
is the quantum simulation in
which a quantum system is simulated
efficiently in a quantum computer,
which is exponentially faster than
classical computers [3].
Using quantum phase estimation,
a novel quantum algorithm was
designed that solves a set of linear
equations exponentially faster than
its classical counterpart [4]. Now this
quantum algorithm has been successfully
demonstrated by a group of
physicists led by Prof. Jianwei Pan,
from the University of Science and Technology, in Hefei, China [5].
They have used 4 photonic qubits
and demonstrated a set of two linear
equations. They used lasers to prepare
two pairs of entangled photons,
which they spatially separated and
sent down four different paths. The
photons passed through a series of
logic gates that corresponded to the
steps of solving two linear equations.
Their experiment has shown the feasibility
of the algorithm.
References

[1]
 P. Shor, SIAM J. Comput. 26, 1484 (1997).

[2]
 Lov Grover, Proceedings of the twentyeighth annual ACM symposium on Theory of computing, Pages 212219,1996.

[3]
 R. P. Feynman, Int. J. Theor. Phys. 21, 467 (1982); S. Lloyd, Science 273, 1073 (1996).

[4]
 A.W. Harrow, A. Hassidim, and S. Lloyd, Phys. Rev. Lett. 103, 150502 (2009).

[5]
 X.D. Cai, C. Weedbrook, Z.E. Su, M.C. Chen, Mile Gu, M.J. Zhu, Li Li, NaiLe Liu, ChaoYang Lu, and JianWei Pan, Phys. Re v. Lett. 110, 230501 (2013)