Ett team av forskare från Australien och Storbritannien har utvecklat en ny teoretisk ram för att identifiera beräkningar som upptar "kvantgränsen" - gränsen vid vilken problem blir omöjliga för dagens datorer och bara kan lösas med en kvantdator. Viktigt, de visar att dessa beräkningar kan utföras med kort sikt, mellanliggande, kvantdatorer.

"Tills nyligen har det varit svårt att definitivt säga när kvantdatorer kan överträffa klassiska datorer, "sade professor Michael Bremner, Chefsutredare vid Center for Quantum Computation and Communication Technology och grundare av UTS Center for Quantum Software and Information (UTS:QSI).

"Den stora utmaningen för kvantkomplexitetsteoretiker under det senaste decenniet har varit att hitta starkare bevis för existensen av kvantgränsen, och sedan för att identifiera var det bor. Vi får nu en känsla av detta, och börjar förstå de resurser som krävs för att korsa gränsen för att lösa problem som dagens datorer inte kan. "

Teamet har identifierat kvantberäkningar som kräver de minst kända fysiska resurser som krävs för att gå utöver klassiska dators kapacitet, betydande på grund av de tekniska utmaningar som är förknippade med att skala upp kvantdatorer.

Prof Bremner sa att resultatet också indikerar att full fel-tolerans inte kan krävas för att överträffa klassiska datorer. "Hittills, det har varit allmänt accepterat att felkorrigering skulle vara en nödvändig komponent i framtida kvantdatorer, men ingen har ännu kunnat uppnå detta i en meningsfull skala, sa Bremner.

"Vårt arbete visar att även om en viss nivå av felreducering behövs för att passera kvantgränsen, vi kanske kan överträffa klassiska datorer utan den extra designkomplexiteten med full feltolerans, " han sa.

Dr Ashley Montanaro från University of Bristol samarbetade med Bremner för att utveckla ramverket.

"Vi började med målet att definiera de minsta resurser som krävs för att bygga en postklassisk kvantdator, men fann sedan att vår modell klassiskt kunde simuleras med en liten mängd brus, eller fysisk ofullkomlighet, sa Montanaro.

"Förhoppningen bland forskare hade alltid varit att om mängden brus i ett kvantsystem var tillräckligt liten så skulle det fortfarande vara överlägset en klassisk dator, men vi har nu visat att detta förmodligen inte är fallet, åtminstone för denna speciella beräkningsklass, " han sa.

"Vi insåg då att det är möjligt att använda en klassisk kodning på en kvantkrets för att övervinna "brus" på ett mycket enklare sätt för att mildra dessa fel. Effektiviteten av detta tillvägagångssätt var överraskande. Vad det antyder är att vi kan använda sådana strukturer att utveckla nya kvantalgoritmer på ett sätt som direkt kan undvika vissa typer av fel. "

"Detta är ett resultat som kan leda till användbara" mellanliggande "kvantdatorer på medellång sikt, medan vi fortsätter att sträva efter målet om en universell kvantdator i full skala. "