Løsning af problemer på et kvanteskakbræt

Fysikere ved universitetet i Innsbruck foreslår en ny model, der kan demonstrere kvantecomputers overlegenhed over klassiske supercomputere til løsning af optimeringsproblemer. I en nylig artikel, de demonstrerer, at kun et par kvantepartikler ville være tilstrækkelige til at løse det matematisk vanskelige N-dronningsproblem i skak selv for store skakbrætter.

Dronningsproblemet er en matematisk opgave, som allerede havde den store matematiker Carl Friedrich Gauss besat, men som han overraskende ikke fandt den rigtige løsning til. Udfordringen her er, hvordan man arrangerer otte dronninger på et klassisk skakbræt med 8 x 8 firkanter, så ingen to dronninger truer hinanden. Matematisk, det er relativt let at afgøre, at der er 92 forskellige måder at arrangere dronningerne på. På et skakbræt med 25 x 25 firkanter er der allerede mere end 2 milliarder muligheder. Beregningen af ​​dette nummer alene tog i alt 53 års CPU -tid.

Opgaven bliver endnu vanskeligere, hvis nogle dronninger allerede er på banen, og visse diagonaler muligvis ikke er besat. For nylig har det vist sig, at med disse yderligere begrænsninger kan problemet med 21 dronninger ikke længere løses ved hjælp af klassiske matematiske algoritmer på en rimelig tid. "Jeg stødte tilfældigt på dette emne og troede, at kvantefysik virkelig kunne udspille fordelene her, "siger Wolfgang Lechner fra Institut for Teoretisk Fysik ved University of Innsbruck og Institute of Quantum Optics and Quantum Information ved det østrigske videnskabsakademi. Sammen med Helmut Ritsch og ph.d. -studerende Valentin Torggler og Philipp Aumann, Lechner udviklede et kvanteskakbræt, hvor dronningens puslespil kunne løses eksperimentelt ved hjælp af kvantefysik.

Fra atomer til skakdronninger

"Et optisk gitter af laserstråler, hvori individuelle atomer er placeret, kan bruges som skakbræt, "forklarer Helmut Ritsch, som også er medlem af Institut for Teoretisk Fysik i Innsbruck. "Ved at justere interaktionen mellem atomerne, vi kan lave skakdronninger ud af atomerne, der opfører sig efter skakreglerne, dvs. undgå hinanden i alle retninger af spillebrættet. "Denne frastødning af partiklerne genereres ved hjælp af lasere, som påføres langs bevægelsesretningerne. Via en optisk resonator - to spejle over og under det optiske gitter - intensiveres denne interaktion yderligere og bliver dermed effektiv over meget større afstande.

"Man kunne også spille dette spil med tilsvarende frastødende billardbolde, "siger Ritsch." Men fordi der er så mange muligheder, det ville tage meget, meget lang tid. Det er derfor afgørende, at atomerne afkøles meget kraftigt, og at deres kvanteegenskaber træder i kraft. Fordi de så opfører sig som bølger og kan teste mange muligheder på samme tid. Så bliver det hurtigt tydeligt, om der er en gyldig løsning efter skakregler for de givne betingelser. "

Quantum supremacy i horisonten

Svaret på spørgsmålet, om der er en løsning under de givne begrænsninger, kan meget let aflæses fra lyset, der udsendes af resonatoren. Men det specifikke arrangement af atomdronningerne kunne kun bestemmes ved atommikroskopi, en metode, der for nylig blev anvendt med succes i beslægtede eksperimenter.

Simuleringer på klassiske computere tyder kraftigt på, at eksperimentet designet af Innsbruck -teoretikerne ville føre til et resultat meget hurtigere end nogen matematisk algoritme på en klassisk computer kunne. "Dette ville gøre det muligt for første gang klart at bevise kvantecomputers overlegenhed til beregning af visse optimeringsproblemer, "opsummerer Wolfgang Lechner." Kontrol af et par dusin atomer er allerede standard praksis i laboratoriet, derfor kan implementeringen af ​​denne idé snart blive til virkelighed. "