Physicists Solve Difficult Classical Problem with One Quantum Bit

January 8th, 2010 in Physics / Quantum Physics
The molecule transcrotonic acid was used in the quantum algorithm DQC1. The molecule’s four carbon nuclei represent the algorithm’s four qubits, only one of which is initially controlled. The algorithm can solve the Jones polynomial, a difficult classical problem that involves distinguishing different knots. Image copyright: G. Passante, et al.


The molecule transcrotonic acid was used in the quantum algorithm DQC1. The molecule’s four carbon nuclei represent the algorithm’s four qubits, only one of which is initially controlled. The algorithm can solve the Jones polynomial, a difficult classical problem that involves distinguishing different knots. Image copyright: G. Passante, et al.

(PhysOrg.com) -- Quantum information algorithms have the potential to solve some problems exponentially faster than current classical methods. However, most research on quantum information systems has concentrated on models that use multiple quantum bits. In a new study, physicists have demonstrated how to solve a difficult classical problem that completely encapsulates a quantum model that requires only one quantum bit.

The scientists, Gina Passante, et al., from the University of Waterloo in Ontario, Canada, have presented their experimental results for the quantum solution of the approximation of the Jones polynomial, which is a knot invariant. By approximating the Jones polynomial, researchers can determine whether two knots are different. Making this distinction is a fundamental problem in knot theory, and has applications in statistical mechanics, , and quantum gravity. Although approximation of the Jones polynomial is a classical problem that is very difficult to solve, the results show that the problem can be solved using a “one model.” The study is published in a recent issue of .

In order to approximate the Jones polynomial, the scientists implemented a quantum algorithm called deterministic quantum computation with one quantum bit (DQC1). For the purposes of the algorithm, the knots were written as braids, or a series of strands crossing over and under each other with the top and bottom ends connected. Given the braid representations of different knots, the quantum algorithm could distinguish between distinct knots.

As the researchers explain, the DQC1 algorithm extracts the power of one bit of quantum information alongside a register of several qubits.

“The ‘one quantum bit model’ means that there is one initialized in the experiment, meaning that we can only control the initial state of one qubit,” Passante told PhysOrg.com. “For four qubits, the other three qubits are initially in a completely random state.”

The scientists experimentally implemented the algorithm using a liquid state nuclear magnetic resonance (NMR) quantum information processor. They implemented the model with the molecule transcrotonic acid, with its four carbon nuclei representing the algorithm’s four qubits. Then the researchers generated radio frequency pulses, starting randomly and improving through iterations.

“Successful experimental implementation of this algorithm relies on our ability to manipulate the qubits to perform the unitary transformations,” Passante said. “These manipulations must be done very accurately and quickly in order to get a reliable result, since the quantum states are very fragile.”

In simulations, the researchers found that, in the case of knots whose braid representations have four strands and three crossings, the algorithm could identify distinct knots 91% of the time. In the future, the scientists plan to apply the quantum algorithm to larger knots, and determine what size knot can be experimentally implemented before noise and control errors destroy the quantum advantage.

“This work demonstrates the use of an NMR quantum computer to solve an important and practical problem that is not feasible on classical computers,” Passante said. “It is the first experimental implementation of a complete problem for the class of DQC1. In the near future, processing devices hope to solve exciting problems with countless applications, and this experiment is an important stepping stone to realizing larger quantum computers.”

More information: G. Passante, O. Moussa, C.A. Ryan, and R. Laflamme. “Experimental Approximation of the Jones Polynomial with One Quantum Bit.” Physical Review Letters 103, 250501 (2009)

Copyright 2010 PhysOrg.com.
All rights reserved. This material may not be published, broadcast, rewritten or redistributed in whole or part without the express written permission of PhysOrg.com.

"Physicists Solve Difficult Classical Problem with One Quantum Bit." January 8th, 2010. http://phys.org/news182165495.html