Fast quantum mechanical algorithms

Details Fast quantum mechanical algorithms Fast quantum mechanical algorithms

1998-11-02

2001-11-13

Mai, Tan V. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06317766

ABSTRACT:

BACKGROUND
This invention relates to computing and, more particularly, to computing with quantum computers.
Quantum computers were first considered in the 70's and early 80's. In 1980, it was shown that a quantum computer could, in principle, compute anything that could be computed by a classical computer. Indeed, Richard Feynman discovered an example of a quantum mechanical system which seemed very difficult to simulate on a classical computer, but which a quantum computer could easily do in polynomial time. Later, the description of quantum computers was formalized, and a number of examples were discovered in which a quantum computer could solve more efficiently than a classical computer.
At the present time, there are still two major considerations relating to quantum computers: how do you build a quantum computer, and what kinds of algorithms could best utilize the inherent characteristics of such a computer.
Quantum computer hardware is still in its infancy. The number of quantum computer designs that have been reported in the art is quite small. One widely discussed model is that of Cirac and Zoller (Phys. Rev. Lett. 74, 4091, 1995) who showed how to use laser-cooled trapped ions as quantum logic and memory devices. In an ion trap, individual atoms are suspended by electromagnetic forces in an ultra-high vacuum, where they are almost completely de-coupled from their environment. The general principles underlying ion trap operations are found in U.S. Pat. Nos. 5,248,883 and 5,379,000. Other physical systems have also been proposed for quantum logic; for example, nuclear spins in solids. See U.S. Pat. No. 5,530,263. A photon model has been tested in an experiment by Kimble et al and reported on in Phys. Rev. Lett. 75, 4710, 1995. U.S. Pat. No. 5,793,091, issued Aug. 11, 1998, titled “Parallel Architecture for Quantum Computers Using Box Trap Arrays” describes a quantum computer architecture that uses many small quantum channels for frequently performed logic and memory operations, and a few large channels for infrequently performed operations.
More recently, in an article titled “Experimental Implementation of fast quantum searching” Isaac Chuang et al reported in Phys. Rev. Lett. Vol. 80, No. 15, April 1998, on a quantum computer implementation that employs the spins of carbon and hydrogen nuclei in chloroform. This is a significant achievement because, as indicated above, not only is building a quantum computer a challenging task, but employing such a computer effectively to solve a useful problem is equally challenging. The Chuang et al article should go a long way to convince designers of the quantum computer's ultimate usefulness.
The realm of algorithms that are particularly well suited for quantum computers has not been without advances either. In 1994, Peter Shor presented an efficient quantum mechanical algorithm for factorization, that is exponentially faster than any known classical algorithm, Factorization is an important problem because numerous encryption systems rely on the fact that classical computers require a very long time to factor large numbers.
In Jul. of 1997, I published an article titled “Quantum Mechanics Helps in Searching for Needle in a Haystack,” in Phys. Rev. Letrs., Vol. 79, No. 2, pp. 325-328, describing an algorithm that is polynomially faster than any classical algorithm. This algorithm finds a desired object in an unsorted database in &ogr;({square root over (N)}) steps, as compared to &ogr;(N) for the classical search. Other quantum mechanical algorithms for important computer science problems have also been discovered, but there is still no general technique for obtaining efficient quantum algorithms.
SUMMARY
This disclosure presents a general quantum mechanical algorithm and system architecture that efficiently solve many classes of real-world problems. Specifically, it demonstrates that quantum mechanical problems are solved efficiently when any unitary matrix U is employed, and a transformation Q is applied, where Q≡−I
s
U
−1
I
t
U. I
s
is a diagonal matrix that characterizes the starting state of the system with 1's in every position along the diagonal, except at the position corresponding to column s and row s, which represents the starting state, where it is −1. I
t
is a similar diagonal matrix that characterizes the desired target state, t. The Q transformation is applied a prescribed number of times, followed by a single transformation U, yielding the desired target state.


REFERENCES:
patent: 5248883 (1993-09-01), Brewer et al.
patent: 5379000 (1995-01-01), Brewer et al.
patent: 5530263 (1996-06-01), DiVincenzo
patent: 5768297 (1998-06-01), Shor
patent: 5793091 (1998-08-01), Devoe
patent: 5838436 (1998-11-01), Hotaling et al.
patent: 5940193 (1999-08-01), Hotaling et al.
patent: 6081882 (2000-06-01), Gossett
patent: 6218832 (2001-04-01), Chuang et al.

Affiliated with

Also associated with

Rating

Fast quantum mechanical algorithms does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fast quantum mechanical algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast quantum mechanical algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2611453