Physicists Solve Difficult Classical Problem with One Quantum Bit

January 8, 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: 12-qubits reached in quantum information quest

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)


Related Stories

12-qubits reached in quantum information quest

May 8, 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

November 9, 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 than conventional ...

Quantum computing may actually be useful, after all

October 9, 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 problems ...

Straightening messy correlations with a quantum comb

November 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 business. Now ...

'Self-correcting' gates advance quantum computing

March 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 to operate quantum ...

Recommended for you

CMS gets first result using largest-ever LHC data sample

February 15, 2019

Just under three months after the final proton–proton collisions from the Large Hadron Collider (LHC)'s second run (Run 2), the CMS collaboration has submitted its first paper based on the full LHC dataset collected in ...

Gravitational waves will settle cosmic conundrum

February 14, 2019

Measurements of gravitational waves from approximately 50 binary neutron stars over the next decade will definitively resolve an intense debate about how quickly our universe is expanding, according to findings from an international ...


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.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.