År 2019, Google hävdade att det var den första att demonstrera en kvantdator som utför en beräkning utöver förmågan hos dagens mest kraftfulla superdatorer.

Men för det mesta, att skapa en kvantalgoritm som har en chans att slå en klassisk dator är en oavsiktlig process, Purdue University forskare säger. För att få mer vägledning till denna process och göra den mindre godtycklig, dessa forskare utvecklade en ny teori som så småningom kan leda till mer systematisk design av kvantalgoritmer.

Den nya teorin, beskrivs i en artikel publicerad i tidskriften Avancerad kvantteknologi , är det första kända försöket att bestämma vilka kvanttillstånd som kan skapas och bearbetas med ett acceptabelt antal kvantportar för att överträffa en klassisk algoritm.

Fysiker hänvisar till detta koncept med att ha rätt antal grindar för att kontrollera varje tillstånd som "komplexitet". Eftersom komplexiteten hos en kvantalgoritm är nära relaterad till komplexiteten hos kvanttillstånd som är involverade i algoritmen, teorin skulle därför kunna skapa ordning i sökandet efter kvantalgoritmer genom att karakterisera vilka kvanttillstånd som uppfyller dessa komplexitetskriterier.

En algoritm är en sekvens av steg för att utföra en beräkning. Algoritmen är vanligtvis implementerad på en krets.

I klassiska datorer, kretsar har grindar som växlar bitar till antingen 0- eller 1-tillstånd. En kvantdator förlitar sig istället på beräkningsenheter som kallas "qubits" som lagrar 0 och 1 tillstånd samtidigt i superposition, så att mer information kan behandlas.

Det som skulle göra en kvantdator snabbare än en klassisk dator är enklare informationsbehandling, kännetecknas av den enorma minskningen av antalet kvantgrindar i en kvantkrets jämfört med en klassisk krets.

I klassiska datorer ökar antalet grindar i kretsar exponentiellt med avseende på storleken på problemet av intresse. Denna exponentiella modell växer så häpnadsväckande snabbt att den blir fysiskt omöjlig att hantera för ens ett måttligt stort problem av intresse.

"Till exempel, även en liten proteinmolekyl kan innehålla hundratals elektroner. Om varje elektron bara kan ta två former, för att simulera 300 elektroner skulle det krävas 2300 klassiska tillstånd, vilket är mer än antalet av alla atomer i universum, sa Saber Kais, en professor vid Purdues avdelning för kemi och medlem av Purdue Quantum Science and Engineering Institute.

För kvantdatorer, det finns ett sätt för kvantportar att skala upp "polynomiellt" - snarare än bara exponentiellt som en klassisk dator - med storleken på problemet (som antalet elektroner i det sista exemplet). "Polynomial" betyder att det skulle behövas drastiskt färre steg (gates) för att bearbeta samma mängd information, gör en kvantalgoritm överlägsen en klassisk algoritm.

Forskare har hittills inte haft ett bra sätt att identifiera vilka kvanttillstånd som skulle kunna uppfylla detta villkor av polynomisk komplexitet.

"Det finns ett mycket stort sökutrymme för att hitta tillstånden och sekvensen av grindar som matchar i komplexitet för att skapa en användbar kvantalgoritm som kan utföra beräkningar snabbare än en klassisk algoritm, sa Kais, vars forskargrupp utvecklar kvantalgoritmer och metoder för kvantmaskininlärning.

Kais och Zixuan Hu, en Purdue postdoktorand, använde den nya teorin för att identifiera en stor grupp av kvanttillstånd med polynomkomplexitet. De visade också att dessa tillstånd kan dela en koefficientfunktion som kan användas för att bättre identifiera dem när man designar en kvantalgoritm.

"Med tanke på vilket kvanttillstånd som helst, vi kan nu designa en effektiv koefficientsamplingsprocedur för att avgöra om den tillhör klassen eller inte, " sa Hu.