Fysiker vid universitetet i Innsbruck föreslår en ny modell som kan visa kvantdatorernas överlägsenhet över klassiska superdatorer när det gäller att lösa optimeringsproblem. I en ny tidning, de visar att bara några kvantpartiklar skulle räcka för att lösa det matematiskt svåra N-drottningsproblemet i schack även för stora schackbrädor.

Drottningproblemet är en matematisk uppgift, som redan hade den store matematikern Carl Friedrich Gauss ockuperat, men som han överraskande nog inte hittade den rätta lösningen för. Utmaningen här är hur man arrangerar åtta damer på ett klassiskt schackbräde med 8 x 8 rutor så att inte två damer hotar varandra. Matematiskt, det är relativt lätt att avgöra att det finns 92 olika sätt att ordna damerna. På ett schackbräde med 25 x 25 rutor finns det redan mer än 2 miljarder möjligheter. Beräkningen av detta antal ensam tog totalt 53 års CPU -tid.

Uppgiften blir ännu svårare om några damer redan är på planen och vissa diagonaler kanske inte är upptagna. Nyligen har det visat sig att med dessa ytterligare begränsningar kan problemet med 21 drottningar inte längre lösas med klassiska matematiska algoritmer inom rimlig tid. "Jag stötte på det här ämnet av en slump och trodde att kvantfysiken verkligen kunde spela ut sina fördelar här, "säger Wolfgang Lechner från institutionen för teoretisk fysik vid universitetet i Innsbruck och institutet för kvantoptik och kvantinformation vid den österrikiska vetenskapsakademien. Tillsammans med Helmut Ritsch och doktorander Valentin Torggler och Philipp Aumann, Lechner utvecklade ett kvantschackbräde där drottningspusslet kunde lösas experimentellt med hjälp av kvantfysiken.

Från atomer till schackdrottningar

"Ett optiskt gitter av laserstrålar i vilket enskilda atomer placeras kan användas som ett schackbräde, " förklarar Helmut Ritsch, som också är medlem av institutionen för teoretisk fysik i Innsbruck. "Genom att justera interaktionen mellan atomerna, vi kan göra schackdrottningar av atomerna, som beter sig enligt schackreglerna, d.v.s. undvik varandra i alla riktningar på spelplanen." Denna repulsion av partiklarna genereras med hjälp av lasrar, som appliceras längs rörelseriktningarna. Via en optisk resonator – två speglar över och under det optiska gittret – intensifieras denna interaktion ytterligare och blir därmed effektiv över mycket större avstånd.

"Man kan också spela det här spelet med motsvarande motbjudande biljardbollar, " säger Ritsch. "Men eftersom det finns så många möjligheter, det skulle ta en mycket, mycket lång tid. Det är därför avgörande att atomerna kyls ner mycket kraftigt och att deras kvantegenskaper träder i kraft. För de beter sig då som vågor och kan testa många möjligheter samtidigt. Då visar det sig snabbt om det finns en giltig lösning enligt schackregler för de givna förutsättningarna."

Kvantöverlägsenhet vid horisonten

Svaret på frågan om det finns en lösning under de givna restriktionerna kan avläsas mycket enkelt från ljuset från resonatorn. Men det specifika arrangemanget av atomdrottningarna kunde bara bestämmas med atommikroskopi, en metod som nyligen tillämpats framgångsrikt i relaterade experiment.

Simuleringar på klassiska datorer tyder starkt på att experimentet designat av Innsbruck-teoretiker skulle leda till ett resultat mycket snabbare än någon matematisk algoritm på en klassisk dator skulle kunna. "Detta skulle göra det möjligt för första gången att tydligt bevisa kvantdatorernas överlägsenhet för beräkning av vissa optimeringsproblem, " sammanfattar Wolfgang Lechner. "Kontrollen av några dussin atomer är redan standardpraxis i laboratoriet, vilket är anledningen till att genomförandet av denna idé snart kan bli verklighet."