Случайността е жизненоважна основа на съвременното общество, като осигурява справедливост при лотариите и избора на жури. Тя се използва и в цифровата комуникация, за да гарантира, че частните ключове, използвани при криптиране, са тайни и непредсказуеми. В организациите случайността е необходима и за прилагането на диференцирано частни протоколи за машинно обучение.

Като детерминистични системи, класическите компютри не могат да създават истинска случайност при поискване. В резултат на това, за да предложим истинска случайност в класическите компютри, често прибягваме до специализиран хардуер, който събира ентропия от непредсказуеми физически източници, например чрез наблюдение на движенията на мишката, наблюдаване на колебанията на температурата, наблюдение на движението на лава лампи или, в екстремни случаи, откриване на космическа радиация. Тези мерки са тромави, трудно се мащабират и нямат строги гаранции, което ограничава възможностите ни да проверим дали техните резултати са наистина случайни.

Предизвикателството се усложнява от факта, че не съществува начин да се провери дали дадена последователност от битове е наистина случайна. Предвид трудностите при осигуряването и проверката на случайността, прибягваме до доверието: просто трябва да вярваме, че хардуерът генерира свежа случайност.

Изискването за доверие обаче се превръща в проблем, когато случайността се използва за вземане на решения между страни, които си нямат доверие, например когато конкуренти прибягват до хвърляне на монета, за да решат спор. Кой може да хвърли монетата? Ако страните участват дистанционно, как може да се провери дали изобщо е имало хвърляне на монета?

Идеалното решение би било вид случайност със следните три характеристики:

• Тя идва от надежден източник, който може да бъде проверен.
• Тя е със строги математически гаранции.
• Тя не може да бъде манипулирана от злонамерен противник.
• Този вид случайност се нарича сертифицирана случайност.

Един от възможните начини за проверка на това, че дадена поредица от числа наистина идва от случаен източник, е да се изиска някакъв подпис или доказателство, може би вградено в самите числа, че те не биха могли да бъдат фалшифицирани с помощта на предсказуеми източници. Можете например да поискате от доставчика си на случайност да извлича числа само от определено вероятностно разпределение, което е трудно да бъде имитирано с помощта на неслучайни източници. След това бихте могли да проверите дали числата, които получавате, идват от избраното от вас разпределение и следователно трябва да са наистина случайни.

Оказва се, че подобен протокол е невъзможно да бъде реализиран с помощта на конвенционални компютри, но може да бъде осъществен с помощта на квантов компютър.

Протокол за сертифицирана случайност от квантов компютър

Случайността е присъща на квантовия компютър: квантовият бит може да се намира в суперпозиция от нула и единица, а измерването му е по същество случаен процес. Освен това, тъй като квантовите компютри все още са обект на изчислителна сложност и теоретични ограничения, техните изходи могат да бъдат строго анализирани. Заедно тези две свойства осигуряват път за използване на квантов компютър за генериране на числа, за които може да се докаже математически, че са случайни.

Конкретно, квантовият компютър, изпълняващ квантова програма (наричана още схема), произвежда изходи, които са по своята същност случайни и уникални за изпълняваната програма. Докато един честен отдалечен доставчик на случайност може бързо да изпълни схеми на квантов компютър, за да предостави числа, съответстващи на квантовите схеми, един злонамерен сървър би се затруднил да направи неслучайни битове, съвместими с предоставените схеми. Изключително трудно е за конвенционален компютър да предвиди вероятните резултати от квантовите програми, тъй като квантовите програми отнемат експоненциално дълго време, за да бъдат изпълнени класически, дори и на най-мощния суперкомпютър.

В най-новата ни работа, публикувана в Nature, демонстрираме изпълнението на такъв протокол с помощта на нашите сътрудници от Quantinuum, Oak Ridge National Laboratory, Argonne National Laboratory и The University of Texas at Austin. Разглеждаме 56-кубитовия квантов компютър Quantinuum System Model H2 с уловени йони като ненадежден сървър, на който изпращаме предизвикателни квантови схеми една по една.

Тези вериги създават вероятностни разпределения, които са изключително трудни за емулиране с помощта на конвенционални компютри: докато очаквахме квантовият компютър да изпълни всяка верига за около две секунди, наблюдавахме, че на най-големия суперкомпютър в света ще са необходими около сто секунди, за да симулира изпълнението на същата верига. За всяка такава схема поискахме от Quantinuum да ни изпрати число в рамките на две секунди и половина. Накрая, за проверка на случайността, изчислихме корелацията на получените числа и схемите, с които започнахме, и математически проверихме, че поне определена част от битовете, получени от Quantinuum, са получени от принципно случайни квантови измервания на първоначално подадените схеми.

Извършването на тази проверка е изчислителна задача. В нашата демонстрация, за да определим корелацията между нашите схеми и получените данни, използваме четири суперкомпютъра, включително Frontier – най-големият суперкомпютър в света по време на експеримента, собственост на Министерството на енергетиката на САЩ и разположен в Националната лаборатория Oak Ridge. Ключовото схващане, което прави този протокол мащабируем, е, че макар да се налага само от време на време да проверяваме нашата случайност, един злонамерен агент би трябвало непрекъснато да изразходва неустойчиво количество ресурси, за да избегне откриването.

От нашата демонстрация проверяваме, че поне 71 313 бита ентропия са сигурни срещу експериментален злонамерен противник, който е поне четири пъти по-мощен от най-големия суперкомпютър в света. Изключително важно е, че ни е гарантирана случайността, дори ако квантовият компютър е действал злонамерено, компрометиран е от трета страна или е бил подставено лице. Следователно случайността, която генерира нашият протокол, не изисква да се доверяваме на никаква външна организация.

Такава проверима квантова случайност е възможна благодарение на квантовите компютри, които могат да изпълняват програми много по-бързо от обикновените компютри. Поради своята простота задачата за вземане на проби от квантови схеми се е утвърдила като еталон за демонстриране на мощта на квантовите компютри и е повтаряна в много експерименти в лаборатории. Нашата работа е първата, която използва тази задача за вземане на проби, за да реализира потенциално полезен криптографски примитив.

Източник: jpmorgan.com