Бозонний семплінг
Бозонний семплінг — це обмежена модель неуніверсальних квантових обчислень, запроваджена С. Ааронсоном та А. Архіповим[1] після оригінальної роботи Л. Троянського та Н. Тишбі, яка досліджувала можливе використання розсіювання бозонів для оцінки очікуваних значень перманентів матриць.[2] Модель складається з висновування з розподілу ймовірностей однакових бозонів, розсіяних лінійним інтерферометром. Хоча проблема чітко визначена для будь-яких бозонових частинок, її фотонна версія в даний час розглядається як найбільш перспективна платформа для масштабованої реалізації пристрою бозонного семплінгу, що робить її неуніверсальним підходом до лінійних оптичних квантових обчислень. Більше того, хоча схема універсального бозонного семплінгу не є загальновідомою, вона реалізує обчислювальні завдання, які важко реалізувати на класичних комп'ютерах, використовуючи набагато менше фізичних ресурсів, ніж повна лінійна оптична квантова обчислювальна установка. Як було повідомлено командою вчених з Університету науки і техніки Китаю (англ. University of Science and Technology of China) квантова перевага була продемострована саме з використанням бозонного семплінгу.[3]
Розглядається багатомодовий лінійно-оптичний ланцюг із N мод, в який вводять M нерозрізнених одиночних фотонів (N>M). Фотонна реалізація завдання бозонного семплінгу складається з генерації вибірки з розподілу ймовірностей однофотонних вимірювань на виході схеми. Зокрема, для цього потрібні надійні джерела одиночних фотонів (в даний час найпоширенішими є кристали з низхідним параметричним розсіянням), а також лінійний інтерферометр. Останні можуть бути виготовлені, наприклад, з дільниками променів із зплавлених волокон,[4] за допомогою інтегрованих інтерферометрів на основі кремнезему на кремнії[5] або нанесених лазером[6][7][8] інтегрованих інтерферометрів, або з оптичними чіпами з електричним та оптичним з'єднанням.[9] Нарешті, схема також вимагає високоефективних детекторів для підрахунку одиничних фотонів, таких як такі, що базуються на зміщених струмом надпровідних нанопроводах, які виконують вимірювання на виході схеми. Отже, виходячи з цих трьох складових, установка бозонного семплінгу не вимагає жодних допоміжних засобів, адаптивних вимірювань або операцій заплутування, як це робиться, наприклад, в універсальній оптичній схемі за Найлом, Лафламме та Мілберном (схема KLM). Це робить його не універсальною моделлю квантових обчислень і зменшує кількість фізичних ресурсів, необхідних для її практичної реалізації.
Зокрема, припустимо, що лінійний інтерферометр описується унітарною матрицею N×N , який виконує лінійне перетворення операторів народження (знищення) вхідних мод схеми:
Тут i (j) позначають вхідні (вихідні) моди, а позначає оператори народження (знищення) вихідних мод (i, j=1,…, N). З іншого боку, інтерферометр, що характеризується унітарною матрицею , природно виконує перетворення над вхідними станами. Більше того, між унітарними матрицями існує гомоморфізм, а останнє перетворення виконується у експоненціально великому гільбертовому просторі системи: простий підрахунок аргументів показуює, що розмір гільбертового простору, що відповідає системі нерозрізнених фотонів M, розподілених між N модами задається біноміальним коефіцієнтом (зауважте, що хоча цей гомоморфізм існує, не всі значення можливі). А саме, припустимо, в інтерферометр вводиться вхідний стан поодиноких фотонів з — кількість фотонів, що вводяться в k-у моду). Потім стан на виході схеми можна записати як Простий спосіб зрозуміти гомоморфізм між та наступний.
Визначимо ізоморфізм для базових станів: x, і отримаємо наступний результат: xx
Отже, ймовірність виявлення фотонів на k-ій вихідній моді подано як[10]
У наведеному вище виразі розшифровується як перманентів матриці яка отримана з унітарної матриці повторенням разів її i-го стовпчика і разів її j-го рядка. Зазвичай в контексті проблеми бозонного семплінгу вхідний стан приймається у стандартній формі, що позначається як для якого в кожну з перших М мод інтерферометра вводиться один фотон. У цьому випадку наведений вище вираз звучить так:
де матриця отримана з збереженням перших М стовпців і повторенням разів її j-го рядка. Згодом завдання бозонного семплінгу полягає у отриманні точних або приблизних виборок з вищезазначеного розподілу вихідних даних, враховуючи унітарну матрицю , що описує лінійно-оптичну схему як вхідні дані. Як докладно описано нижче, поява перманента у відповідних статистичних даних однофотонних вимірювань сприяє складності проблеми бозонного семплінгу.
Основною причиною зростаючого інтересу до моделі бозонного семплінгу є те, що, незважаючи на те, що вона не є універсальною, існує впевнена думка, що вона виконує обчислювальну задачу, яка є нерозв'язною для класичного комп'ютера. Однією з основних причин цього є те, що розподіл ймовірностей, з яким пристрій для бозонного семплінгу повинен брати вибірки, пов'язаний з перманентом комплексних матриць. Обчислення перманенту[en] в загальному випадку є надзвичайно важким завданням: воно потрапляє до класу складності #P-складні[en]. Більше того, його апроксимація в межах мультиплікативної помилки також є #P-складною проблемою.
Усі сучасні докази складності моделювання бозонного семплінгу на класичному комп'ютері покладаються на сильні обчислювальні наслідки, які могло б мати його ефективне моделювання за допомогою класичного алгоритму. А саме ці докази показують, що ефективне класичне моделювання означало б крах поліноміальної ієрархії класів складності до її третього рівня — можливість, яка вважається дуже малоймовірною[джерело?] спільнотою інформатиків через її сильні обчислювальні наслідки (відповідно сильні наслідки проблеми P = NP).
Доказ складності точної проблеми бозонного семплінгу можна отримати двома різними шляхами. Зокрема, перший використовує інструменти теорії складності обчислень та поєднує в собі наступні два факти:
- Наближення ймовірності конкретного результату вимірювання на виході лінійного інтерферометра з точністю до мультиплікативної константи є проблемою #P-складною (через складність перманента)
- Якщо б існував класичний алгоритм точного бозонного семплінгу з поліноміальним часом, то вищевказана ймовірність могла бути наближена з точністю до мультипликативної константи в класі складності BPPNP,[11] тобто в межах третього рівня ієрархії поліноміальної складності
Поєднання цих двох фактів разом із теоремою Тода[en] призводить до розпаду ієрархії поліноміальної складності, що, як зазначалось вище, малоймовірно. Це призводить до висновку, що не існує класичного алгоритму з поліноміальним часом виконання для точної задачі бозонного семплінгу.
З іншого боку, альтернативний доказ натхненний подібним результатом для іншої обмеженої моделі квантових обчислень — моделі миттєвих квантових обчислень.[12] А саме, в доказі використовується схема KLM, яка говорить, що лінійна оптика з адаптивними вимірюваннями є універсальною для класу BQP[en]. Він також спирається на такі факти:
- Лінійна оптика з постселективними вимірюваннями є універсальною для PostBQP[en], тобто квантового класу поліномного часу з постселекцією (прямий наслідок конструкції KLM)
- Клас PostBQP еквівалентний PP (тобто клас імовірнісного поліноміального часу): PostBQP = PP[13]
- Існування класичного алгоритму бозонного семплінгу передбачає моделювання постселективної лінійної оптики в класі PostBPP (тобто класичного поліноміального часу з постселекцією, відомого також як клас BPPpath)
Знову ж таки, поєднання цих трьох результатів, як і в попередньому випадку, призводить до розпаду ієрархії поліноміальної складності. Це робить існування класичного алгоритму поліноміального часу для точної проблеми бозонного семплінгу надзвичайно малоймовірним.
Найкращий запропонований класичний алгоритм для точного бозонного семплінгу працює за час для системи з n фотонів та m мод.[14] Цей алгоритм призводить до оцінки у 50 фотонів, необхідних для демонстрації квантової переваги за допомогою бозонного семплінгу. Існує також реалізація з відкритим вихідним кодом мовою програмування R.
Наведені вище докази складності не застосовуються до реалістичної реалізації пристрою для бозонного семплінгу через недосконалість будь-якої експериментальної установки (включаючи наявність шуму, декогеренцію, втрату фотонів тощо). Тому для практичних потреб потрібно відповідати складності для відповідного наближеного завдання. Останнє складається з вибірки з розподілу ймовірностей, що є -наближеною до одного з поданих , через загальну відстань варіації[en]. Тоді розуміння складності цієї проблеми спирається на кілька додаткових припущень, а також на дві поки не доведені гіпотези.
Зокрема, докази точної задачі бозонного семплінгу тут не можуть бути застосовані безпосередньо, оскільки вони засновані на #P-складності оцінки експоненціально-малої ймовірності конкретного результату вимірювання. Таким чином, якщо той, хто виконує семплінг, «знав» що з ми хотіли оцінити, тоді він міг би визнати його пошкодженням (якщо завдання є приблизним). Ось чому, ідея полягає в тому, щоб «приховати» вищевказану ймовірність у випадковій унітарній матриці N×N. Це можна зробити, знаючи, що будь-яка підматриця M×M унітарної матриці , випадково обраних відповідно до міри Хаара, близьких за відстанню варіації до матриці незалежних однаково розподілених комплексних випадкових змінних з нормальним розподілом, за умови, що M ≤ N1/6 (випадкові матриці Хаара можуть бути безпосередньо реалізовані в оптичних ланцюгах шляхом відображення незалежних функцій щільності ймовірності для їх параметрів на компоненти оптичного ланцюга, тобто дільники променя та фазоперетворювачі[15]). Отже, якщо лінійна оптична схема реалізує випадкову унітарну матрицю Хаара, змагальна особа, що виконує вибірку, не зможе визначити, яка з ймовірностей, яких експоненційно багато, нас цікавить і, отже, не зможемо уникнути його оцінки. В цьому випадку пропорційна квадрату абсолютного значення перманента матриці M×M незалежних однаково розподілених гауссових величин, внесених всередину Ці аргументи підводять нас до першої гіпотези доказу складності наближеної задачі бозонного семплінгу — гіпотези перманента нормально розподілених величин:
- Апроксимація перманента матриці з незалежних однаково розподілених величин з нормальним розподілом з точністю до мультиплікативної помилки — це #P-складне завдання.
Більше того, наведену вище гіпотезу можна пов'язати з оцінкою , якій пропорційна дана ймовірність конкретного результату вимірювання. Однак для встановлення цього зв'язку потрібно спиратися на іншу гіпотезу — гіпотезу про постійну антиконцентрацію:
- Існує такий поліном Q, що для будь-якого M і δ> 0 ймовірність над матрицями M × M виконується наступна нерівність, менша ніж δ:
Використовуючи вищезазначені дві гіпотези (які мають декілька свідчень істинності), остаточне підтвердження врешті-решт стверджує, що існування класичного алгоритму поліноміального часу для задачі приблизного бозонного семплінгу передбачає крах ієрархії поліноміальної складності. Варто також згадати ще один факт, важливий для доказу цього твердження, а саме так званий парадокс бозонного дня народження (за аналогією з відомим парадоксом днів народження). Останній стверджує, що якщо M однакових бозонів розпорошені між N≫M 2 модами лінійного інтерферометра без двох бозонів в одній моді, то з високою ймовірністю двох бозонів також не буде знайдено в одній вихідній моді.[16] Ця властивість спостерігалась експериментально[17] з двома і трьома фотонами в інтегрованих інтерферометрах до 16 мод. З одного боку, ця особливість полегшує реалізацію обмеженого пристрою для бозонного семплінгу. А саме, якщо ймовірність мати більше одного фотона на виході лінійного оптичного ланцюга є незначною, більше не потрібно детекторів, що розпізнають число фотонів: детекторів включення-вимкнення буде достатньо для реалізації установки.
Хоча ймовірність конкретний результат вимірювання на виході інтерферометра пов'язаний з перманентом підматриць унітарної матриці, машина для бозонного семплінгу не дозволяє його оцінити. Основна причина полягає в тому, що відповідна ймовірність виявлення, як правило, експоненціально мала. Таким чином, щоб зібрати достатньо статистичних даних, щоб наблизити її значення, потрібно проводити квантовий експеримент експоненціально довго. Отже, оцінка, отримана за допомогою пристрою бозонного семплінгу, не є більш ефективною, ніж запуск класичного алгоритму поліноміального часу за Гурвіцем для апроксимації перманента будь-якої матриці в межах адитивної помилки.[18]
Як уже зазначалося вище, для впровадження машини для бозонного семплінгу необхідне надійне джерело багатьох нерозрізнювальних фотонів, і ця вимога в даний час залишається однією з основних труднощів при збільшенні складності пристрою. А саме, незважаючи на останні досягнення в технологіях генерації фотонів із використанням атомів, молекул, квантових точок та кольорових центрів у діамантах, найбільш широко використовуваним методом залишається механізм параметричного розсіювання. Основними перевагами джерел на основі параметричного розсіювання є висока нерозрізнюваність фотонів, ефективність збору та відносно прості експериментальні установки. Однак одним із недоліків цього підходу є його недетермінований характер. Зокрема, припустимо, що ймовірність генерування одного фотона за допомогою кристала з параметричним розсіюванням дорівнює ε. Тоді ймовірність одночасного генерування M одиночних фотонів дорівнює εM, яка експоненціально зменшується зі зростанням M. Іншими словами, для того, щоб генерувати вхідний стан для машини бозонного семплінгу, потрібно було б чекати експоненціально довгий час, що вбило б перевагу квантової установки перед класичною машиною. Згодом ця характеристика обмежила використання джерел на основі параметричного розсіювання лише демонстрацією доказу принципів пристрою для бозонного семплінгу.
Однак нещодавно було запропоновано нову схему, яка найкраще використовує джерела на основі параметричного розсіювання для потреб бозонного семплінгу, значно підвищуючи швидкість настання M-фотонної події. Цей підхід отримав назву бозонний семплінг з розсіянням,[19][20] який складається з підключення N однофотонних джерел (N> M) до різних вхідних портів лінійного інтерферометра. Тоді, при накачуванні всіх N кристалів з параметричним розсіюванням одночасними лазерними імпульсами, ймовірність генерування M фотонів матиме вигляд . Отже, для N≫M це призводить до експоненціального поліпшення швидкості генерації одиночного фотона по відношенню до звичайного бозонного семплінгу із фіксованим входом із M джерелами. Цей параметр також можна розглядати як проблему семплінгу N двомодових стиснених вакуумних станів, згенерованих N джерелами на основі параметричного розсіювання.
Бозонний семплінг з розсіянням все ще нерозв'язна для класичного комп'ютера: у звичайній установці ми зафіксували стовпці, які визначали нашу підматрицю M×M, і змінювали лише рядки, тоді як тепер ми також змінюємо стовпці залежно від які M з N кристалів з параметричним розсіюванням генерували одиночні фотони. Тому доказ можна побудувати тут подібним оригінальному. Крім того, нещодавно також було здійснено бозонний семплінг з розсіянням із шістьма джерелами фотонних пар, з'єднаними з інтегрованими фотонними схемами з дев'ятьма та тринадцяттю модами, що є важливим стрибком до переконливої експериментальної демонстрації квантової обчислювальної переваги.[21] Модель бозонного семплінгу з розсіюванням може бути узагальнена на той випадок, коли обидві ніжки джерела на основі параметричного розсіювання піддаються лінійним оптичним перетворенням (в оригінальному випадку розсіяне випромінювання одного з плечей використовується для проголошення, тобто воно проходить через канал ідентичності). Така подвійна модель бозонного семплінгу з розсіюванням також є обчислювально складною, що доведено використанням симетрії квантової механіки при оберненні часу.[22]
Інша фотонна реалізація бозонного семплінгу стосується гауссових вхідних станів, тобто станів, квазімовірність (функція розподілу Вігнера[en]) яких є гауссовою. Складність відповідного завдання бозонного семплінгу може бути пов'язана з складністю бозонного семплінгу з розсіянням. А саме, останній може бути вбудований у звичайну установку бозонного семплінгу за допомогою гауссових входів. Для цього потрібно генерувати двомодові заплутані гауссові стани і застосовувати випадковий унітарний оператор Хаара до їх «правих половин», при цьому нічого не роблячи з іншими. Тоді ми можемо виміряти «ліві половинки», щоб з'ясувати, в якому з вхідних станів містився фотон, перш ніж ми застосували . Це точно еквівалентно бозонному семплінгу з розсіянням, за винятком того факту, що наші вимірювання фотонів-зразків були відкладені до кінця експерименту, а не виконані на початку. Отже, щодо складності приблизного гаусового бозонного семплінгу можна використовувати точно тіж ж самі припущення про складність, що і приблизний бозонноий семплінг.[20] Гауссові ресурси також можуть бути використані на етапі вимірювання. А саме, можна визначити модель бозонного семплінгу, де лінійна оптична еволюція вхідних однофотонних станів завершується вимірами Гаусса (точніше, восьмипортовим гомодинним виявленням[en], яке проектує кожну вихідну моду на стиснутий когерентний стан). Така модель має справу з результатом вимірювання неперервної змінної, що за певних умов є обчислювально важким завданням.[22] Нарешті, також доступна лінійна оптична платформа для здійснення експерименту з бозонним семплінгом, де вхідні одиничні фотони зазнають активного (нелінійного) перетворення Гаусса. Цей параметр використовує набір двомодових стиснених вакуумних станів як попереднього ресурсу, не потребуючи однофотонних джерел або вбудованого нелінійного середовища для посилення.[23]
Вищезазначені результати свідчать про те, що існування класичного алгоритму поліноміального часу для вихідної схеми бозонного семплінгу з нерозрізненими одиночними фотонами (у точному та наближеному випадках), для бозонного семплінгу з розсіянням, а також для загальних проблем гаусового бозонного семплінгу є малоймовірним. Тим не менше, існують деякі нетривіальні реалізації проблеми бозонного семплінгу, які дозволяють проводити її ефективне класичне моделювання. Одним з таких прикладів є випадки, коли в оптичний ланцюг вводяться помітні поодинокі фотони. У цьому випадку замість підсумовування амплітуди ймовірності, що відповідає фотонним багаточастинковим шляхам, потрібно підсумувати відповідні ймовірності (тобто квадратичні абсолютні значення амплітуд). Отже, ймовірність виявлення буде пропорційна перманенту підматриць (складових) квадрата абсолютного значення унітарної матриці . Остання тепер є негативною матрицею. Отже, хоча точне обчислення відповідної константи є проблемою #P-повною, його апроксимація може бути ефективно виконана на класичному комп'ютері завдяки насіннєвому алгоритму Джерума, Сінклера та Вігоди.[24] Іншими словами, приблизний бозонний семплінг з розрізнюваними фотонами ефективно моделюється класичним алгоритмом.
Інший приклад класично модельованих установок бозонного семплінгу складається із вибірки з розподілу ймовірностей когерентних станів, що вводяться в лінійний інтерферометр. Причина полягає в тому, що на виході лінійного оптичного ланцюга когерентні стани залишаються такими і не створюють жодного квантового заплутування серед мод. Точніше, трансформуються лише їх амплітуди, і перетворення можна ефективно обчислити на класичному комп'ютері (обчислення включає множення матриць). Цей факт може бути використаний для виконання відповідних завдань семплінгу з іншого набору станів: так званих класичних станів, чия P-функція Glauber-Sudarshan[en] є чітко визначеним розподілом ймовірностей. Ці стани можна представити як суміш когерентних станів завдяки теоремі оптичної еквівалентності[en]. Отже, вибираючи випадкові когерентні стани, розподілені відповідно до відповідної функції P, можна здійснити ефективне класичне моделювання бозонного семплінгу з цього набору класичних станів.[25][26]
Вищезазначені вимоги до машини для бозонного семплінгу дозволяють проводити її маломасштабну конструкцію за допомогою існуючих технологій. Отже, незабаром після того, як була введена теоретична модель, виникли чотири різні групи[4][5][7][8] одночасно повідомили про свою реалізацію.
Зокрема, це включало здійснення бозонного семплінгу з:
- два та три фотони, розсіяні шестимодовим лінійним унітарним перетворенням (представленим двома ортогональними поляризаціями в 3×3 просторових модах дільника променів із зплавлених волокон) завдяки співпраці університету Квінсленда та MIT[4]
- три фотони в різних модах шестимодового ланцюга хвилеводу з діоксида кремнію на кремнії завдяки співпраці університетів Оксфорда, Шанхая, Лондона та Саутгемптона[5]
- три фотони у фемтосекундному п'ятимодовому інтерферометрі, записані лазером, за співпраці між університетами Відня та Єни[7]
- три фотони у фемтосекундному лазерному п'ятимодовому інтерферометрі, що реалізує випадкове унітарне перетворення Хаара, за участю Міланського Інституту фотоніки та нанотехнологій, Університет Федерального Флуміненсе та Римський університет Сапієнца.[8]
Пізніше були проведені більш складні експерименти з бозонним семплінгом, зі збільшенням кількості просторових мод випадкових інтерферометрів до 13[27] and 9[28] мод, і реалізація 6-модової повністю реконфігуруваної інтегральної схеми.[9] Ці експерименти в цілому являють собою демонстрації принципів робочого пристрою для бозонного семплінгу та шлях до його більш масштабних реалізацій.
У 2015 був проведений перший експеримент з відбору зразків бозонів[21] з використанням шести джерел фотонних пар, з'єднаних з інтегрованими фотонними схемами з 13 модами. 6 джерел фотонних пар отримано за допомогою процесу параметричного розсіяння типу II у 3 різних нелінійних кристалах (використовуючи ступінь свободи поляризації). Це дозволило зробити бозонного семплінгу одночасно між 8 різними вхідними станами. 13-модовий інтерферометр реалізовано за допомогою фемтосекундної лазерної техніки запису на алюмо-боросилікатному склі.
Ця експериментальна реалізація являє собою стрибок у напрямку експериментальної демонстрації квантової переваги.[21]
Є ще кілька пропозицій щодо здійснення бозонного семплінгу фотонів. Сюди входить, наприклад, довільно масштабована схема бозонного семплінгу із використанням двох вкладених волоконних петель. У цьому випадку в архітектурі використовується кодування з використанням часових слотів, завдяки чому падаючі фотони утворюють імпульсну послідовність, що надходить у петлі. Тим часом, динамічно керовані коефіцієнти зв'язку петлі дозволяють побудувати довільні лінійні інтерферометри. Більше того, архітектура використовує лише одну точку інтерференції, і тому її може бути легше стабілізувати, ніж інші реалізації.[29]
Інший підхід спирається на здійснення унітарних перетворень у часових режимах, заснованих на дисперсії та формуванні імпульсів. А саме, проходження послідовно оголошених фотонів через незалежну від часу дисперсію та вимірювання часу виходу фотонів еквівалентно експерименту з бозонним семплінгом. Залежно від часу дисперсії також можливо реалізувати довільні одночастинні унітарні оператори. Ця схема вимагає набагато меншої кількості джерел і детекторів і не вимагає великої системи дільників променя.[30]
Вихід працюючого універсального квантового комп'ютера, наприклад, алгоритм факторизації Шора, може бути ефективно перевірений класично, як це стосується всіх проблем у класі складності недетермінованого поліноміального часу (NP). Однак незрозуміло, чи подібна структура існує для схеми бозонного семплінгу. А саме, оскільки остання пов'язана з проблемою оцінки перманента матриць (потрапляючи до класу складності #P-складні), не зрозуміло, як перевірити правильність роботи для великих версій установки. Зокрема, наївна перевірка вихідних даних бозонного семплінгу шляхом обчислення відповідних ймовірностей вимірювань представляє проблему, яку не можна вирішити класичним комп'ютером.
Перше важливе питання полягає в тому, чи можна чи не можна розрізнити рівномірний розподіл та розподіл бозонного семплінгу шляхом проведення поліноміального числа вимірювань. Початковий аргумент, представлений у посиланні[31] стверджує, що до тих пір, поки використовуються симетричні параметри вимірювання, вищезазначене неможливо (грубо кажучи, симетрична схема вимірювання не дозволяє маркувати вихідні моди оптичного ланцюга). Однак у рамках сучасних технологій припущення про симетричну настройку не є виправданим (відстеження статистичних даних вимірювань є повністю доступним), і тому вищезазначений аргумент не застосовується. Тоді можна визначити суворий та ефективний тест для розрізнення статистики вибірки бозонів від неупередженого розподілу ймовірностей.[32] Відповідний дискримінатор корелюється із перманетом підматриці, асоційованої із заданою схемою вимірювання, але може бути ефективно розрахований. Цей тест був застосований експериментально для розрізнення бозонного семплінгу та рівномірного розподілу в 3-фотонному режимі з інтегральними схемами на 5, 7, 9 та 13 мод,[27] так же як для 9 мод.[28]
Наведений вище тест розрізняє більш складні розподіли, такі як квантовий та класичний, або між ферміонною та бозонною статистикою. Фізично вмотивованим сценарієм є небажане введення відмінності між фотонами, що руйнує квантову інтерференцію (цей режим легко доступний експериментально, наприклад, шляхом введення тимчасової затримки між фотонами). Тоді існує можливість налаштуватись між ідеально нерозрізнюваними (квантовими) та абсолютно відмінними (класичними) даними та виміряти зміну у відповідно побудованій метриці. Цей сценарій може бути вирішений за допомогою статистичного тесту, який виконує індивідуальне порівняння ймовірностей вихідних ймовірностей. Цей тест вимагає розрахунку невеликої кількості постійних, але не потребує розрахунку повного очікуваного розподілу ймовірностей. Про експериментальне впровадження тесту було успішно повідомлено в інтегрованих лазерних мікросхемах як для стандартного бозонного семплінгу[27] (3 фотони в 7-, 9- та 13-модових інтерферометрах) та версії бозонного семплінгу з розсіянням[21] (3 фотони в 9- і 13-модових інтерферометрах з різними вхідними станами). Інша можливість ґрунтується на властивості згуртування нерозрізнюваних фотонів. Можна проаналізувати ймовірність знайти результати вимірювання збігу k (без будь-якого багаторазово заповнення вхідної моди), яка значно вища для розрізнюваних частинок, ніж для бозонів через тенденцію до згуртування останніх.[28] Нарешті, залишаючи простір випадкових матриць, можна зосередитися на конкретних багатомодових установках з певними функціями. Зокрема, було доведено, що аналіз ефекту бозонного помутніння (тенденція бозонів надавати перевагу подіям з усіма частинками в одній половині вихідного масиву безперервного багаточастотного квантового блукання) розрізняє поведінку розрізнюваних і нерозрізнюваних частинок на цій конкретній платформі.[28]
Інший підхід для підтвердження того, що машина для бозонного семплінгу поводиться так, як передбачає теорія, полягає у використанні повністю реконфігуруваних оптичних схем. З широкомасштабними однофотонними та багатофотонними інтерференціями, перевіреними передбачуваними багатомодовими кореляціями в повністю охарактеризованій схемі, обґрунтованим є припущення, що система підтримує правильну роботу, оскільки схема постійно переналаштовується для здійснення випадкової унітарної операції. З цією метою можна використовувати закони квантового придушення (ймовірність певних комбінацій вхід-вихід придушується, коли описується лінійний інтерферометр матриці Фур'є[en] або інших матриць з відповідними симетріями).[33] Ці закони придушення можна ефективно передбачити класичними методами. Цей підхід дозволяє також виключити інші фізичні моделі, такі як стани середнього поля, що імітують деякі колективні властивості багаточастинок (включаючи бозонне помутніння). Повідомляється про реалізацію схеми матриці Фур'є в повністю реконфігурованому 6-модовому пристрої,[9] і експериментальні спостереження за законом придушення були показані для 2-х фотонів у 4- і 8-модових матрицях Фур'є.[34]
Окрім фотонної реалізації завдання бозонного семплінгу, було запропоновано кілька інших установок. Сюди входить, наприклад, кодування бозонів у локальні поперечні фононні режими захоплених іонів. Схема дозволяє детерміновану підготовку та високоефективне зчитування стану Фока відповідного фонона та універсальну маніпуляцію фононними режимами за допомогою поєднання кулонівської взаємодії та індивідуальних фазових зсувів.[35] Ця схема є масштабованою і спирається на недавній прогрес у техніках вловлювання іонів (кілька десятків іонів можуть бути успішно захоплені, наприклад, у лінійних пастках Пола, використовуючи ангармонічні осьові потенціали).
Іншою платформою для реалізації бозонного семплінгу є система взаємодіючих спінів: нещодавнє спостереження показує, що бозонний семплінгу з M частинками в N модах еквівалентна короткочасній еволюції з M збудженнями 2N спінів у XY моделі[en].[36] Тут необхідні кілька додаткових припущень, включаючи ймовірність згрупування малих бозонів та ефективну постселекцію помилок. Однак ця масштабована схема є досить багатообіцяючою у світлі значного розвитку конструкції та маніпуляцій зв'язаними надпровідними кубітами[en], а саме машини D-Wave.
Завдання бозонного семплінгу має особливу схожість із задачею визначення молекулярних вібронних спектрів: можлива модифікація схеми бозонного семплінгу призводить до установки, яка може бути використана для реконструкції профілів Франка — Кондона молекули (для яких в даний час не відомий ефективний класичний алгоритм). Зокрема, зараз завдання полягає у введенні конкретних стиснутих когерентних станів в лінійний інтерферометр, який визначається властивостями молекули, що нас цікавить.[37] Отже, це видатне спостереження викликає інтерес до реалізації завдання бозонного семплінгу, що поширюється далеко за межі фундаментальної основи.
Також було запропоновано використовувати мережу надпровідних резонаторів як інтерферометр пристрою бозонного семплінгу. Це застосування вважається практичним, оскільки невеликі зміни в муфтах між резонаторами змінять результати семплінгу. Таким чином, досягається відчуття зміни параметрів, здатних змінити муфти, при порівнянні результатів вибірки з незмінним еталоном.[38]
Варіанти моделі бозонного семплінгу використовувались для побудови класичних обчислювальних алгоритмів, спрямованих, наприклад, на оцінку певних перманентів матриць (наприклад, перманентів додатно-напіввизначених матриць[en]), пов'язаних до відповідної відкритої задачі в інформатиці[39]) комбінуючи інструменти, властиві квантовій оптиці та теорії складності обчислень.[40]
Грубий бозонний семплінг був запропонований як ресурс рішень та функціональних проблем, які є обчислювально складними, і, отже, можуть мати застосування у криптографії.[41][42]
Гаусів бозонний семплінг розглядали як компонент пошуку для обчислення схильності зв'язування між молекулами, що представляє інтерес для фармакології.[43]
- ↑ Aaronson, Scott; Arkhipov, Alex (2013). The computational complexity of linear optics. Theory of Computing. 9: 143—252. doi:10.4086/toc.2013.v009a004.
- ↑ Troyansky, Lidror; Tishby, Naftali (1996). «Permanent uncertainty: On the quantum evaluation of the determinant and the permanent of a matrix». Proceedings of PhysComp, 1996: 314—318.
- ↑ Quantum computational advantage using photons // Science. — . Архівовано з джерела 15 грудня 2020. Процитовано 8 грудня 2020.
- ↑ а б в Broome, Matthew; Fedrizzi, Alessandro; Rahimi-Keshari, Saleh; Dove, Justin; Aaronson, Scott; Ralph, Timothy; White, Andrew (2013). Photonic boson sampling in a tunable circuit. Science. 339 (6121): 794—798. arXiv:1212.2234. Bibcode:2013Sci...339..794B. doi:10.1126/science.1231440. PMID 23258411.
- ↑ а б в Spring, Justin; Metcalf, Benjamin; Humphreys, Peter; Kolthammer, Steven; Jin, Xian-Min; Barbieri, Marco; Datta, Animesh; Thomas-Peter, Nicholas; Langford, Nathan; Kundys, Dmytro; Gates, James; Smith, Brian; Smith, Peter; Walmsley, Ian (2013). Boson sampling on a photonic chip. Science. 339 (6121): 798—801. arXiv:1212.2622. Bibcode:2013Sci...339..798S. doi:10.1126/science.1231692. PMID 23258407.
- ↑ Szameit, Alexander; Dreisow, Felix; Pertsch, Thomas; Nolte, Stefan; Tünnermann, Andreas (2007). Control of directional evanescent coupling in fs laser written waveguides. Optics Express. 15 (4): 1579—1587. Bibcode:2007OExpr..15.1579S. doi:10.1364/OE.15.001579. PMID 19532390.
- ↑ а б в Tillmann, Max; Dakic, Borivoje; Heilmann, Rene; Nolte, Stefan; Szameit, Alexander; Walther, Philip (2013). Experimental boson sampling. Nature Photonics. 7 (7): 540—544. arXiv:1212.2240. Bibcode:2013NaPho...7..540T. doi:10.1038/nphoton.2013.102.
- ↑ а б в Crespi, Andrea; Osellame, Roberto; Ramponi, Roberta; Brod, Daniel; Galvao, Ernesto; Spagnolo, Nicolò; Vitelli, Chiara; Maiorino, Enrico; Mataloni, Paolo; Sciarrino, Fabio (2013). Integrated multimode interferometers with arbitrary designs for photonic boson sampling. Nature Photonics. 7 (7): 545—549. arXiv:1212.2783. Bibcode:2013NaPho...7..545C. doi:10.1038/nphoton.2013.112.
- ↑ а б в Carolan, Jacques; Harrold, Christopher; Sparrow, Chris та ін. (2015). Universal linear optics. Science. 349 (6249): 711—716. arXiv:1505.01182. doi:10.1126/science.aab3642. PMID 26160375.
- ↑ Scheel, Stefan (2008). Permanents in linear optical networks. Acta Physica Slovaca. 58 (5): 675. arXiv:quant-ph/0406127. Bibcode:2004quant.ph..6127S. doi:10.2478/v10155-010-0092-x.
- ↑ Polynomial-time hierarchy. Complexity Zoo. Архів оригіналу за 14 лютого 2014. Процитовано 24 липня 2022.
- ↑ Bremner, Michael; Jozsa, Richard; Shepherd, Dan (2011). Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. Roy. Soc. A. 467 (2126): 459—472. arXiv:1005.1407. Bibcode:2011RSPSA.467..459B. doi:10.1098/rspa.2010.0301.
- ↑ Aaronson, Scott (2005). Quantum computing, postselection, and probabilistic polynomial-time. Proc. Roy. Soc. A. 461 (2063): 3473—3482. arXiv:quant-ph/0412187. Bibcode:2005RSPSA.461.3473A. doi:10.1098/rspa.2005.1546.
- ↑ Clifford, Peter; Clifford, Raphaël (5 червня 2017). The Classical Complexity of Boson Sampling. arXiv:1706.01260 [cs.DS].
- ↑ Russell, Nicholas; Chakhmakhchyan, Levon; O'Brien, Jeremy; Laing, Anthony (2017). Direct dialling of Haar random unitary matrices. New J. Phys. 19 (3): 033007. arXiv:1506.06220. Bibcode:2017NJPh...19c3007R. doi:10.1088/1367-2630/aa60ed.
- ↑ Arkhipov, Alex; Kuperberg, Greg (2012). The bosonic birthday paradox. Geometry & Topology Monographs. Proceedings of the Freedman Fest. 18: 1—7. arXiv:1106.0849. doi:10.2140/gtm.2012.18.1.
- ↑ Spagnolo, Nicolò; Vitelli, Chiara; Sanson, Linda та ін. (2013). General Rules for Bosonic Bunching in Multimode Interferometers. Phys. Rev. Lett. 111 (13): 130503. arXiv:1305.3188. Bibcode:2013PhRvL.111m0503S. doi:10.1103/PhysRevLett.111.130503. PMID 24116759.
- ↑ Gurvits, Leonid (2005). On the complexity of mixed discriminants and related problems. Mathematical Foundations of Computer Science: 447—458.
- ↑ Lund, Austin; Laing, Anthony; Rahimi-Keshari, Saleh та ін. (2014). Boson sampling from a Gaussian state. Phys. Rev. Lett. 113 (10): 100502. arXiv:1305.4346. Bibcode:2014PhRvL.113j0502L. doi:10.1103/PhysRevLett.113.100502. PMID 25238340.
- ↑ а б Aaronson, Scott. Scattershot BosonSampling: a new approach to scalable BosonSampling experiments. Shtetl-Optimized. Архів оригіналу за 16 грудня 2020. Процитовано 10 грудня 2020.
- ↑ а б в г Bentivegna, Marco; Spagnolo, Nicolo; Vitelli, Chiara; Flamini, Fulvio; Viggianiello, Niko; Latmiral, Ludovico; Mataloni, Paolo; Brod, Daniel; Galvão, Ernesto; Crespi, Andrea; Ramponi, Roberta; Osellame, Roberto; Sciarrino, Fabio (2015). Experimental scattershot boson sampling. Science Advances. 1 (3): e1400255. arXiv:1505.03708. Bibcode:2015SciA....1E0255B. doi:10.1126/sciadv.1400255. PMC 4640628. PMID 26601164.
- ↑ а б Chakhmakhchyan, Levon; Cerf, Nicolas (2017). Boson sampling with Gaussian measurements. Phys. Rev. A. 96 (3): 032326. arXiv:1705.05299. Bibcode:2017PhRvA..96c2326C. doi:10.1103/PhysRevA.96.032326.
- ↑ Chakhmakhchyan, Levon; Cerf, Nicolas (2018). Simulating arbitrary Gaussian circuits with linear optics. Phys. Rev. A. 98 (6): 062314. arXiv:1803.11534. Bibcode:2018PhRvA..98f2314C. doi:10.1103/PhysRevA.98.062314.
- ↑ Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric (2001). A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM. 51 (4): 671—697. CiteSeerX 10.1.1.18.9466. doi:10.1145/1008731.1008738.
- ↑ Rahimi-Keshari, Saleh; Lund, Austin; Ralph, Timothy (2015). What can quantum optics say about computational complexity theory?. Phys. Rev. Lett. 114 (6): 060501. arXiv:1408.3712. Bibcode:2015PhRvL.114f0501R. doi:10.1103/PhysRevLett.114.060501. PMID 25723196.
- ↑ Rahimi-Keshari, Saleh; Ralph, Timothy; Carlton, Caves (2016). Efficient classical simulation of quantum optics. Physical Review X. 6 (2): 021039. arXiv:1511.06526. Bibcode:2016PhRvX...6b1039R. doi:10.1103/PhysRevX.6.021039.
- ↑ а б в Spagnolo, Nicolo; Vitelli, Chiara; Bentivegna, Marco; Brod, Daniel; Crespi, Andrea; Flamini, Fulvio; Giacomini, Sandro; Milani, Giorgio; Ramponi, Roberta; Mataloni, Paolo; Osellame, Roberto; Galvão, Ernesto; Sciarrino, Fabio (2014). Experimental validation of photonic boson sampling. Nature Photonics. 8 (8): 615—620. arXiv:1311.1622. Bibcode:2014NaPho...8..615S. doi:10.1038/nphoton.2014.135.
- ↑ а б в г Carolan, Jacques; Meinecke, Jasmin; Shadbolt, Pete; Russell, Nicholas; Ismail, Nur; Wörhoff, Kerstin; Rudolph, Terry; Thompson, Mark; O'Brien, Jeremy; Matthews, Jonathan; Laing, Anthony (2014). On the experimental verification of quantum complexity in linear optics. Nature Photonics. 8 (8): 621—626. arXiv:1311.2913. Bibcode:2014NaPho...8..621C. doi:10.1038/nphoton.2014.152.
- ↑ Motes, Keith; Gilchrist, Alexei; Dowling, Jonathan; Rohde, Peter (2014). Scalable boson sampling with time-bin encoding using a loop-based architecture. Phys. Rev. Lett. 113 (12): 120501. arXiv:1403.4007. Bibcode:2014PhRvL.113l0501M. doi:10.1103/PhysRevLett.113.120501. PMID 25279613.
- ↑ Pant, Mihir; Englund, Dirk (2016). High dimensional unitary transformations and boson sampling on temporal modes using dispersive optics. Physical Review A. 93 (4): 043803. arXiv:1505.03103. Bibcode:2016PhRvA..93d3803P. doi:10.1103/PhysRevA.93.043803.
- ↑ Gogolin, C.; Kliesch, M.; Aolita, L.; Eisert, J. (2013). Boson-Sampling in the light of sample complexity. arXiv:1306.3995 [quant-ph].
- ↑ Aaronson, Scott; Arkhipov, Alex (2013). BosonSampling is far from uniform. arXiv:1309.7460 [quant-ph].
- ↑ Tichy, Malte; Mayer, Klaus; Buchleitner, Andreas; Mølmer, Klaus (2014). Stringent and Efficient Assessment of Boson-Sampling Devices. Phys. Rev. Lett. 113 (2): 020502. arXiv:1312.3080. Bibcode:2014PhRvL.113b0502T. doi:10.1103/PhysRevLett.113.020502. PMID 25062152.
- ↑ Crespi, Andrea; Osellame, Roberto; Ramponi, Roberta та ін. (2016). Quantum suppression law in a 3-D photonic chip implementing the fast Fourier transform. Nature Communications. 7: 10469. arXiv:1508.00782. Bibcode:2015arXiv150800782C. doi:10.1038/ncomms10469. PMC 4742850. PMID 26843135.
- ↑ Shen, C.; Zhang, Z.; Duan, L.-M. (2014). Scalable implementation of boson sampling with trapped ions. Phys. Rev. Lett. 112 (5): 050504. arXiv:1310.4860. Bibcode:2014PhRvL.112e0504S. doi:10.1103/PhysRevLett.112.050504. PMID 24580579.
- ↑ Peropadre, Borja; Aspuru-Guzik, Alan; Garcia-Ripoll, Juan (2015). Spin models and boson sampling. arXiv:1509.02703 [quant-ph].
- ↑ Huh, Joonsuk; Giacomo Guerreschi, Gian; Peropadre, Borja; McClean, Jarrod; Aspuru-Guzik, Alan (2015). Boson sampling for molecular vibronic spectra. Nature Photonics. 9 (9): 615—620. arXiv:1412.8427. Bibcode:2015NaPho...9..615H. doi:10.1038/NPHOTON.2015.153.
- ↑ Goldstein, Samuel; Korenblit, Simcha; Bendor, Ydan; You, Hao; Geller, Michael R.; Katz, Nadav (17 січня 2017). Decoherence and interferometric sensitivity of boson sampling in superconducting resonator networks. Phys. Rev. B. 95 (2): 020502. arXiv:1701.00714. Bibcode:2017PhRvB..95b0502G. doi:10.1103/PhysRevB.95.020502.
- ↑ Див. проблему (4) у Shtetl Optimized: Introducing some British people to P vs. NP. Архів оригіналу за 8 листопада 2020. Процитовано 13 грудня 2020.
- ↑ Chakhmakhchyan, Levon; Cerf, Nicolas; Garcia-Patron, Raul (2017). A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices. Phys. Rev. A. 96 (2): 022329. arXiv:1609.02416. Bibcode:2017PhRvA..96b2329C. doi:10.1103/PhysRevA.96.022329.
- ↑ Nikolopoulos, Georgios M.; Brougham, Thomas (2016). Decision and function problems based on boson sampling. Physical Review A. 94: 012315. arXiv:1607.02987. doi:10.1103/PhysRevA.94.012315.
- ↑ Nikolopoulos, Georgios M. (2019). Cryptographic one-way function based on boson sampling. Quantum Information Processing. 18 (8): 259. arXiv:1607.02987. doi:10.1007/s11128-019-2372-9.
- ↑ Banchi, Leonardo; Fingerhuth, Mark; Babej, Tomas; Ing, Christopher; Arrazola, Juan Miguel (2020). Molecular docking with Gaussian Boson Sampling. Science Advances. 6 (23). doi:10.1126/sciadv.aax1950.
- QUCHIP project [Архівовано 3 квітня 2022 у Wayback Machine.]
- Quantum Information Lab — Sapienza: video on boson sampling [Архівовано 17 січня 2021 у Wayback Machine.]
- Quantum Information Lab — Sapienza: video on scattershot boson sampling [Архівовано 31 липня 2020 у Wayback Machine.]
- The Qubit Lab — Boson Sampling