Department of Electrical Engineering
Virginia Commonwealth University
Richmond, VA 23284
Date: Wednesday, April 30, 2002
Abstract: Quantum computers promise vastly enhanced computational prowess and an uncanny ability to solve intractable problems. In quantum computation, a logic device is neither in the binary state 1, nor in the state 0, but exists in a coherent superposition of these two states known as a “qubit”. As a result, a n-bit element that can normally store n bits of information, can end up storing 2n bits of information. To put this into proper perspective, it is impossible to make a computer that can store 21000 bits of information since the number 21000 exceeds the total number of atoms in the known universe. However, a 1000-bit quantum computer could store that much information.
More importantly, a quantum computer can solve problems much more efficiently than a classical computer. For example, consider the following problem from a crossword puzzle: --r-nh- (solution: piranha). You have a dictionary with a million words arranged alphabetically. It will take 500,000 attempts to find the correct solution, on the average, using this dictionary. It is very difficult to do any better than that. However, with a quantum computer, you could solve this puzzle within 1000 steps using a quantum search algorithm .
Another example of the uncanny power of quantum computation is evident in the famous Shor’s algorithm which allows a large integer to be factorized into its prime constituents in polynomial steps as opposed to the exponentially large number of steps that even the best classical algorithm can promise. Furthermore, quantum computers will allow a feat known as “quantum teleportation” which allows a sender to teleport a quantum object over arbitrary distances using a construct known as quantum non-locality.
This talk will review basic features of quantum computers and end with a description of our research in this field that could lead to a scalable solid state quantum logic gate where a single electron spin will encode a qubit.
 This example is taken from L. K. Grover, Am. J. Phys., 69, 769 (2001). Grover is the inventor of this quantum search algorithm.