Quantum computer

A quantum computer and quantum computer is a computer whose function is based on the laws of quantum mechanics. Unlike the digital computer it does not work on the basis of the laws of classical physics or computer science, but on the basis of quantum-mechanical states, which goes substantially beyond the rules of classical theories (see for example Bell's inequality), and the processing is done of these states according to quantum mechanical principles. These are mainly

Theoretical studies can be solved much more efficiently suggest that taking advantage of these effects specific problems of computer science, such as searching in extremely large databases (see Grover algorithm) and the product decomposition extremely long numbers (see Shor algorithm) than with classical computers. This would make the mathematical problem, which is the basis for the security of widely used cryptographic techniques, easily detachable and these become useless.

The quantum computer is currently still a largely theoretical concept. However, there is now a variety of proposals, such as a quantum computer could be realized, and on a small scale, some of these concepts were tested in the laboratory and have been implemented with few qubits quantum computer; but from an actual application and practical use is still far away.

• 7.1 predictability
• 7.2 complexity

Qubits

In a classical computer, all information is represented in bits. Physically, a bit realized in that a voltage potential is either above a certain level ( which corresponds to the binary value "1" ) or below ( "0").

In a quantum computer, information is represented in binary as a rule. For this purpose, use is made of a physical system with two basic states of a two-dimensional complex space, as occurs in quantum mechanics. A basic state represents the quantum mechanical state vector, the state vector of the other. This one uses the conventional in quantum physics Dirac notation. These " two-level systems " of quantum mechanics, it can be for example, the spin of an electron, which is either upward or downward. Other implementations make use of the energy level of molecules or atoms or in the direction of a current flow in an annular superconductor.

The term qubit is to emphasize the quantum mechanical nature of the bits shown in this way and is derived from quantum bit off.

An important property of a quantum-mechanical state vectors in this context that this can be a superposition of the other states. This is also called superposition. In the specific case, this means that a qubit either not or must be, as is the case for the bits of the conventional computer. Rather, the state of a qubit in the above-mentioned two-dimensional complex space yields generally

Are being admitted as in coherent optics arbitrary superposition states. The difference between classical and quantum mechanical computing is thus analogous to that between incoherent and coherent optics ( in the first case the intensities are added, in the second directly the field amplitudes, such as in holography ).

Here, and arbitrary complex numbers. For normalization, but we demand without loss of generality yet. The absolute squares of complex numbers and give the probability for it to get as a result of a measurement on the state the value 0 or 1. Thus, for example, the probability of measuring a 0. One must this probabilistic behavior but not so interpret that the qubit with a certain probability in the state and with another probability is in the state, while other states are not allowed. Such an " exclusionary " conduct could also be achieved with a classical computer, which uses a random number generator to determine the occurrence of superimposed states whether to continue expects 0 or 1. In theoretical physics comes before a corresponding exclusionary behavior in the so-called statistical physics, in contrast to quantum mechanics is so incoherent.

Taking into account the coherent superposition is obtained, however, generally

Wherein the real part of the complex number is, the complex conjugate number, and to the quantum dot of the respective states.

Quantum register, " entanglement"

As in the classic computer also, one summarizes several qubits together to quantum registers. The state of a qubit register is then under the laws of many-body quantum mechanics a state from one -dimensional Hilbert space. A possible basis of this vector space is the product base on the base. For a register of two qubits would be obtained, therefore the base. And the state of the register can be any superposition of basis states, ie when N qubits of the mold with any complex numbers and the conventional dual basis. Also sums or differences of such terms are allowed, whereas in classical computers, only the base states themselves occur, ie composed of the digits 0 or 1 prefactors. An important property of a quantum register is that the conditions can not always be composed of the independent states of qubit example, one can not break down in the state of a product of a state for the first state and the second qubit.

We call such a state, therefore, also crossed ( in the English literature one speaks of " entanglement "). The same applies also to the state of various

The property of entanglement is also an indication that quantum computers can be more powerful than classical computers, ie that they can solve certain problems much faster in principle, than is possible with classical computers: To represent the state of a classical bit register, bits of information are required. However, the state of the quantum register is a vector of one - dimensional vector space, so you have to specify complex valued for its representation coefficients. Here it is essential that for large n, the number is much greater than 2N N itself

The superposition principle is often illustrated as a quantum computer in a quantum register of qubits simultaneously could all numbers from 0 to save. This notion is misleading. Since a measurement taken at the register always just selects one of the basis states, it can be shown using the so-called Holevo 's theorem that the maximum accessible information content of a single qubit unverschränkten exactly is a bit like in the classical case. It is nevertheless true that the principle of superposition parallelism allowed in the bills that go beyond much of what happens in a classical " parallel computers ". In the minds of some quantum algorithms is discussed in more detail.

Quantum gates

In classical computer through logic gates (English Gates ) are carried out elementary operations on bits. Several gates are connected to a switching network that can perform complex operations such as adding two binary numbers. The gates are realized by physical devices such as transistors and passed the information as an electrical signal through these devices.

Calculations on a quantum computer run fundamentally different from: A quantum gate (English Quantum Gate) is not a technical device, but is from an elementary physical manipulation of one or more qubits dar. How exactly looks like a manipulation depends on the actual physical nature of the qubit. Thus, for the spin of an electron by incident magnetic fields affect the excited state of an atom by laser pulses. Thus, although a quantum gate is no electronic component, but one that is applied to the quantum register in the course of time, action, describing quantum algorithms with the aid of circuit diagrams, cf the article List of quantum gates.

Spoken formally a quantum gate is a unitary operation, the effect on the state of the quantum register:

A quantum gate can therefore be written as a unitary matrix. A gate, which reverses the state of a qubit ( negated), would correspond to the case of a two-dimensional state space of the following matrix:

To write are more complicated quantum gates ( unitary matrices ), which modify the two-or multi - Qubitzustände, such as in defined CNOT gate, with the "two- qubit " state table and you can asserted additional to bodies indices a and b symmetrized or antisymmetrisieren, approximately according to the scheme whereby entangled states arise, as is characteristic of quantum mechanics.

A quantum circuit now comprises a plurality of quantum gates that are used in fixed time sequence on the quantum register. Examples include the quantum fourier transform, or Shor algorithm. Mathematically, a quantum circuit, a unitary transformation, the matrix is simply the product of the matrices of the single quantum gates.

One-way quantum computer

Another approach to implementation of a quantum computer is the so-called one-way quantum computer (one-way quantum computer, Hans J. Briegel, Robert versions Endorf 2001). This differs from the circuit model in that a first universal is (that is independent of the problem ) is generated entangled quantum state (such as a so-called cluster state), and the actual calculation is performed by specific measurements in this state. In this case, determine the results of previous measurements are performed which further measurements.

Unlike in the circuit model of this folded quantum state is only used as a resource. In the actual calculation only individual qubits of the state used to be measured and performed classical calculations. In particular, no multi - qubit operations are performed ( the production of the state requires such course). Nevertheless it can be shown that the one-way quantum computer performs just as well as a value based on the circuit model quantum computer.

Adiabatic quantum computers

Another approach for a quantum computer is based on an entirely different concept: According to the laws of quantum mechanics is a quantum mechanical system that initially in the ground state ( minimum energy state ) is a time-independent system, even with changes to the system in the ground state, if the change only sufficiently slowly (ie adiabatic) happens. The idea of the adiabatic quantum computer is now to construct a system that has a ground state, which corresponds to the solution of a particular problem, and another, whose ground state is easy to prepare experimentally. Subsequently, the system easily to be prepared is transferred into the system, to the ground state one is interested in, and the state then measured. If the transition is done slowly enough, you have the solution of the problem.

The company D - Wave Systems in 2007 claims to have developed a commercially viable quantum computer, which is based on this principle. On 26 May 2011 the company D-Wave Systems sold the first commercial quantum computer "D -Wave One" at the Lockheed Martin Corporation. However, their results are still controversial.

Physical realization

The concept described so far is at first abstract and universal. In theoretical terms the treatment of quantum computers is therefore already quite advanced. If you want to build a concrete usable quantum computer, one must consider the natural physical limitations, which are described below.

Relaxation

If you leave a system itself, it tends to occupy a state with the lowest possible energy. This leads to a qubit in the state after a certain time has jumped with a certain probability in the condition. This process is called relaxation. The relaxation time is exponentially distributed with it.

Decoherence

With the loss decoherence of superposition properties of a quantum state is meant. Through the influence of the environment develops from any superposition state ( with ) either the state or the state ( with corresponding probabilities, which may be, for example, given by, while "mixed terms " (for example ) does not occur ( " state reduction ", " incoherent " versus " coherent " superposition, " thermalization ", as in statistical physics ) ). Then the qubit behaves just like a classical bit. The decoherence time is also usually exponentially, and typically much smaller than the relaxation time. During the relaxation is also a problem for classical computers ( such magnets could be on the hard disk spontaneously reverse the polarity ), decoherence is a purely quantum mechanical phenomenon.

The reliability of quantum computers can be increased by the so-called quantum error correction.

Computability and Complexity Theory

Since formally defined as a quantum computer works, which are known from theoretical computer science concepts such as predictability or complexity class can be applied to a quantum computer. It is found that a quantum computer can solve any fundamentally new problems, some problems to be resolved quickly, however.

Predictability

A classical computer can simulate a quantum computer, since the effect of gates on the quantum register of a matrix -vector multiplication corresponds. The classic computer must now easily perform all these multiplications to transform the initial to the final state of the register.

Direct consequence of the simulatability is that all problems that can be solved on a quantum computer can be solved on a classical computer. Conversely, this means that problems such as the halting problem on a quantum computer can not be solved.

It can be shown that the simulation of a quantum computer in the complexity class PSPACE is. It is therefore considered that there is no simulation algorithm that simulates a quantum computer with polynomiellem loss of time.

Conversely, simulate a classical computer, a quantum computer. Therefore one must first know that any logical circuit can be formed solely of NAND gates. The Toffoli gate can be obtained a quantum gate with appropriate wiring of the three inputs now that behaves on qubits in the basis of classical bits as a NAND gate. In addition, the Toffoli gate can be used to double an input bit. Due to the no- cloning theorem, this is only possible for the states. This doubling ( also called fan-out ) is necessary because it is possible in a classical circuit to spread a bit on two lines.

Complexity

In the context of complexity theory, it associates algorithmic problems known complexity classes. The best known and most important of which are the classes P and NP. Here P denotes those problems whose solution can be computed deterministically in polynomial for input length runtime. In NP are the problems to which it gives solution algorithms that are non- deterministic polynomial time. The non-determinism allows simultaneously abzutesten different ways. Since our current computer run deterministically, the non-determinism by sequential execution of the various options must be simulated, so that the polynomiality of the solution strategy may be lost.

For a quantum computer to define the complexity class BQP. This includes those problems whose running time polynomially dependent on the input length and its error probability is below. It follows from the previous section that BQP PSPACE. Furthermore, P BQP is true because a quantum computer can simulate classical computers with only polynomiellem loss of time.

How is BQP to the important class NP in relationship is still unclear. You do not know if a quantum computer to solve an NP -complete problem efficiently or not. If one could prove that BQP is a proper subset of NP, so that would be solved the P- NP problem: Then, namely, P NP. Secondly, from the proof that NP is a proper subset of BQP, follow that P is a proper subset of PSPACE. Both the P- NP problem and the question P PSPACE are important unresolved issues of theoretical computer science.

Algorithms for quantum computers

The previously found algorithms for quantum computers can be roughly divided into three categories:

• Algorithms based on the quantum fourier transform. Among them the most famous algorithm for quantum computers, the Shor algorithm falls factorization of large integers. The time is polynomial in the number of digits. In contrast, the best currently -known classical algorithm, the number field sieve, superpolynomiell (but sub-exponentially ) takes much time. The importance of Shor's algorithm is based on the fact that the security of the widely used asymmetric encryption methods such as RSA is based on that no efficient "classical" algorithms for factoring large numbers are known.
• Quantum search algorithms. This includes which of the Grover algorithm and variants. It is used for efficient search in an unsorted array. An ordinary computer must be on entries in the worst case View all entries ( ie compare ), this classic problem is thus solved in steps of calculation. On a quantum computer you can do this with the Grover algorithm in just completing operations. This bound is tight, ie, no quantum algorithm can solve this problem in ( asymptotically ) less operations. It follows that, in general no benefit is to be expected exponential rate with the use of quantum algorithms.
• Quantum simulation. In order to simulate quantum mechanical systems, it makes sense to re- use quantum mechanical systems. With an appropriate set of quantum gates, each Hamiltonian can be represented, and sufficient in many cases to a small number of gates from. Algorithms of this kind would play in particular for quantum chemistry an immense role, as with today's means simple molecules can not be simulated without gross approximations themselves.

Many algorithms for quantum computers provide a certain probability of a correct result; one speaks of probabilistic algorithms. By repeatedly applying the algorithm the probability of error, however, can be arbitrarily small. If the initial success probability large enough range of a few repetitions.

Architecture for quantum computers

All previously experimentally demonstrated a "quantum computer " consisted of only a few qubits and were not scalable in terms of decoherence and error rates even in regard to the architecture used. Sub-architecture is understood in this context in particular the concept of scalable arrangement of a very large number of qubits: how to ensure that the error rate per gate is small ( below the threshold for fault-tolerant computing ) regardless of the number of qubits of the quantum computer and on the spatial distance of the qubits involved in the quantum register.

The problem was summarized by David P. DiVincenzo in a catalog of five criteria that must be met by a scalable, fault-tolerant quantum computer. The DiVincenzo criteria are

The main requirements arising in this case from the first and the last point. Scalability in this case means that it must in principle be possible to arbitrarily large to choose the number of qubits and that other properties must be met regardless of the number of qubits. The threshold for fault-tolerant computing, depending on the used code and used geometry of the quantum register with an error probability of (or even smaller values ​​) per gate. So far, no universal set of gates with this accuracy has been realized. Often the criteria are supplemented by two others that relate to the networking of quantum computers:

The search for a scalable architecture for fault tolerant quantum computers is the subject of intense current research. The central question here is how you can achieve that quantum gates on different qubits in parallel (simultaneously) can be executed even if the interaction between the physical qubits is local, ie not every qubit with each other is in direct interaction. Depending on the used concept ( gate network, one-way quantum computer, adiabatic quantum computer, ...) and the chosen implementation ( trapped ions, superconducting circuits, ...) There do many different suggestions, but so far at best for very small prototypes have been demonstrated. One of the most concrete and far advanced proposals include the following:

• Quantum computer in microstructured ion trap: qubits are realized by the internal state of individual trapped ions. In a microstructured trap the ions are controlled between memory and interaction regions reciprocated. Rather than to be coupled with each other ions to move into a common interaction region, including long-range interactions between them could be used. In experiments at the University of Innsbruck, it was demonstrated that as the electrical dipole interaction between small groups of oscillating ions ( which act as antennas ) can be used for coupling of the ions which are more than 50 microns apart, are used.
• Superconducting qubits in a two-dimensional network of superconducting stripline resonators ( stripline resonators )
• Quantum computer based on nitrogen -vacancy centers ( " NV- centers " ) in Diamond: As qubits acting nuclear spins of nitrogen atoms in a two-dimensional grid of NV centers; Selection and coupling via the electronic spin of the NV center, in which the coupling is achieved by the magnetic dipole interaction; inhomogeneous magnetic fields allow individual addressing and parallel operation on many qubits.

Research

Quantum computer with just a few qubits have already been realized. So Shor's algorithm was realized in 2001 with a price based on nuclear magnetic resonance quantum computer at the IBM Almaden Research Center for a system with 7 qubits and 15 could successfully break down the number into its prime factors 3 and 5. Also was able to realize the German - Jozsa algorithm in 2003 based on a stored in ion traps particles quantum computer.

In November 2005, the first time succeeded Rainer Blatt at the Institute for Experimental Physics, University of Innsbruck, to create a quantum register with eight entangled qubits. The entanglement of all eight qubits has to be verified by measurements of 650,000 and took 10 hours.

In March 2011, the Innsbruck scientists have this record again almost doubled. In an ion trap, they catch 14 calcium atoms, which they then manipulated a quantum processor with laser light.

At Yale University, New Haven, a research team led by Leo DiCarlo cooled a two - qubit register on a long 7 mm and 2 mm wide, from a multi-curved channel by early quantum processor to a temperature of 13 mK from, and generated so that a 2 - qubit quantum computer register in one piece. The superconducting chip played according to a publication by Nature for the first time quantum algorithms.

A group of researchers at the National Institute of Standards and Technology ( NIST) in Boulder, USA, in 2011, it is managed to entangle ions using microwaves for use in a quantum computer. The NIST research group has shown that one can only be achieved with a complex, room-filling laser system such operations do not, but also with miniaturized microwave electronics. To produce the interleaving, the physicist integrated microwave source to the electrodes of a so-called chip case, a microscopic chip-like structure for the storage and manipulation of the ions in a vacuum cell. With this experiment, the researchers have shown that the entanglement of ions works with microwaves in 76 percent of all cases. The laser- based quantum logic gates used in research for several years, with a rate of 99.3 percent still better than the gate on the basis of microwaves. The new method has the distinct advantage that it only takes about one-tenth the space of a laser experiment.

On January 2, 2014, the Washington Post reported, citing documents the whistleblower Edward Snowden that the National Security Agency ( NSA ) of the USA is working to develop a " cryptologically useful" quantum computer.