Kvantecomputer

Fra Wikipedia, den frie encyklopædi
(Omdirigeret fra Qubit)
Gå til: navigation, søg

En kvantecomputer er et apparat, der kan beregne ved hjælp af kvantefysisk sammenfiltringer af kvantetilstande. For nylig (før dec. 2008) er små kvantecomputere blevet bygget. Mange myndigheder og militære organer som f.eks. NATO støtter universiteter og kvanteberegningsforskningscentre til at udvikle en computer til f.eks. kryptering.

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.

Historie[redigér | redigér wikikode]

Det var fysikeren Richard Feynman, som i 1982 foreslog at man skulle forsøge at simulere kvantemekaniske objekter i kvantemekanikken selv i form af en kvantecomputer. I 1985 offentliggjorde David Deutsch en banebrydende artikel med en beskrivelse af den universelle kvantecomputer. I 1994 beviste Peter Shor at man med en kvantecomputer kunne faktorisere tal eksponentielt hurtigere end på en klassisk computer[1].

Dette betød et væld af forskningsmidler til forskning i kvantecomputere og deres algoritmer, da langt størstedelen af alle public key krypteringssytemer baserer deres "ubrydelighed" på, at det er vanskeligt at faktorisere heltal eller at det er vanskeligt at løse den diskrete logaritme.

Opbygning[redigér | redigér wikikode]

Partikler i kvantemekanik er i stand til at være to steder på samme tid eller være i to kvantemekaniske tilstande på samme tid. Denne effekt er ofte beskrevet ved at anvende tankeeksperimentet Schrödingers kat, hvor en kat både kan være i live og død på samme tid. Denne mulighed til at være i flere kvantemekaniske tilstande samtidigt kaldes kvantemekanisk superposition.

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 sammenfiltrede 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 kvantefysisk sammenfiltrede kvantetilstandslagre, kan være fotoner, molekyler...

Funktionsmåde[redigér | redigér wikikode]

En klassisk computer med 3 bits kan kun lagre et mønster af 3 digitale et-taller eller nuller. Eksempelvis kan bittene på et tidspunkt have lagret "101".

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)        (a²+b²)
     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

Hvis der havde været n qubits, skulle tabellen have 2n rækker. For flere hundrede n, skulle der være flere rækker end der er atomer i det kendte univers. Omformuleret gælder det, at n antal qubits kan foretager 2n beregninger, hvilket matematisk er en eksponentiel sammenhæng. Det ses, at antallet af mulige beregninger fordobles for hver qubit.[2]

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 kvantecomputeren 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.

Referencer[redigér | redigér wikikode]

  1. A short introduction to quantum computation
  2. Engelhardt, Robin; Jensen, Hans Siggaard. "I selverkendelsens lys", ERGO: Naturvidenskabens filosofiske historie (1. udgave), Nørhaven Book A/S 2007, s. 281. ISBN 978-87-595-2866-2.

Se også[redigér | redigér wikikode]

Mere information[redigér | redigér wikikode]

  • Gode generelle referencer:
  • Termiske Ensembler
    • Overview of early developments, with links
    • De første to artikler skrevet om emnet: 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)
  • Anvendelse af kvantecomputere til at simulere kvantesystemer:
    • Feynman, R. P. "Simulating Physics with Computers" International Journal of Theoretical Physics, Vol. 21 (1982) pp. 467-488.
  • Kvantekryptografi:
    • Den første artikel skrevet om emnet: 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.
    • Den første artikel publiceret om emnet: 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.
    • En lang liste over artikler om kvantekryptografi, med kommentarer, finde på http://www.cs.mcgill.ca/~crepeau/CRYPTO/Biblio-QC.html
  • Universel kvantecomputer og Church-Turing princippet:
    • Deutsch, D. "Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer" Proc. Roy. Soc. Lond. A400 (1985) pp. 97-117.
  • Shor's faktoriseringsalgoritme:
    • 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)
    • IBMs annoncering af den første virkelige afvikling af algoritmen, som også giver historien om de forstekvantecomputere med 2, 3, 5, og 7 qubits. Publiceret i 19. december 2001 udgaven af Nature.
  • Kvantedatabase opslag:
    • 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.
  • Kvantecomputer simulatorer:
    • libquantum – Et library til kvantecomputer simulering
    • QCL – Simulation af kvanteberegning med et kvantecomputer sprog
    • Quantum::Entanglement – Kvanteberegningsmodul til Perl.
  • Kvantemekanisk fejlkorrektion:
    • 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.
  • Kvantemekanisk fejlforebyggelse:
    • D. A. Lidar, I.L. Chuang, K.B. Whaley, "Decoherence free subspaces for quantum computation", Phys. Rev. Lett 81, (1998) pp. 2594-2587
  • Løsning af NP-Complete og #P-Complete problemer:
    • 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 her eller her)

Eksterne henvisninger[redigér | redigér wikikode]