BQP - Quantum Computation

Quantum Computation

The number of qubits in the computer is allowed to be a polynomial function of the instance size. For example, algorithms are known for factoring an n-bit integer using just over 2n qubits (Shor's algorithm).

Usually, computation on a quantum computer ends with a measurement. This leads to a collapse of quantum state to one of the basis states. It can be said that the quantum state is measured to be in the correct state with high probability.

Quantum computers have gained widespread interest because some problems of practical interest are known to be in BQP, but suspected to be outside P. Some prominent examples are:

  • Integer factorization (see Shor's algorithm)
  • Discrete logarithm
  • Simulation of quantum systems (see universal quantum simulator)
  • Computing the Jones polynomial at certain roots of unity

Read more about this topic:  BQP

Other articles related to "quantum, computation, quantum computation":

Quantum Computer - Operation
... List of unsolved problems in physics Is a universal quantum computer sufficient to efficiently simulate an arbitrary physical system? While a classical three ... In classical randomized computation, the system evolves according to the application of stochastic matrices, which preserve that the probabilities add up to one (i.e ... In quantum computation, on the other hand, allowed operations are unitary matrices, which are effectively rotations (they preserve that the sum of the ...
Artur Ekert - Research
... Artur Ekert's research extends over most aspects of information processing in quantum-mechanical systems, with a focus on quantum cryptography and quantum computation ... Building on the idea of quantum non-locality and Bell's inequalities he introduced entanglement-based quantum key distribution in his 1991 paper which generated a spate of new research that established a vigorously ... resulted in the proof-of-principle experimental quantum key distribution, introducing parametric down-conversion, phase encoding and quantum interferometry into the repertoire of cryptography ...
Anton Zeilinger - Work - Quantum Entanglement
... late 1980s, Anton Zeilinger became interested in quantum entanglement ... significant accomplishments and opened up the new fields of quantum teleportation, quantum information, quantum communication and quantum cryptography ... theorem (see Greenberger-Horne-Zeilinger state) is fundamental for quantum physics, as it provides the most succinct contradiction between local realism and the predictions of quantum mechanics ...

Famous quotes containing the words computation and/or quantum:

    I suppose that Paderewski can play superbly, if not quite at his best, while his thoughts wander to the other end of the world, or possibly busy themselves with a computation of the receipts as he gazes out across the auditorium. I know a great actor, a master technician, can let his thoughts play truant from the scene ...
    Minnie Maddern Fiske (1865–1932)

    A personality is an indefinite quantum of traits which is subject to constant flux, change, and growth from the birth of the individual in the world to his death. A character, on the other hand, is a fixed and definite quantum of traits which, though it may be interpreted with slight differences from age to age and actor to actor, is nevertheless in its essentials forever fixed.
    Hubert C. Heffner (1901–1985)