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: New research signals big future for quantum radar

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

New filter could advance terahertz data transmission

Feb 27, 2015

University of Utah engineers have discovered a new approach for designing filters capable of separating different frequencies in the terahertz spectrum, the next generation of communications bandwidth that ...

The super-resolution revolution

Feb 27, 2015

Cambridge scientists are part of a resolution revolution. Building powerful instruments that shatter the physical limits of optical microscopy, they are beginning to watch molecular processes as they happen, ...

Precision gas sensor could fit on a chip

Feb 27, 2015

Using their expertise in silicon optics, Cornell engineers have miniaturized a light source in the elusive mid-infrared (mid-IR) spectrum, effectively squeezing the capabilities of a large, tabletop laser onto a 1-millimeter ...

A new X-ray microscope for nanoscale imaging

Feb 27, 2015

Delivering the capability to image nanostructures and chemical reactions down to nanometer resolution requires a new class of x-ray microscope that can perform precision microscopy experiments using ultra-bright ...

New research signals big future for quantum radar

Feb 26, 2015

A prototype quantum radar that has the potential to detect objects which are invisible to conventional systems has been developed by an international research team led by a quantum information scientist at the University ...

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.

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.