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å qubits

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

Improved Success Probability with Greater Circuit Depth for the Quantum Approximate Optimization Algorithm
Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem

Mer om den svenska kvantdatorsatsningen

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