Wednesday 12 January 2011

Cribsheet - Quantum Computers (for Beginners)

Cribsheet #15 Quantum Computing

Seed’s Tear-Outable Tool for Living in the 21st Century

   Intel cofounder Gordon Moore famously observed nearly half a century ago that the number of transistors economically crammed into a single computer chip was doubling every two years. This trend toward miniaturization is seen throughout the history of modern computing. Today elements of microchips are only tens of nanometers in size, and if miniaturization continues, microchip components will eventually reach atomic scales, where their properties will be dictated by quantum mechanics.

   Miniaturization may ultimately lead to quantum computers, which use quantum effects to perform calculations. Quantum computers could, in principle, solve certain problems exponentially faster than the best known “classical” methods with far-reaching consequences for cryptography and the simulation of quantum physics. Simple quantum computers have already been built, but most experts believe robust and powerful systems remain many years away.

 

The Key Questions of Quantum computing: What is a quantum computer, and how does it differ from modern computers? How can we use quantum computing?

 

Quantum Computing 101

 

Both classical and quantum computers perform calculations by manipulating information. Classical computers represent information as binary digits, or bits, which can have values of either 0 or 1. Quantum computers represent information as quantum bits, or qubits. Many different physical objects can be used as qubits, such as atoms, photons, or electrons. Paradoxically, a qubit can represent 0 and 1, as well as other possible values, at the same time, in what is called a quantum superposition. This allows a qubit to simultaneously use many more informational states for computation and is responsible for quantum computing’s advantages over classical computing. In the illustration above, an atomic spin represents a qubit. An “up” spin corresponds to 0; a “down”spin equates to 1. A quantum superposition encompasses 0, 1 and all possible values in between.

 

 

INTERFERENCE PATTERNS

 

The latent possibilities within a superposition can actually interfere with each other, constructively reinforcing or destructively canceling each other to form the final definite state. The programmer of a quantum computer must choreograph the calculation in such a way that computational paths leading to a “wrong” answer will destructively interfere with each other, canceling each other out and leaving only the “right” answers to be observed.

 

 

 

FINDING AN ANSWER

 

The ability of quantum objects to simultaneously hold multiple, seemingly conflicting values is at the heart of quantum computing. This state is called a quantum superposition (at right). Superpositions occur all the time at the quantum level. In fact, any isolated quantum object like an atom or a photon is in a superposition. But as soon as the object interacts with something else, such as another atom or photon, the superposition is liable to collapse. The collapse of a superposition is called decoherence. Decoherence is essentially an act of measurement, where all possible states in the superposition collapse into the one ultimately observed. If the quantum computer’s qubits suffer too much decoherence before the calculation is completed, the information will be irretrievably lost and the probability of producing a correct answer becomes essentially zero.

 

 

 

 

 

 

 

 

 

 

 

             

 

Fig

 

 

1.    The encryption vital for modern secure communications assumes that factoring large numbers in a reasonable amount of time is beyond the capabilities of today’s commercial computers. In 1994 computer scientist Peter Shor devised an algorithm allowing a quantum computer to quickly factor large numbers. Thus, a powerful quantum computer could break the world’s dominant encryption schemes, resulting in the need for new security methods. For perspective, today’s quantum computers are scarcely powerful enough to factor a number like 15. At right, a schematic illustration outlining how Shor’s algorithm works:

2.    Hundreds or thousands of qubits would be needed to factor very large numbers. For convenience, here we’ve illustrated only four.

3.    Place the qubits in a superposition over all of their possible configurations in preparation for initiating a quantum interference pattern.

4.    Choreograph quantum interference to allow paths to correct answers to reinforce each other.

5.    Perform a measurement, collapsing the qubits’ superposition. By repeating these steps and combining the results, we can reliably obtain the factors of a very large number.

 


What Problems Can a Quantum Computer Solve?

 

 

 

Computer scientists classify a problem’s difficulty by the number of computational steps an algorithm requires to solve it. Problems that a classical computer can quickly solve are called P (polynomial time) problems. In P problems, as the problem size n increases, the number of steps to solve it grows polynomially, for instance by n2. Determining whether a number is prime is an example of a P problem. NP (nondeterministic polynomial time) problems consist of all problems for which the answers are easy to check, even though finding those answers may take an exponential number of computational steps, such as 2n. Every P problem is also an NP problem, but computer scientists believe that not all NP problems are P problems. BQP (bounded-error, quantum polynomial time) problems are the class of problems that quantum computers can efficiently solve. Factoring the product of two large prime numbers is an example of a problem that is both an NP and a BQP problem. Though no one knows for certain, it appears that BQP does not include most NP problems. This means that for most NP problems, quantum computers may offer no significant advantages over classical computers.

 

THE ISSUE: Can we build a sophisticated quantum computer?

 

A company called D-Wave Systems has exhibited what it controversially calls the world’s first commercial quantum computer, but most experts treat these claims with considerable skepticism. Some of the best minds in physics today are struggling to build simple quantum computers, and computer scientists are still seeking their ideal applications. It seems that even if practical, powerful quantum computing existed today, we probably wouldn’t know how to best use it. Ironically, if building sophisticated quantum computers turns out to be impossible in principle, this may be the biggest breakthrough of all, as it would imply that our fundamental understanding of the quantum world is incorrect.

 

SOUNDBITE

 

Quantum computers could theoretically revolutionize our ability to solve certain kinds of computational problems, but first we must discover how best to build and use them.

 


1 comment:

  1. Always prepared for the next generation of technologies, you wont miss the singularity ;)

    ReplyDelete