Бозонний семплінг — це обмежена модель неуніверсальних квантових обчислень, запроваджена С. Ааронсоном та А. Архіповим після оригінальної роботи Л. Троянського та Н. Тишбі, яка досліджувала можливе використання розсіювання бозонів для оцінки очікуваних значень перманентів матриць.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. Модель складається з висновування з розподілу ймовірностей однакових бозонів, розсіяних лінійним інтерферометром. Хоча проблема чітко визначена для будь-яких бозонових частинок, її фотонна версія в даний час розглядається як найбільш перспективна платформа для масштабованої реалізації пристрою бозонного семплінгу, що робить її неуніверсальним підходом до лінійних оптичних квантових обчислень. Більше того, хоча схема універсального бозонного семплінгу не є загальновідомою, вона реалізує обчислювальні завдання, які важко реалізувати на класичних комп'ютерах, використовуючи набагато менше фізичних ресурсів, ніж повна лінійна оптична квантова обчислювальна установка. Як було повідомлено командою вчених з Університету науки і техніки Китаю () квантова перевага була продемострована саме з використанням бозонного семплінгу.
Опис Розглядається багатомодовий лінійно-оптичний ланцюг із N мод, в який вводять M нерозрізнених одиночних фотонів (N>M). Фотонна реалізація завдання бозонного семплінгу складається з генерації вибірки з розподілу ймовірностей однофотонних вимірювань на виході схеми. Зокрема, для цього потрібні надійні джерела одиночних фотонів (в даний час найпоширенішими є кристали з низхідним параметричним розсіянням), а також лінійний інтерферометр. Останні можуть бути виготовлені, наприклад, з дільниками променів із зплавлених волокон, за допомогою інтегрованих інтерферометрів на основі кремнезему на кремнії або нанесених лазером інтегрованих інтерферометрів, або з оптичними чіпами з електричним та оптичним з'єднанням. Нарешті, схема також вимагає високоефективних детекторів для підрахунку одиничних фотонів, таких як такі, що базуються на зміщених струмом надпровідних нанопроводах, які виконують вимірювання на виході схеми. Отже, виходячи з цих трьох складових, установка бозонного семплінгу не вимагає жодних допоміжних засобів, адаптивних вимірювань або операцій заплутування, як це робиться, наприклад, в універсальній оптичній схемі за Найлом, Лафламме та Мілберном (схема KLM). Це робить його не універсальною моделлю квантових обчислень і зменшує кількість фізичних ресурсів, необхідних для її практичної реалізації.
Зокрема, припустимо, що лінійний інтерферометр описується унітарною матрицею N×N , який виконує лінійне перетворення операторів народження (знищення) вхідних мод схеми:
Тут i (j) позначають вхідні (вихідні) моди, а позначає оператори народження (знищення) вихідних мод (i, j=1,…, N). З іншого боку, інтерферометр, що характеризується унітарною матрицею , природно виконує перетворення над вхідними станами. Більше того, між унітарними матрицями існує гомоморфізм, а останнє перетворення виконується у експоненціально великому гільбертовому просторі системи: простий підрахунок аргументів показуює, що розмір гільбертового простору, що відповідає системі нерозрізнених фотонів M, розподілених між N модами задається біноміальним коефіцієнтом (зауважте, що хоча цей гомоморфізм існує, не всі значення можливі). А саме, припустимо, в інтерферометр вводиться вхідний стан поодиноких фотонів з — кількість фотонів, що вводяться в k-у моду). Потім стан на виході схеми можна записати як Простий спосіб зрозуміти гомоморфізм між та наступний.
Визначимо ізоморфізм для базових станів: , і отримаємо наступний результат:
Отже, ймовірність виявлення фотонів на k-ій вихідній моді подано як
У наведеному вище виразі розшифровується як перманентів матриці яка отримана з унітарної матриці повторенням разів її i-го стовпчика і разів її j-го рядка. Зазвичай в контексті проблеми бозонного семплінгу вхідний стан приймається у стандартній формі, що позначається як для якого в кожну з перших М мод інтерферометра вводиться один фотон. У цьому випадку наведений вище вираз звучить так:
де матриця отримана з збереженням перших М стовпців і повторенням разів її j-го рядка. Згодом завдання бозонного семплінгу полягає у отриманні точних або приблизних виборок з вищезазначеного розподілу вихідних даних, враховуючи унітарну матрицю , що описує лінійно-оптичну схему як вхідні дані. Як докладно описано нижче, поява перманента у відповідних статистичних даних однофотонних вимірювань сприяє складності проблеми бозонного семплінгу.
Складність проблеми Основною причиною зростаючого інтересу до моделі бозонного семплінгу є те, що, незважаючи на те, що вона не є універсальною, існує впевнена думка, що вона виконує обчислювальну задачу, яка є нерозв'язною для класичного комп'ютера. Однією з основних причин цього є те, що розподіл ймовірностей, з яким пристрій для бозонного семплінгу повинен брати вибірки, пов'язаний з перманентом комплексних матриць. в загальному випадку є надзвичайно важким завданням: воно потрапляє до класу складності . Більше того, його апроксимація в межах мультиплікативної помилки також є #P-складною проблемою.
Усі сучасні докази складності моделювання бозонного семплінгу на класичному комп'ютері покладаються на сильні обчислювальні наслідки, які могло б мати його ефективне моделювання за допомогою класичного алгоритму. А саме ці докази показують, що ефективне класичне моделювання означало б крах поліноміальної ієрархії класів складності до її третього рівня — можливість, яка вважається дуже малоймовірною спільнотою інформатиків через її сильні обчислювальні наслідки (відповідно сильні наслідки проблеми P = NP).
Точний семплінг Доказ складності точної проблеми бозонного семплінгу можна отримати двома різними шляхами. Зокрема, перший використовує інструменти теорії складності обчислень та поєднує в собі наступні два факти:
Наближення ймовірності конкретного результату вимірювання на виході лінійного інтерферометра з точністю до мультиплікативної константи є проблемою #P-складною (через складність перманента) Якщо б існував класичний алгоритм точного бозонного семплінгу з поліноміальним часом, то вищевказана ймовірність могла бути наближена з точністю до мультипликативної константи в класі складності BPPNP, тобто в межах третього рівня ієрархії поліноміальної складності
Поєднання цих двох фактів разом із призводить до розпаду ієрархії поліноміальної складності, що, як зазначалось вище, малоймовірно. Це призводить до висновку, що не існує класичного алгоритму з поліноміальним часом виконання для точної задачі бозонного семплінгу.
З іншого боку, альтернативний доказ натхненний подібним результатом для іншої обмеженої моделі квантових обчислень — моделі миттєвих квантових обчислень. А саме, в доказі використовується схема KLM, яка говорить, що лінійна оптика з адаптивними вимірюваннями є універсальною для класу . Він також спирається на такі факти:
Лінійна оптика з постселективними вимірюваннями є універсальною для , тобто квантового класу поліномного часу з постселекцією (прямий наслідок конструкції KLM) Клас PostBQP еквівалентний PP (тобто клас імовірнісного поліноміального часу): PostBQP = PP Існування класичного алгоритму бозонного семплінгу передбачає моделювання постселективної лінійної оптики в класі PostBPP (тобто класичного поліноміального часу з постселекцією, відомого також як клас BPPpath)
Знову ж таки, поєднання цих трьох результатів, як і в попередньому випадку, призводить до розпаду ієрархії поліноміальної складності. Це робить існування класичного алгоритму поліноміального часу для точної проблеми бозонного семплінгу надзвичайно малоймовірним.
Найкращий запропонований класичний алгоритм для точного бозонного семплінгу працює за час для системи з n фотонів та m мод. Цей алгоритм призводить до оцінки у 50 фотонів, необхідних для демонстрації квантової переваги за допомогою бозонного семплінгу. Існує також реалізація з відкритим вихідним кодом мовою програмування R.
Приблизний семплінг Наведені вище докази складності не застосовуються до реалістичної реалізації пристрою для бозонного семплінгу через недосконалість будь-якої експериментальної установки (включаючи наявність шуму, декогеренцію, втрату фотонів тощо). Тому для практичних потреб потрібно відповідати складності для відповідного наближеного завдання. Останнє складається з вибірки з розподілу ймовірностей, що є -наближеною до одного з поданих , через . Тоді розуміння складності цієї проблеми спирається на кілька додаткових припущень, а також на дві поки не доведені гіпотези.
Зокрема, докази точної задачі бозонного семплінгу тут не можуть бути застосовані безпосередньо, оскільки вони засновані на #P-складності оцінки експоненціально-малої ймовірності конкретного результату вимірювання. Таким чином, якщо той, хто виконує семплінг, «знав» що з ми хотіли оцінити, тоді він міг би визнати його пошкодженням (якщо завдання є приблизним). Ось чому, ідея полягає в тому, щоб «приховати» вищевказану ймовірність у випадковій унітарній матриці N×N. Це можна зробити, знаючи, що будь-яка підматриця M×M унітарної матриці , випадково обраних відповідно до міри Хаара, близьких за відстанню варіації до матриці незалежних однаково розподілених комплексних випадкових змінних з нормальним розподілом, за умови, що M ≤ N1/6 (випадкові матриці Хаара можуть бути безпосередньо реалізовані в оптичних ланцюгах шляхом відображення незалежних функцій щільності ймовірності для їх параметрів на компоненти оптичного ланцюга, тобто дільники променя та фазоперетворювачі). Отже, якщо лінійна оптична схема реалізує випадкову унітарну матрицю Хаара, змагальна особа, що виконує вибірку, не зможе визначити, яка з ймовірностей, яких експоненційно багато, нас цікавить і, отже, не зможемо уникнути його оцінки. В цьому випадку пропорційна квадрату абсолютного значення перманента матриці M×M незалежних однаково розподілених гауссових величин, внесених всередину Ці аргументи підводять нас до першої гіпотези доказу складності наближеної задачі бозонного семплінгу — гіпотези перманента нормально розподілених величин: Апроксимація перманента матриці з незалежних однаково розподілених величин з нормальним розподілом з точністю до мультиплікативної помилки — це #P-складне завдання.
Більше того, наведену вище гіпотезу можна пов'язати з оцінкою , якій пропорційна дана ймовірність конкретного результату вимірювання. Однак для встановлення цього зв'язку потрібно спиратися на іншу гіпотезу — гіпотезу про постійну антиконцентрацію: Існує такий поліном Q, що для будь-якого M і δ> 0 ймовірність над матрицями M × M виконується наступна нерівність, менша ніж δ:
Використовуючи вищезазначені дві гіпотези (які мають декілька свідчень істинності), остаточне підтвердження врешті-решт стверджує, що існування класичного алгоритму поліноміального часу для задачі приблизного бозонного семплінгу передбачає крах ієрархії поліноміальної складності. Варто також згадати ще один факт, важливий для доказу цього твердження, а саме так званий парадокс бозонного дня народження (за аналогією з відомим парадоксом днів народження). Останній стверджує, що якщо M однакових бозонів розпорошені між N≫M 2 модами лінійного інтерферометра без двох бозонів в одній моді, то з високою ймовірністю двох бозонів також не буде знайдено в одній вихідній моді. Ця властивість спостерігалась експериментально з двома і трьома фотонами в інтегрованих інтерферометрах до 16 мод. З одного боку, ця особливість полегшує реалізацію обмеженого пристрою для бозонного семплінгу. А саме, якщо ймовірність мати більше одного фотона на виході лінійного оптичного ланцюга є незначною, більше не потрібно детекторів, що розпізнають число фотонів: детекторів включення-вимкнення буде достатньо для реалізації установки.