Kvantecomputer kan løse matematikernes middagsselskabsproblem

En ny computer har beregnet løsninger på et af matematikkens mere drilske problemer: middagsselskabsproblemet.

Computerberegningerne har ikke foreløbig givet andre svar, end de allerede kendte. Men da forskerne bag hævder, at den anvendte computer er en kvantecomputer, diskuterer eksperter ivrigt, om dette er korrekt.

Er det virkelig tilfældet, vil det måske være muligt med endnu kraftigere computer af samme type, der forventes klar i 2015, at løse middagsselskabsproblemer, der ikke kendes løsninger til i dag.

I givet fald vil der være tale om både et matematisk gennembrud og et gennembrud for en særlig form for kvantecomputere, der kaldes adiabatiske kvantecomputere.

Adiabatiske kvantecomputere

Før vi vender tilbage til middagsselskabsproblemet en kort gennemgang af de forskelige typer af kvantecomputere.

Kvantecomputere kan opdeles i to forskelige grupper.

I kredsløbsorienterede kvantecomputere udfører man beregninger med logiske operationer – i princippet efter samme metoder som i en klassisk computer.

Operationerne udføres blot med kvantebits (qubits), og det er den endelige tilstand af disse qubits, der giver løsningen. Qubits er karakteriseret ved at de samtidig er både ’0’ og ’1’, på samme måde som Schrödingers kat er både død og levende på samme tid.

I en adiabatisk kvantecomputer lader man et kvantesystem udvikle sig fra en kendt begyndelsestilstand til en sluttilstand under påvirkning af eksterne parametre. Hvis vekselvirkningerne sker langsomt, dvs. adiabatisk, vil sluttilstanden give det ønskede svar.

De kredsløbsorienterede kvantecomputere er meget følsomme over for støj og uperfektheder, der ødelægger kvanteberegningerne. Derfor har man kun lavet meget små kvantecomputere af denne type hidtil. En adiabatisk kvantecomputer er mere tolerant over for disse.

Til gengæld kan en adiabatisk kvantecomputer ikke udføre alle de typer beregninger, der kan udføres med en kredsløbsorienteret kvantecomputer.

Ramsey viste der var en løsning

Tilbage til middagsselskabsproblemet.

Her er opgaven: Du skal invitere et antal personer til et middagsselskab under den betingelse, at selskabet enten skal indeholde mindst en gruppe på m personer, som alle kender hinanden på forhånd, eller en gruppe på mindst n personer, hvoraf ingen kender hinanden på forhånd. Du ved ikke på forhånd om de personer, du vil invitere, er bekendte med hinanden eller ej.

Hvor få personer kan du nøjes med at invitere, for at den ene eller den anden betingelse med garanti er opfyldt – uanset hvem der inviteres?

Den britiske matematiker Frank Ramsey, der døde kun 26 år gammel i 1930 af gulsot, viste i 1928, at der for alle m og n findes et sådant minimumstal.

Beviset herfor blev offentliggjort i Proceedings of London Mathematical Society i 1930 i artiklen ’On a Problem of Formal Logic’. Tallet kaldes nu Ramsey-tallet R(m,n).

Problemet er blot, at dette tal er meget svært at udregne.

Det vides dog, at R(3,3) = 6 og R(m,2)=m

Men om R(5,5) vides det kun, at det er større end eller lig 43 og mindre end eller lig 49, tilsvarende ligger R(6,6) mellem tallene 102 og 165 (tallene iberegnet).

I en artikel i Physical Review Letters beskriver Zhengbing Bian og to øvrige forskere fra canadiske D-Wave Systems nu sammen med to uafhængige universitetsforskere, at de har udregnet R(3,3), R(4,4), R(6,2) og R(8,2) med firmaets adiabatiske kvantecomputer.

Beregningerne tog omkring et par millisekunder. Forskerne oplyser, at beregningen af R(8,2) udnyttede i alt 84 qubit.

De skriver afslutningsvis i deres artikel: 'Det er efter vores bedste viden den største eksperimentelle implementering af en videnskabelig meningsfuld adiabatisk evolutions-algoritme'.

Men er det en kvantecomputer?

Lige siden D-wave lancerede første udgave af deres kvantecomputer i 2007 har eksperter ivrigt diskuteret om den rent faktisk udførte kvanteberegninger.

I april i år konkludere en række uafhængige forskere dog i en videnskabelig artikel: 'Vores eksperimenter viser, at en form for kvanteberegninger med mere end 100 qubit finder sted i D-Wave One.'

Læs også: Uafhængige forskere blåstempler kontroversiel kvantecomputer

Den nye artikel om beregningen af Ramsey-tal mødes dog alligevel med skepsis.

Graeme Smith og John Smolin fra IBM TJ Watson Research Center i Yorktown Heights, New York skriver på physics.org, at der efter deres opfattelse er et problem med fortolkningen af resultaterne i artiklen fra D-Wave-forskerne.

Smith og Smolin påpeger, at der er anvendt en maskine med en meget høj dekohærens.

Det antyder, at maskinen fungerer efter klassiske metoder, og der ikke kan forventes meget hurtigere beregninger, end det er mulig med traditionelle klassiske computere, som er optimeret til forskellige beregningsopgaver.

Det kan derfor ikke anses for bevist, at der er tale om kvanteberegninger, konkluderer Smith og Smolin.

De to IBM-forskere er i øvrigt heller ikke overbevist om rigtigheden af konklusionen i artiklen nævnt ovenfor, der beskrev, at der var tale om kvanteberegninger med D-Wave computeren i andre tilfælde.

Ny computer kan afgøre sagen

Colin Williams, der er direktør for forretningsudvikling og strategiske partnerskaber hos D-Wave, siger dog til Physics World, at der ikke er tvivl om, at der er tale om kvanteberegninger.

Han tilføjer, at med en ny større maskine med 2.048 qubit, som efter planen bliver færdig 2015, vil der være en mulighed for, at man kan beregne et hidtil ukendt Ramsey-tal.

Et sådant nyt Ramsey-tal vil ikke kun være interessant for værter for middagsselskaber, det kan også afgøre, om D-Wave computeren rent faktisk er en kvantecomputer eller en ’blot’ en variant af en klassisk computer.

sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først

"Inviterer du seks personer til middagsselskab – helt vikårligt – vil der enten være en gruppe på tre personer til stede, der alle kender hinanden, eller mindst tre personer, som ikke kender nogen andre.

Øh, hvad så med 3 par?

  • 1
  • 0

er der ikke lidt molbo over det? skal man ikke huske at tælle sig selv med... eller har matematikere for vane at invitere til fest uden selv at dukke op? (ikke at det vil undre nogen)

  • 1
  • 1
Bidrag med din viden – log ind og deltag i debatten