Liten kvantdator har löst verkligt optimeringsproblem
Kvantdatorer har redan lyckats överträffa vanliga datorer i att lösa vissa uppgifter – dessvärre totalt onyttiga sådana. Nästa milstolpe är att få dem att uträtta användbara saker. Forskare på Chalmers har nu visat att de med sin lilla, men välfungerande kvantdator kan lösa en liten del av ett verkligt logistikproblem.
Intresset för att bygga kvantdatorer har tagit ordentlig fart de senaste åren och det arbetas febrilt på många håll i världen. År 2019 gjorde Googles forskarlag ett stort genombrott när deras kvantdator lyckades lösa en uppgift långt snabbare än världens bästa superdator. Baksidan är att den lösta uppgiften inte har någon som helst praktisk användning – den valdes enbart för att den bedömdes vara enkel att lösa för en kvantdator och samtidigt mycket svår för en konventionell dator.
Därför är en viktig uppgift inom kvantdatorutecklingen nu att hitta användbara, relevanta problem som ligger utom räckhåll för vanliga datorer, men som en förhållandevis liten kvantdator skulle kunna lösa.
– Vi vill vara säkra på att kvantdatorn vi utvecklar tidigt kan användas för att lösa relevanta problem. Därför arbetar vi tätt ihop med företag i industrin, säger teoretiska fysikern Giulia Ferrini, en av ledarna för Chalmers kvantdatorprojekt som startade år 2018.
Giulia Ferrini har, tillsammans med Göran Johansson, lett det teoretiska arbetet när ett lag chalmersforskare, däribland en industridoktorand från flyglogistikföretaget Jeppesen, nu visat att en kvantdator kan lösa en del av ett verkligt problem inom flygbranschen.
Algoritmen bevisad på två kvantbitar
För alla större flygbolag är schemaläggning en utmaning. Att avgöra vilket flygplan som ska flyga vilken rutt är ett optimeringsproblem som mycket snabbt växer i omfång och svårighet när antalet destinationer och flygplan ökar.
Forskare hoppas att kvantdatorer kommer att kunna hantera sådana problem mycket bättre än dagens datorer. Kvantdatorns grundläggande byggsten – kvantbiten – bygger på helt andra principer än byggstenarna i dagens datorer, vilket gör att den har möjlighet att hantera enorma mängder information med relativt få kvantbitar.
På grund av sin annorlunda uppbyggnad måste dock kvantdatorer programmeras på helt andra sätt än vanliga datorer. En föreslagen algoritm som tros kunna bli användbar på tidiga kvantdatorer är den så kallade Quantum Approximate Optimization Algorithm (QAOA).
Chalmersforskarna har nu framgångsrikt kört nämnda algoritm på sin kvantdator – en processor med två kvantbitar – och lyckats lösa problemet med att tilldela flygplan rutter. I denna första demonstration kunde resultatet enkelt verifieras eftersom skalan var mycket liten – problemet involverade endast två flygplan.
Potential att hantera många flygplan
Med bedriften var de först att visa att QAOA-algoritmen fungerar i praktiken för att lösa problemet med att tilldela flygplan rutter. De lyckades också köra algoritmen en nivå längre än vad någon gjort förut, en prestation som kräver mycket bra hårdvara och exakt styrning.
– Vi har visat att vi har förmågan att lösa verkliga problem på vår kvantprocessor. Vi har än så länge få kvantbitar, men de fungerar bra. Vår plan har varit att först få allt att fungera väldigt bra i liten skala, innan vi skalar upp, säger experimentalisten Jonas Bylander som är en av ledarna av Chalmers kvantdatorbygge.
Teoretikerna i forskarlaget har också simulerat att lösa samma optimeringsproblem för upp till 278 flygplan, vilket skulle kräva en kvantdator med 25 kvantbitar.
– Resultaten blev fortsatt bra när vi skalade upp. Det indikerar att QAOA-algoritmen har potential att lösa den här typen av problem även i större skala, säger Giulia Ferrini.
För att överträffa dagens bästa datorer krävs dock mycket större kvantdatorer än så. Forskarna på Chalmers har nu påbörjat uppskalningen och arbetar för närvarande med fem kvantbitar. Planen är att under år 2021 komma upp i minst 20 kvantbitar utan att göra avkall på prestandan.
Forskningsresultaten har publicerats i två artiklar i Physical Review Applied:
Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem
Mer om: Jakten på en svensk kvantdator
Forskningen ingår i Wallenberg Centre for Quantum Technology (WACQT) som är en tolvårig miljardsatsning med två huvudsyften: att utveckla svensk kompetens inom kvantteknologi och att bygga en fungerande kvantdator med minst hundra kvantbitar. Forskningscentret finansieras huvudsakligen av Knut och Alice Wallenbergs stiftelse. Läs vidare:
Nu startar bygget av en svensk kvantdator (ursprungligt pressmeddelande från 2017)
Discover quantum technology (populärvetenskaplig introduktion till kvantteknologi)
Quantum computing (populärvetenskaplig introduktion till kvantdatorer)
Wallenberg Centre for Quantum Technology (WACQT)
Research in quantum computing and simulation (om kvantdatorforskningen inom WACQT)
Kontaktpersoner:
Giulia Ferrini, forskarassistent i tillämpad kvantfysik, Chalmers, ferrini@chalmers.se, 031-772 64 17 (talar engelska och italienska)
Jonas Bylander, docent i kvantteknologi, Chalmers, jonas.bylander@chalmers.se, 031-772 51 32 (helst eftermiddagar)
Christian Borg
Pressansvarig
031-772 3395
christian.borg@chalmers.se
________________
Chalmers tekniska högskola i Göteborg forskar och utbildar inom teknik och naturvetenskap på hög internationell nivå. Universitetet har 3 100 anställda, 10 000 studenter och utbildar ingenjörer, arkitekter och sjöbefäl.
Med vetenskaplig excellens som grund utvecklar Chalmers kompetens och tekniska lösningar för en hållbar värld. Genom globalt engagemang och entreprenörsanda skapar vi innovationskraft, i nära samarbete med övriga samhället. EU:s största forskningsinitiativ – Graphene Flagship – leds av Chalmers, liksom bygget av en svensk kvantdator.
Chalmers grundades 1829 och har än idag samma motto: Avancez – framåt.
