Sunnyvale, Kalifornien – 26 oktober 2022 – NTT Research meddelade att en forskare från dess Lab för kryptografi och informationssäkerhet (CIS). och en kollega från NTT Social Informatics Laboratories (SIL) har skrivit ett banbrytande dokument om kvantfördelar. Uppsatsen valdes ut för att presenteras vid det årliga IEEE Symposium on Foundations of Computer Science (FOCS), som äger rum 31 oktober–nov. 3 i Denver.
Medförfattarna till tidningen, med titeln "Verifierbar Quantum Advantage utan struktur,” är Dr. Takashi Yamakawa, framstående forskare vid NTT SIL och Dr. Mark Zhandry, senior forskare i NTT-forskning CIS Lab. Arbetet utfördes delvis vid Princeton University, där Dr Yamakawa var gästforskare och Dr Zhandry också fungerar som biträdande professor i datavetenskap.
Ämnet kvantfördelar (eller kvanthastighet) relaterar till de typer av problem som kvantdatorer kan lösa snabbare än klassiska eller icke-kvantdatorer och hur mycket snabbare de är. Problemen i fråga beskrivs vanligen som icke-deterministisk polynom-tidsklass (NP). Hur stor fördel kan variera i hög grad. En kvantdator kanske kan lösa ett visst problem på en minut eller en sekund som tar en klassisk dator i veckan, eller möjligen en outgrundligt exponentiell tid. I den här artikeln tar författarna upp utmaningen att verifiera denna överlägsenhet och göra det effektivt. Hittills har demonstrationer av kvantfördelar inneburit betydande "struktur" eller kommunikation fram och tillbaka mellan två eller flera parter. Genombrottet för Yamakawa och Zhandry-papperet är att demonstrera ett NP-problem där verifiering är möjlig utan struktur.
"Detta är första gången som vi har sett en exponentiell kvanthastighet för ett NP-sökproblem, som bara kräver ett slumpmässigt orakel", säger University of Texas i Austin professor i datavetenskap Dr. Scott Aaronson, som kommenterade en tidig version av uppsatsen under en workshop den 13 juni 2022 på Simons Institute for the Theory of Computing. Genom att bara kräva ett slumpmässigt orakel, dvs en teoretisk svart låda som genererar slumpmässiga svar på varje fråga, byggde Yamakawa och Zhandry sitt problem på ostrukturerade beräkningsantaganden. Som sådan ligger deras problem närmare i linje med envägsfunktioner istället för strukturerade, som de som finns i kryptografi med publik nyckel. Den envägsanpassningen underlättar effektiv verifiering.
"Det är spännande att se NTT-anslutna kryptografer samarbeta om forskning som återigen förtjänar etiketten "genombrott", särskilt i en artikel som berikar vår förståelse av kvantberäkning, ett annat fokusområde för oss på NTT Research, säger Kazuhiro Gomi , NTT Research VD och koncernchef. "Grattis och lyckönskningar till alla deltagare i denna prestigefyllda IEEE-konferens."
NP-sökproblemet som Yamakawa och Zhandry skapade var ett två-i-ett-problem som innebär att man hittade 1) en n-symbolsträng som är ett kodord för en given felkorrigeringskod, och 2) en n-symbolsträng där varje symbolen mappas till noll under det slumpmässiga oraklet. Varje problem separat är enkelt. Men att hitta en enda sträng av symboler som både är ett kodord och mappar till noll är mycket svårare, åtminstone klassiskt. "Om du är kvant kan du lösa detta i polynomtid," sa Dr Zhandry, "men om du är klassisk, åtminstone om du är i den här svarta lådan, behöver du exponentiell tid." Å andra sidan, givet en potentiell lösning, är det enkelt att verifiera den genom att kontrollera att den löser vart och ett av de två problemen separat. Observera att, som det anstår ett papper för FOCS, är detta arbete grundläggande eller grundläggande. Som påpekades i Dr. Aaronsons tal vid Simons Institute (diskuterat i denna NTT Research bloggartikel), faller Yamakawa-Zhandry-argumentet i en klass av hastighetshöjningar som lätt kan kontrolleras matematiskt, men inte demonstreras praktiskt av en verklig kvantdator någon gång snart. Utöver det banbrytande verifieringsschemat pekar artikeln också på något nytt när det gäller omfattningen av kvanthastigheten.
"Innan vårt arbete hade vi exempel på kvantfördelar för NP-problem, som factoring eller, i den svarta lådan, periodfynd. Men det visar sig att kvantalgoritmen som ligger till grund för alla dessa exempel i grund och botten var periodfynd – även om det ofta var icke-trivialt att visa hur man tillämpar periodhittande på dessa exempel, säger Dr. Zhandry. "Vårt papper visar att det finns åtminstone ett andra fall. Du kan optimistiskt tolka det som att det finns hopp om att kvantfördelen är mer utbredd än vi kanske tidigare trott."
Sponsrad av IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF), är FOCS en ledande konferens inom området teoretisk datavetenskap. Inbjudan till papper för FOCS 2022, den 63:e årliga sammankomsten, angav kvantberäkning som ett av 17 allmänna intresseområden. Yamakawa-Zhandry-tidningen är planerad att presenteras den 31 oktober 2022 kl. 10:15 MT. För att lära dig mer om och registrera dig för detta evenemang, besök FOCS 2022 webbsajt.
