Az Egyesült Államok tudósai kitalálták, hogyan lehet kipróbálni azokat a problémákat, amelyek az emberek számára még nem állnak rendelkezésre. A tudósok ugyanazt a módszert használják, mint a rendõrségi nyomozók, miközben párbeszédet folytatnak a számítógépekkel e problémák megoldása érdekében. "Összetévesztik" a kihallgatást, két autót külön kérdeznek ki, stb. Még kvantummechanikát is használnak.
Képzelje el: egy ember hozzád jön és azt mondja, hogy van egy korbácsolója, és hogy ez a korbács felfedi a világegyetem érthetetlen titkait. Érdekes vagy, de alig hiszel el neki. Minden bizonnyal meg kell győződnie arról, hogy az elválasztó igazat mond, és ehhez valamilyen módra vagy módszerre van szüksége.
Ez a számítástechnika egyik fő problémájának lényege. Egyes feladatokat túl nehéz elvégezni ésszerű időn belül. De megoldásukat könnyű ellenőrizni. Ezért a számítógépes tudósok tudni akarják: Mennyire összetett lehet egy olyan probléma, amely ellenőrizhető megoldással rendelkezik?
Kiderül, hogy a válasz: hihetetlenül bonyolult lehet.
Két informatikus tudósító áprilisban kiadott egy kutatási papírt, amely megsokszorozta a nehéz megoldandó, de könnyen ellenőrizhető problémák számát. Leírták a szinte hihetetlenül összetett problémák megoldásának tesztelésére szolgáló módszert. „Őrültnek hangzik” - mondta Thomas Vidick, a kaliforniai technológiai intézet számítógépes tudósa, aki nem vett részt ebben az új munkában.
A kutatás olyan kvantumszámítógépekre vonatkozik, amelyek a kvantummechanika ellentmondásos szabályai szerint végeznek számításokat. A kvantum számítógépek csak most kezdtek megjelenni, de a jövőben forradalmasíthatják a számítást és a számítást.
Valójában az elvégzett új tudományos kutatás lehetőséget ad nekünk, hogy befolyásoljuk a cikk elején ismertetett elválasztót. Még ha ígéri is, hogy válaszokat ad azoknak a problémáknak, amelyeket mi magunk nem képesek megoldani, akkor még ebben a látszólag reménytelen helyzetben is megvan a módja annak, hogy kipróbáljuk a fogorvost, és megbizonyosodjunk arról, hogy ő igazat mond (vagy megtéveszt).
Promóciós videó:
AZ EGYETEM haláláig
Ha egy problémát nehéz megoldani, de könnyű ellenőrizni, a megoldás megtalálása sok időt vesz igénybe, de az adott megoldás helyességének ellenőrzése nem az.
Íme egy példa. Képzelje el, hogy kap egy rajzot. Ez egy olyan pontok (csúcsok) gyűjteménye, amelyeket vonalak (élek) kapcsolnak össze. Azt kérdezik tőle, hogy lehetséges-e ezeknek a alakzatoknak a pontjait csak három színben festeni, hogy a vonalakkal összekötött pontok különböző színűek legyenek.
Ezt a „háromszínű” problémát nehéz megoldani. Általában véve, a háromszínű ábra összeállításához (vagy annak megállapításához, hogy nem létezik) szükséges idő exponenciálisan növekszik, amint az ábra növekszik. Például, ha egy számnak 20 vonal-összekötési pontja van, akkor a probléma megoldása a nanoszekundumok huszadik teljesítményére 3-ig terjed, azaz több másodpercre esik az az időegységek, amelyekhez hozzászoktunk. De ha ez a szám 60 ponttal rendelkezik, akkor a megoldás keresése százszor hosszabb időt vesz igénybe, mint az univerzum becsült kora.
De képzeljük el: valaki állítja, hogy ilyen háromszínű figurát készített. Nem sok időbe telik, hogy ellenőrizzük nyilatkozatának valódiságát. Most kezdjük el ellenőrizni a vonalak csatlakozási pontjait egyenként. A szám növekedésével az ellenőrzési idő lassan növekszik. Ez az úgynevezett polinomiális idő. Ennek eredményeként kiderül, hogy a számítógépnek nem sokkal több időbe telik egy háromszínű ábra 60 csúcsú ellenőrzése, mint a 20 csatlakozási ponttal rendelkező ábra ellenőrzéséhez.
"Nagyon könnyű kipróbálni, hogy ez az áramkör működjön, mindaddig, amíg ez egy igazi háromszínű alak" - mondja John Wright, a MIT fizikus, aki egy új papírt írt a Caltech Anand Natarajan című művével. …
Az 1970-es években a programozók azonosítottak egy olyan problémacsoportot, amelyet könnyű tesztelni, bár néha nehéz megoldani. Ezt az osztályt NPT-nek adták - nem determinisztikus polinomiális idõ. Azóta sok számítógépes tudós nagyon intenzíven vizsgálja ezeket a problémákat. A tudósok különösen azt akarják tudni, hogyan változik a probléma ezen osztálya, amikor az ellenőr új módszerekkel ellenőrzi a megoldás helyességét.
HELYES KÉRDÉSEK
Natarajan és Wright munkája előtt két fontos felfedezés történt a megoldás helyességének igazolására. Ezek jelentősen megnövelték a szuper kemény problémák tesztelésének képességét.
Az első kitörés felfedezésének megértése érdekében képzelje el, hogy színvak vagy. Két kockát helyeznek az asztalra előtted, és megkérdezik, hogy azonos színűek vagy eltérőek-e. Ez a feladat lehetetlen számodra. Sőt, nem áll módjában kipróbálni egy másik személy döntését.
De megkérdezheti ezt a személyt, akit közmondásnak hívunk. Tegyük fel, hogy a közmondó azt mondja neked, hogy egy pár kocka különböző színű. Az első kockát "A" betűvel, a második "B" betűvel jelöljük. Ved a kockákat, elrejti a háta mögött, és többször átadja kézről kézre. Akkor megmutatja a kockákat, és megkéri a közmondást, hogy mutassa meg az A. kockát.
Ha a kockák különböző színűek, akkor minden rendkívül egyszerű. A próféta tudja, hogy az A kocka, mondjuk, piros, és minden alkalommal helyesen mutat rá.
De ha a kocka azonos színű, vagyis a próféta hazudott, mondván, hogy a színek különböznek, akkor csak azt tudja kitalálni, hogy melyik kocka van. Emiatt csak helyesen jelzi az idő 50% -át. Ez azt jelenti, hogy ha többször megkérdezi a közmondást a megoldásról, ellenőrizheti annak helyességét.
"A vizsgáztató kérdéseket tehet fel a közmondónak" - mondta Wright. "És talán a beszélgetés végén nő a hitelesítő magabiztossága."
1985-ben egy programozó trió bebizonyította, hogy az ilyen interaktív igazolások felhasználhatók a NIP osztálynál összetettebb problémák megoldásainak tesztelésére. Munkájuk eredményeként megjelent egy új típusú probléma, az IPT, az interaktív polinomidő. A két kocka színének tesztelésére használt módszer felhasználható a bonyolultabb problémák és kérdések megoldásainak tesztelésére.
Ugyanezen évtizedben megtették a második fő lépést. Itt minden rendőrségi nyomozás logikáját követi. Ha két gyanúsítottja van, aki szerinte bűncselekményt követett el, akkor együtt nem fogja kihallgatni őket. Különböző helyiségekben fogja kihallgatni őket, majd összehasonlítja az általuk adott válaszokat. Ha ezeket az embereket külön hallgatja meg, több igazságot tanulhat meg, mintha csak egy gyanúsított lenne.
"A két gyanúsított nem lesz képes előállítani valami hihető és következetes verziót, mert egyszerűen nem tudják egymás válaszát" - mondta Wright.
1988-ban egy négy számítógépes tudósból álló csoport bebizonyította, hogy ha két számítógépet külön kérik meg, hogy ugyanazt a problémát külön oldják meg, majd külön kérdezzék meg a válaszokat, akkor a problémák még szélesebb osztályát lehet kipróbálni, mint az IPV-t. Ezt az osztályt IDMD-nek hívják - sok próféta interaktív bizonyítéka.
Ennek a megközelítésnek a segítségével például meg lehet vizsgálni a "háromszínű" problémákat olyan alakzatok sorozatával szemben, amelyek méretüknél sokkal gyorsabban növekszik a méret, mint a nemdeterminiszta polinomiális időben. Nem determinisztikus polinom időben az alakzatok mérete lineárisan növekszik - a vonalak csatlakozási pontjainak száma 1-ről 2-re, majd 3-ra, majd 4-re növekedhet és így tovább. Így soha nem lesznek hatalmas különbségek az ábra méretében a háromszín színének teszteléséhez szükséges idő alatt. De ha egy interaktív bizonyítékról beszélünk, amelyben sok próféta van, akkor itt az ábra pontszáma exponenciálisan növekszik.
Ennek eredményeként ezek a számok túl nagyok és nem illeszkednek az ellenőrző számítógép memóriájába, ezért nem tudja ellenőrizni a háromszínüket a csatlakozási pontok listájának futtatásával. De továbbra is ellenőrizhető a háromszín, ha a két provert külön, de kapcsolódó kérdésekre felteszi.
Az IDMD probléma osztályban a vizsgáztató elegendő memóriával rendelkezik egy program futtatásához annak meghatározására, hogy az alakzat két pontja egy vonalhoz kapcsolódik-e. A közmondó ezután megkérheti minden közmondót, hogy nevezze meg a vonallal összekötött két pont egyikét, majd könnyen összehasonlíthatja a próféta válaszait, hogy megbizonyosodjon arról, hogy a háromszínű ábra helyes-e.
A nehezen megoldható, de könnyen ellenőrizhető feladatok szintjének növelése az NPV-től az IPV-ig, majd az IDMD-hez klasszikus számítógépekkel érhető el. A kvantum számítógépek másképp működnek. Évtizedekig nem volt egyértelmű, hogy hogyan változtatják meg a képet, vagyis hogy nehezebb vagy könnyebb ellenőrizni a megoldást a segítségükkel.
Natarajan és Wright új munkája válaszol erre a kérdésre.
QUANTUM DÖNTÉS
A kvantumszámítógépek kvantumbitek (kvitek) manipulálásával hajtják végre a számítást. Furcsa tulajdonságuk van, amelynek lényege az, hogy összetéveszthetőek egymással. Amikor két kvbit vagy akár nagy kvbitrendszer összefonódik egymással, ez azt jelenti, hogy fizikai tulajdonságaik bizonyos módon megszabadítják őket.
Új munkájukban Natarajan és Wright két olyan különálló kvantumszámítógéppel foglalkoznak, amelyek közös, egymással összefonódott kviteket osztanak meg.
Úgy tűnik, hogy egy ilyen rendszer ellentétes az érvényesítéssel. Az interaktív bizonyítás sok próféta meggyőző képessége pontosan azzal magyarázható, hogy két provert meghallgathat külön, majd összehasonlíthatja a válaszokat. Ha ezek a válaszok megegyeznek, akkor valószínűleg helyesek. De ha két próféta zavart állapotban van, akkor nagyobb esélyük van arra, hogy következetesen és következetesen rossz válaszokat adjunk.
Valójában, amikor 2003-ban először született két összefonódott kvantumszámítógépet, a tudósok azt sugallták, hogy az összefonódás gyengíti a hitelesítési képességeket. "Mindenkinek, köztük én is, nagyon nyilvánvaló reakciójuk volt: most a próduáknak több erő és meggyőző képességük lesz" - mondta Vidik. "A beolvadást felhasználhatják a válaszok összehangolására."
E kezdeti pesszimizmus ellenére Vidic több évet töltött másképp bizonyítani. 2012-ben, Tsuyoshi Ito-val együtt, bebizonyította, hogy továbbra is lehetséges az IDMD osztály összes problémájának kipróbálása kvóta számítógépek segítségével.
Natarajan és Wright most bebizonyította, hogy a helyzet még jobb. A probléma szélesebb osztálya kipróbálható az összefonódással, mint anélkül. Az összefonódott kvantumszámítógépek közötti kapcsolatok a vizsgáztató javára fordíthatók.
Hogy megértsük, emlékezzünk vissza a háromszínű figurák tesztelésére, amelyek mérete exponenciálisan növekszik, ha sok próféta interaktív igazolását használunk. A hitelesítőnek nincs elegendő memóriája a teljes ábra tárolására, de elegendő ahhoz, hogy két kapcsolódó pontot azonosítson, és megkérdezze a prófétarendszerektől, hogy milyen színűek.
Ha olyan problémákról beszélünk, amelyeket Natarajan és Wright figyelembe vesznek - és amelyek nemdeterminisztikus kettős exponenciális időnek (NDEW) nevezett osztályba tartoznak -, akkor az ábra mérete még gyorsabban nő, mint az IDMD osztály problémája. Az NDEV-ben szereplő szám kétszeresen exponenciálisan növekszik. Vagyis kettős geometriai progresszió. Ez az érték nem a 21., 22., 23. fok sebességével növekszik, hanem "fok fokban". Emiatt a formák olyan gyorsan növekednek, hogy a vizsgáztató nem talál egyetlen összekapcsolt pontot.
„2n bitre van szükség egy pont megjelöléséhez, amely exponenciálisan nagyobb, mint a hitelesítő működési memóriája” - mondja Natarajan.
Natarajan és Wright azonban azt állítják, hogy kettős exponenciális alak háromszínű színét tesztelni lehet anélkül, hogy meg tudnánk határozni, hogy mely pontokban kérdezzük meg a prófétokat. A lényeg az, hogy a próduák maguk is kérdéseket tesznek fel.
A tudósok szerint az a gondolat, hogy megkérdezzék a számítógépeket, hogy ellenőrizzék saját döntéseiket a szavazás útján, ugyanolyan ésszerű, mint az a gondolat, hogy megkérdezzék a bűncselekmény gyanúját. Vagyis ez teljes ostobaság. Igaz, Natarajan és Wright azzal érvelnek, hogy nem erről van szó. Ennek oka a zavar.
"Az összefonódott állapot megosztott erőforrás" - mondja Wright. "A teljes protokollunk célja annak megértése, hogyan lehet ezt a megosztott erőforrást felhasználni a kapcsolódó kérdések előkészítésére."
Ha a kvantumszámítógépeket összekeverik, akkor a pontok megválasztása összekapcsolódik, és a helyes kérdéseket fogják adni a háromszín színének teszteléséhez.
Ugyanakkor a vizsgáztatónak nincs szüksége a két kvantumszámítógép túl szoros összekapcsolására, mivel ezekre a kérdésekre adott válaszuk következetes lesz (ez megegyezik azzal a ténnyel, hogy két gyanúsított egyetértett egymás között hamis alibival). Egy másik furcsa kvantumjellemző kijavítja ezt a problémát. A kvantummechanikában a bizonytalanság elv megakadályozza, hogy egyidejűleg megismerjük a részecske helyzetét és az erő lendületét. Ha egyiket mér, akkor elpusztíthatja a másikra vonatkozó információkat. A bizonytalanság elve súlyosan korlátozza a kvantumrendszer két "kiegészítő" tulajdonságának ismereteit.
Natarajan és Wright ezt kihasználták munkájuk során. A csúcs színének kiszámításához két kvantumszámítógépet használnak, amelyek kiegészítik egymást a mérésekkel. Minden számítógép kiszámítja pontjainak színét, és ezzel megsemmisíti az összes információt a másik számítógép pontjairól. Más szavakkal: az összefonódás lehetővé teszi a számítógépek számára, hogy egymással összefüggő kérdéseket fogalmazjanak meg, de a bizonytalanság elve megakadályozza őket abban, hogy megválaszolják őket.
"El kell felejtenünk a közmondást [az események hamis verziójáról], és ez a legfontosabb dolog, amit [Natarajan és Wright] tettek munkájuk során" - mondta Vidik. "Arra kényszerítik a közmondást, hogy távolítsa el az információkat, amikor méréseket végez."
Munkájuk hatalmas és nagyon fontos következményekkel jár. Mielőtt ez a munka megjelent, a tudásmennyiség korlátja, amelyet teljes bizalommal megkaphattunk, jelentősen alacsonyabb volt. Ha választ kapnánk az IDMD problémájára, hitben kellene elfogadnunk, mivel nincs más választásunk. Natarajan és Wright azonban megszüntette ezt a korlátozást, és lehetővé tette a sokkal több számítási problémára adott válaszok érvényesítését.
De most, hogy megtették, nem világos, hogy hol van az érvényesítési határ.
"Ez sokkal tovább mehet" - mondta Lance Fortnow, a georgiai technológiai intézet számítástechnikai kutatója. "Teret hagynak még egy lépésre."
Kevin Hartnett