Physicists Solve Difficult Classical Problem with One Quantum Bit

Jan 08, 2010 By Lisa Zyga feature
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.

( -- 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 “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.”

Explore further: Interview with Gerhard Rempe about the fascination of and prospects for quantum information technology

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)

4.7 /5 (38 votes)

Related Stories

12-qubits reached in quantum information quest

May 08, 2006

In the drive to understand and harness quantum effects as they relate to information processing, scientists in Waterloo and Massachusetts have benchmarked quantum control methods on a 12-Qubit system. Their research was performed ...

Solving big problems with new quantum algorithm

Nov 09, 2009

( -- In a recently published paper, Aram Harrow at the University of Bristol and colleagues from MIT in the United States have discovered a quantum algorithm that solves large problems much faster ...

Quantum computing may actually be useful, after all

Oct 09, 2009

( -- In recent years, quantum computers have lost some of their luster. In the 1990s, it seemed that they might be able to solve a class of difficult but common problems — the so-called NP-complete ...

Straightening messy correlations with a quantum comb

Nov 23, 2009

Quantum computing promises ultra-fast communication, computation and more powerful ways to encrypt sensitive information. But trying to use quantum states as carriers of information is an extremely delicate ...

'Self-correcting' gates advance quantum computing

Mar 12, 2009

( -- Two Dartmouth researchers have found a way to develop more robust “quantum gates,” which are the elementary building blocks of quantum circuits. Quantum circuits, someday, will be used ...

Recommended for you

Progress in the fight against quantum dissipation

23 hours ago

( —Scientists at Yale have confirmed a 50-year-old, previously untested theoretical prediction in physics and improved the energy storage time of a quantum switch by several orders of magnitude. ...

A quantum logic gate between light and matter

Apr 10, 2014

Scientists at Max Planck Institute of Quantum Optics, Garching, Germany, successfully process quantum information with a system comprising an optical photon and a trapped atom.

User comments : 4

Adjust slider to filter visible comments by rank

Display comments: newest first

not rated yet Jan 10, 2010
Well, 640 kB ought to be enough for everyone..
not rated yet Jan 14, 2010
Not really.

So far, almost every quantum computing experiment has been in making an extremely specialized machine (if we can even really call this a machine in this case,)...ahem...machine which runs exactly one algorithm.

To be practical, we need quantum processors that are capable of performing a wide variety of calculations or at least being networked like the components of a PC: CPU, video card, sound card, modem, etc.

In addition, even if the amount of information you could store on a molecule were unlimited in theory, in reality there will be a physical limit in the number and size of detectors needed to "read" and interpret those memory positions for practical computing purposes.

A 640kb quantum computer made by extrapolating the apparatus these scientists are using would probably be like the size of the computers from Forbidden Planet...
not rated yet Jan 15, 2010
@Qunatum_Conundrum: I think you're missing the historical humor here in flaredone's post.

Also, a quantum computer cannot do some of the things that a classical computer can. Computers of the far future will be a hybrid of the two technologies.
not rated yet Jan 15, 2010
Computers of the far future will be a hybrid of the two technologies.
Quantum computers could be parallelized easily with compare to von Neumann architecture. In fact, we can use them for simulation of quantum mechanics phenomena - just in more controlled, larger scale. After all, human brain does similar stuff with its sound solitons. These solitons are quite similar to real 1D quantum waves - i.e. strings of string theory, just simulated in approximately 40 kqubit scale. This scale is sufficiently robust, but it still enables high informational density.

More news stories

Robotics goes micro-scale

( —The development of light-driven 'micro-robots' that can autonomously investigate and manipulate the nano-scale environment in a microscope comes a step closer, thanks to new research from the ...

Tiny power plants hold promise for nuclear energy

Small underground nuclear power plants that could be cheaper to build than their behemoth counterparts may herald the future for an energy industry under intense scrutiny since the Fukushima disaster, the ...

Unraveling the 'black ribbon' around lung cancer

It's not uncommon these days to find a colored ribbon representing a disease. A pink ribbon is well known to signify breast cancer. But what color ribbon does one think of with lung cancer?