Kvantecomputer

Det formodes at hvis stor-skala kvantecomputere kan bygges, vil de være i stand til at løse visse datalogiske problemer hurtigere end enhver klassisk computer. Kvantecomputere er forskellige fra klassiske computere som f.eks. DNA-computere og computere baseret på transistorer og evt. transistorer baseret på kvantemekaniske effekter uden kvantefysisk sammenfiltring.

Table of contents

1 Kvantecomputeren - lidt historie 2 Kvantecomputerens opbygning 3 Hvordan kvantecomputere virker 4 Se også 5 Mere information 6 Eksterne henvisninger

Kvantecomputeren - lidt historie

Dette betød et væld af forskningsmidler til forskning i kvantecomputere og deres algoritmer, da langt størstedelen af kryptering RSA, DES..., baserer deres "ubrydelighed" på, at det er vanskeligt at faktorisere heltal.

Kvantecomputerens opbygning

En klassisk computers hukommelse er lavet af bits. Hver af bittene kan lagre en af to mulige tilstande, disse kan f.eks. fortolkes som "0" og "1", som de to tilstande af bekvemmelighedårsager kaldes, i næsten al faglitteratur. Computeren beregner ved at manipulere disse bits.

En kvantecomputer, derimod, har en mængde af qubits. En qubit kan lagre de "klassiske" to tilstande "0", "1" eller en superposition af de to tilstande. Det er forkert at sige at en qubit kan lagre to egentlige tilstande på samme tid - det den derimod kan, er at lagre en superposition af to vægtede tilstande. Kvantecomputeren beregner ved at manipulere disse qubits. Qubittene skal være kvantemekanisk entanglede for at virke som qubits.

En kvantecomputer kan realiseres ved at anvende enhver lille partikel, som kan have en separat skriv/læsbar kvantetilstandslager. Partiklerne, med de entanglede kvantetilstandslagre, kan være fotoner, molekyler...

Hvordan kvantecomputere virker

En kvantecomputer med 3 qubits kan faktisk lagre en superposition af 16 analoge tilstande/værdier, der med fordel kan modelleres som 8 komplekse tal. På et vilkårligt tidspunkt, kan qubittene lagre:

    Tilstand     Amplitude    Sandsynlighed
                  (a+ib)        (a2+b2)
     000       0,37 + i 0,04      0,14
     001       0,11 + i 0,18      0,04        
     010       0,09 + i 0,31      0,10
     011       0,30 + i 0,30      0,18
     100       0,35 + i 0,43      0,31
     101       0,40 + i 0,01      0,16
     110       0,09 + i 0,12      0,02
     111       0,15 + i 0,16      0,05
     ---------------------------------
      na           na             1,00 Sum

Den første søjle viser alle mulige tilstande for 3 bits. En klassisk computer kan kun lagre et af disse mønstre ad gangen. En kvantecomputer kan være i en superposition af alle 8 tilstande på samme tid. Den anden søjle viser en selvvalgt "amplitude" med en bestemt "retning" for hver af de 8 tilstande. Disse 8 komplekse tal er et øjebliksbillede af kvantekcomputeren på et givet tidspunkt. Ved en beregning bliver disse 8 tal ændret og interagerer med hinanden.

Dette at kvantecomputeren kan lagre og beregne på de 8 amplituder på samme tid, viser at kvantecomputeren kan lagre meget mere end en 3-bit klassisk computer.

Det skal dog bemærkes at de 8 amplituder ikke kan aflæses udenfor qubittene. Når en algoritme er slut, foretages en enkelt måling/aflæsning. Aflæsningen får kun et 3 bit mønster og i aflæsningsprocessen slettes de 8 amplituder. Aflæsningen returnerer et tilfældigt af de 8 mønstre med sandsynligheden fra tabellen. I eksemplet er der 14% chance for at det aflæste mønster er "000", 4% chance for at det aflæste mønster er "001" osv. Hver af de komplekse tal (a+bi) kaldes en amplitude og hver sandsynlighed (a²+b²) kaldes den kvadrerede amplitude, fordi de er lig |a+bi|². De 8 sandsynligheder summer til 1.

Se også

• Kvantecomputertidslinje
• Nanoteknologi

• Quantum computing is part of quantum information processing.

• Good general reference:
  • Centre for Quantum Computation, University of Oxford http://www.qubit.org

• Thermal Ensembles
  • Overview of early developments, with links
  • The first two papers ever written on this topic: D.G Cory, A.F. Fahmy, T.F. Havel, Proc. Nat. Acad. of Science, 94, 1634 (1997), and N. Gershenfeld and I. Chuang, Science, 275, pp. 350-356, 1997. (download)

• Using quantum computers to simulation quantum systems:
  • Feynman, R. P. "Simulating Physics with Computers" International Journal of Theoretical Physics, Vol. 21 (1982) pp. 467-488.

• Quantum cryptography:
  • The first paper ever written on this: Wiesner, S. "Conjugate Coding" SIGACT News, Vol. 15, 1983, pp. 78-88; Brassard, G. and Bennett, C.H., Proceedings of the IEEE International Conference on Computer Systems and Signal Processing, 1984, p. 175 Ekert, A. "Quantum Cryptography Based on Bell's Theorem" Physical Review Letters, Vol. 67 1991 pp. 661-663.
  • The first paper ever published on this: Bennett, C. H., Brassard, G., Breidbart, S. and Wiesner, S., "Quantum cryptography, or unforgeable subway tokens", Advances in Cryptology: Proceedings of Crypto 82, August 1982, Plenum Press, pp. 267 - 275.
  • A listing of a huge number of quantum cryptography papers, with some discussion of them, is at http://www.cs.mcgill.ca/~crepeau/CRYPTO/Biblio-QC.html

• Universal quantum computer and the Church-Turing thesis:
  • Deutsch, D. "Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer" Proc. Roy. Soc. Lond. A400 (1985) pp. 97-117.

• Shor's factoring algorithm:
  • Shor, P. "Algorithms for quantum computation: discrete logarithms and factoring" Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 20-22 Nov. 1994, IEEE Comput. Soc. Press (1994) pp. 124-134.
  • John-Pierre Seifert, "Using fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation," (download)
  • IBM's announcement of the first actual execution of the algorithm, which also gives the history of the first quantum computers with 2, 3, 5, and 7 qubits. Published in the December 19, 2001 issue of Nature.

• Quantum database search:
  • Grover, L. K. "A Fast Quantum Mechanical Algorithm for Database Search" Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, (1996) pp. 212-219.

• Quantum computer simulators:
  • libquantum - A library for quantum computer simulation
  • QCL - Simulation of quantum computing with a quantum computing language
  • Quantum::Entanglement - Quantum computation module for Perl.

• Quantum error correction:
  • Shor, P. W. "Scheme for reducing decoherence in quantum computer memory" Phys. Rev. A 52,(1995) pp. 2493-2496.
  • Calderbank, A. R. and Shor, P.W. "Good quantum error-correcting codes exist" Phys. Rev. A 54, (1996) pp. 1098-1106.
  • Shor. P. W. "Fault-tolerant quantum computation" Proc. 37nd Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, (1996) pp. 56-65.

• Quantum error avoidance:
  • D. A. Lidar, I.L. Chuang, K.B. Whaley, "Decoherence free subspaces for quantum computation", Phys. Rev. Lett 81, (1998) pp. 2594-2587

• Solving NP-Complete and #P-Complete problems:
  • Daniel S. Abrams (1), Seth Lloyd (2) ( (1) Dept. of Physics, MIT, (2) Dept. of Mechanical Engineering, MIT), 1988, "Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems"(download)
  • Phil Gossett, 1988, "NP in BQP with Nonlinearity", (download)
  • Yu Shi, 2001, "Entanglement Between Bose-Einstein Condensates", Int. J. Mod. Phys. B, Vol. 15 (Sept 10, 2001) 3007-3030. (download here or here)

• For the interested non-expert:
  • West, J.(2000). The Quantum Computer - An Introduction. (Easy to understand explanation of quantum computing. )

• Number 570 #4, December 21, 2001, AIP: A Quantum Computer Has Factored the Number 15
• EETIMES 17-1-2001: Optical components proposed for viable quantum computer, ETDN mirror Citat: "...SANTA FE, N.M. - Researchers at Los Alamos National Laboratories claim to have originated a blueprint for room-temperature quantum computers using such optical components as beam splitters, phase shifters and photodetectors...."

• Laser Focus World 18-3-2001: Quantum information processing may no longer face entanglement problems
• CNN May 17, 2001 Quantum-light processor may thrash supercomputers Citat: "...Mimicking quantum mechanics and using laser technology, scientists have constructed the prototype of a lightning-fast computer that could render conventional supercomputers obsolete..."
• December 19, 2001, IBM's Test-Tube Quantum Computer Makes History, First demonstration of Shor's historic factoring algorithm
• 15-Feb-2002 First Step To Noiseless Qubit For Quantum Computers
• December 10, 1997 Science fact: Scientists achieve 'Star Trek'-like feat Citat: "... If the notion of entanglement leaves your head spinning, don't feel bad. Zeilinger said he doesn't understand how it works either. "And you can quote me on that," he said. Prof. Anton Zeilinger ..."
• UniSci, 26-Nov-2001 Holograms Based On 'Spooky Action At A Distance' Citat: "...It's the interference of the possible paths that encodes the holographic image of the hidden object, which is very spooky indeed. ..."
• Physics Web, 17 Mar 2000, Quantum leap for entanglement Citat: "...Entanglement is one of the most mysterious and fundamental properties of quantum mechanics. When two or more particles are "entangled", the wavefunction describing them cannot be factorized into a product of single-particle wavefunctions. This means that a measurement on one particle will immediately influence the state of the other particles in the entangled system. A group of physicists in the US has now "entangled" four particles for the first time (Nature 404 256)..."

Denne artikel er fra Wikipedia. Læs artiklen hos Wikipedia.