Квантова перевага в квантових обчисленнях на основі часових плоских вимірювань

Перевидано Платоном

читають: 0

Майкл де Олівейра^1,2,3, Луїс С. Барбоза^1,2,3та Ернесто Ф. Гальвао^3,4

¹Університет Мінью, факультет комп’ютерних наук, Брага, Португалія
²INESC TEC, Брага, Португалія
³Міжнародна Іберійська Нанотехнологічна Лабораторія (INL) Av. Местре Хосе Вейга, 4715-330, Брага, Португалія
⁴Instituto de Física, Universidade Federal Fluminense Av. гал. Milton Tavares de Souza s/n, Niterói, RJ, 24210-340, Brazil

Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на SciRate.

абстрактний

Було показано, що кілька класів квантових схем забезпечують квантову обчислювальну перевагу за певних припущень. Дослідження все більш обмежених класів квантових схем, здатних до квантової переваги, мотивується можливими спрощеннями в експериментальних демонстраціях. У цій статті ми досліджуємо ефективність квантових обчислень на основі вимірювань із повністю плоским часовим упорядкуванням вимірювань. Ми пропонуємо нові конструкції для детермінованого обчислення довільних булевих функцій, спираючись на кореляції, присутні в мультикубітових станах Грінбергера, Хорна та Цайлінгера (GHZ). Ми характеризуємо необхідну складність вимірювань за допомогою ієрархії Кліффорда, а також загалом зменшуємо кількість необхідних кубітів відносно попередніх конструкцій. Зокрема, ми визначаємо сімейство булевих функцій, для яких можлива детермінована оцінка з використанням неадаптивного MBQC, яка має квантову перевагу в ширині та кількості вентилів порівняно з класичними схемами.

Рекомендоване зображення: неадаптивну модель MBQC можна описати за допомогою спеціальної обчислювальної архітектури, яка розділена на процес підготовки квантового стану, процедуру вимірювання та пов’язану до- та посткласичну лінійну обробку (угорі ліворуч). Ця модель полегшує вивчення вимог до ресурсів для оцінки симетричних булевих функцій з точки зору асимптотичної кількості кубітів і необхідних операцій (угорі праворуч). Ці елементи розкривають наші основні результати [внизу], які сформульовані для стандартних класичних і квантових наборів вентилів і описів схем [внизу зліва], що характеризують набір булевих функцій, які демонструють квантову перевагу щодо кількості вентилів і ширини ланцюги (праворуч внизу).

[Вбудоване вміст]

► Дані BibTeX

@article{Oliveira2024quantumadvantagein, doi = {10.22331/q-2024-04-09-1312}, url = {https://doi.org/10.22331/q-2024-04-09-1312}, title = {Квантова перевага в квантових обчисленнях на основі часових плоских вимірювань}, автор = {Oliveira, Michael de and Barbosa, Lu{'{i}}s S. and Galv{~{a}}o, Ernesto F.}, журнал = {{Quantum}}, issn = {2521-327X}, видавець = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, обсяг = {8}, сторінки = {1312}, місяць = квітень, рік = {2024} }

► Список літератури

[1] Скотт Ааронсон, ДеВон Інграм і Вільям Кречмер. «Акробатика BQP». Шачар Ловетт, редактор, 37-а конференція з обчислювальної складності (CCC 2022). Том 234 Leibniz International Proceedings in Informatics (LIPIcs), сторінки 20:1–20:17. Дагштуль, Німеччина (2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https:///doi.org/10.4230/LIPIcs.CCC.2022.20

[2] Річард Йоза та Ной Лінден. «Про роль заплутаності в квантово-обчислювальному прискоренні». Праці Лондонського королівського товариства. Серія A: Математичні, фізичні та інженерні науки 459, 2011–2032 (2003).
https: / / doi.org/ 10.1098 / rspa.2002.1097

[3] Марк Ховард, Джоел Уоллман, Віктор Вейтч і Джозеф Емерсон. «Контекстуальність забезпечує «магію» для квантових обчислень». Nature 510, 351–355 (2014).
https: / / doi.org/ 10.1038 / nature13460

[4] Хуан Бермехо-Вега, Ніколас Дельфосс, Ден Е. Браун, Сіхан Окей і Роберт Рауссендорф. «Контекстуальність як ресурс для моделей квантового обчислення з кубітами». фіз. Преподобний Летт. 119, 120505 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.120505

[5] Ернесто Ф. Гальван. «Дискретні функції Вігнера та квантове прискорення обчислень». фіз. Rev. A 71, 042302 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.042302

[6] А. Марі та Я. Айзерт. «Позитивні функції Вігнера роблять класичне моделювання квантових обчислень ефективним». фіз. Преподобний Летт. 109, 230503 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.230503

[7] Лов К. Гровер. «Переваги суперпозиції». Наука 280, 228–228 (1998).
https: / / doi.org/ 10.1126 / science.280.5361.228

[8] Роберт Рауссендорф і Ганс Дж. Брігель. «Односторонній квантовий комп’ютер». фіз. Преподобний Летт. 86, 5188–5191 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[9] Маартен Ван ден Нест, Акімаса Міяке, Вольфганг Дюр і Ганс Дж. Брігель. «Універсальні ресурси для квантових обчислень на основі вимірювань». фіз. Преподобний Летт. 97, 150504 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.150504

[10] Джанет Андерс і Ден Е. Браун. «Обчислювальна потужність кореляцій». фіз. Преподобний Летт. 102, 050502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.050502

[11] Вінсент Данос і Елхам Кашефі. “Детермінізм в односторонній моделі”. фіз. Rev. A 74, 052310 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052310

[12] Деніел Е Браун, Елхам Кашефі, Мехді Мхалла та Саймон Пердрікс. «Узагальнений потік і детермінізм у квантових обчисленнях на основі вимірювань». New Journal of Physics 9, 250 (2007).
https://doi.org/10.1088/1367-2630/9/8/250

[13] Майкл Бремнер, Ешлі Монтанаро та Ден Шеперд. «Складність середнього випадку проти наближеного моделювання комутуючих квантових обчислень». фіз. Преподобний Летт. 117, 080501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501

[14] Метті Дж. Хобан, Джоел Дж. Уолман, Хуссейн Анвар, Найрі Ашер, Роберт Рауссендорф і Ден Е. Браун. «Класичне обчислення на основі вимірювань». фіз. Преподобний Летт. 112, 140505 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.112.140505

[15] Майкл Дж. Бремнер, Ешлі Монтанаро та Ден Дж. Шеферд. «Досягнення квантової переваги за допомогою розріджених і шумних комутуючих квантових обчислень». Квант 1, 8 (2017).
https://doi.org/10.22331/q-2017-04-25-8

[16] Леонардо Ново, Хуані Бермехо-Вега та Рауль Гарсія-Патрон. «Квантова перевага вимірювань енергії багатотільних квантових систем». Квант 5, 465 (2021).
https://doi.org/10.22331/q-2021-06-02-465

[17] Масахіто Хаясі та Юкі Такеучі. «Перевірка комутуючих квантових обчислень за допомогою оцінки точності зважених станів графа». New Journal of Physics 21, 93060 (2019).
https://doi.org/10.1088/1367-2630/ab3d88

[18] Хуан Бермехо-Вега, Домінік Ханглейтер, Мартін Шварц, Роберт Рауссендорф і Єнс Айзерт. «Архітектури для квантового моделювання, які демонструють квантове прискорення». фіз. Ред. X 8, 021010 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.021010

[19] Джейкоб Міллер, Стівен Сандерс та Акімаса Міяке. «Квантова перевага в обчисленнях на основі вимірювань постійного часу: уніфікована архітектура для вибірки та перевірки». фіз. Rev. A 96, 062320 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062320

[20] Метті Дж. Хобан, Ерл Т. Кемпбелл, Клеархос Лукопулос і Ден Е. Браун. «Квантові обчислення на основі неадаптивних вимірювань і багатосторонні нерівності Белла». New Journal of Physics 13, 23014 (2011).
https://doi.org/10.1088/1367-2630/13/2/023014

[21] Рюхей Морі. “Періодичне представлення Фур’є булевих функцій”. Квантова інформація. обчис. 19, 392–412 (2019). url: https:///dl.acm.org/doi/abs/10.5555/3370251.3370253.
https:///dl.acm.org/doi/abs/10.5555/3370251.3370253

[22] Маркус Фрембс, Сем Робертс, Ерл Т. Кемпбелл і Стівен Д. Бартлетт. «Ієрархії ресурсів для квантових обчислень на основі вимірювань». New Journal of Physics 25, 013002 (2023).
https:///doi.org/10.1088/1367-2630/acaee2

[23] Єлена Макепранг, Даніель Бхатті, Метті Дж. Хобан і Стефані Барз. «Потужність qutrits для неадаптивних квантових обчислень на основі вимірювань». New Journal of Physics 25, 073007 (2023).
https:///doi.org/10.1088/1367-2630/acdf77

[24] Деніел Коллінз, Ніколас Гісін, Санду Попеску, Девід Робертс і Валеріо Скарані. «Нерівності дзвонового типу для виявлення справжньої нероздільності тіла $mathit{n}$». фіз. Преподобний Летт. 88, 170405 (2002).
https: / / doi.org/ 10.1103 / PhysRevLett.88.170405

[25] Ніколас Бруннер, Даніель Кавальканті, Стефано Піроніо, Валеріо Скарані та Стефані Венер. “Нелокальність Белла”. Rev. Mod. фіз. 86, 419–478 (2014).
https: / / doi.org/ 10.1103 / RevModPhys.86.419

[26] Дмитро Кравченко. «Квантові ігри, квантові стани, їх властивості та застосування». кандидатська дисертація. Latvijas Universitāte. (2013).

[27] Вільям Слофстра. «Нижні межі заплутування, необхідні для гри в нелокальні ігри XOR». Журнал математичної фізики 52, 102202 (2011).
https: / / doi.org/ 10.1063 / 1.3652924

[28] Андріс Амбайніс, Яніс Іраідс, Дмитро Кравченко та Мадарс Вірза. «Переваги квантових стратегій у випадкових симетричних xor іграх». Антонін Кучера, Томас А. Гензінгер, Ярослав Нешетрил, Томаш Войнар і Девід Антош, редактори, Математичні та інженерні методи в інформатиці. Сторінки 57–68. Берлін, Гейдельберг (2013). Шпрінгер Берлін Гейдельберг.
https://doi.org/10.1007/978-3-642-36046-6_7

[29] Андріс Амбайніс і Яніс Ірайдс. «Доказова перевага квантових стратегій у випадкових симетричних іграх XOR». У Simone Severini та Fernando Brandao, редактори, 8-а конференція з теорії квантових обчислень, комунікації та криптографії (TQC 2013). Том 22 Leibniz International Proceedings in Informatics (LIPIcs), сторінки 146–156. Дагштуль, Німеччина (2013). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https:///doi.org/10.4230/LIPIcs.TQC.2013.146

[30] Семюел Маркович і Бенні Резнік. “Наслідки складності зв’язку в багатосторонніх системах”. фіз. Rev. A 77, 032120 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.032120

[31] Марчін Павловський, Томаш Патерек, Дагомір Кашликовскі, Валеріо Скарані, Андреас Вінтер і Марек Жуковскі. “Інформаційна причинність як фізичний принцип”. Nature 461, 1101–1104 (2009).
https: / / doi.org/ 10.1038 / nature08400

[32] Санду Попеску та Даніель Рорліх. “Квантова нелокальність як аксіома”. Основи фізики 24, 379–385 (1994).
https: / / doi.org/ 10.1007 / BF02058098

[33] Джонатан Барретт, Ной Лінден, Серж Массар, Стефано Піроніо, Санду Попеску та Девід Робертс. “Нелокальні кореляції як інформаційно-теоретичний ресурс”. фіз. Rev. A 71, 022101 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.022101

[34] А. А. Разборов. “Квантова комунікаційна складність симетричних предикатів”. Известия: Математика 67, 145 (2003).
https://doi.org/10.1070/IM2003v067n01ABEH000422

[35] Чжицян Чжан і Яоюнь Ши. “Комунікаційні складності симетричних функцій XOR”. Квантова інформація та обчислення 9, 255–263 (2009). url: https:///dl.acm.org/doi/abs/10.5555/2011781.2011786.
https:///dl.acm.org/doi/abs/10.5555/2011781.2011786

[36] П'єр Боттерон. «Нелокальні ящики та комунікаційна складність». Магістерська робота. Університет Поля Сабатьє Тулуза III. (2022). url: https:///pierre-botteron.github.io/Articles/2022-06-MSc-Thesis.pdf.
https:///pierre-botteron.github.io/Articles/2022-06-MSc-Thesis.pdf

[37] Квангіл Бе і Вонмін Сон. “Узагальнені критерії нелокальності за кореляційної симетрії”. фіз. Rev. A 98, 022116 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.022116

[38] Маркус Фрембс, Сем Робертс і Стівен Д. Бартлетт. «Контекстуальність як ресурс для квантових обчислень на основі вимірювань за межами кубітів». New Journal of Physics 20, 103011 (2018).
https:///doi.org/10.1088/1367-2630/aae3ad

[39] Сергій Бравий, Девід Госсет і Роберт Кеніг. «Квантова перевага з неглибокими ланцюгами». Наука 362, 308–311 (2018).
https:///doi.org/10.1126/science.aar3106

[40] Деніел Грієр і Люк Шеффер. «Інтерактивні неглибокі схеми Кліффорда: квантова перевага проти NC¹ і не тільки». У матеріалах 52-го щорічного симпозіуму ACM SIGACT з теорії обчислень. Сторінки 875–888. STOC 2020Нью-Йорк, Нью-Йорк, США (2020). Асоціація обчислювальної техніки.
https: / / doi.org/ 10.1145 / 3357713.3384332

[41] Лібор Каха, Ксав'є Койтекс-Рой та Роберт Кеніг. «Телепортація з одним кубітом забезпечує квантову перевагу» (2022). arXiv:2209.14158.
arXiv: 2209.14158

[42] Франсуа Ле Галль. «Квантова перевага в середньому випадку з неглибокими ланцюгами». Амір Шпілька, редактор, 34-та конференція з обчислювальної складності (CCC 2019). Том 137 Leibniz International Proceedings in Informatics (LIPIcs), сторінки 21:1—-21:20. Дагштуль, Німеччина (2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:///doi.org/10.4230/LIPIcs.CCC.2019.21

[43] Меттью Кудрон, Джалекс Старк і Томас Відік. «Торгівля місцевістю для часу: сертифікована випадковість із низьких ланцюгів». Повідомлення в математичній фізиці 382, 49–86 (2021).
https: / / doi.org/ 10.1007 / s00220-021-03963-w

[44] Сергій Бравий, Девід Госсет, Роберт Кеніг і Марко Томамічел. «Квантова перевага з шумними мілкими ланцюгами». Nature Physics 16, 1040–1045 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

[45] Ацуя Хасеґава та Франсуа Ле Гал. «Квантова перевага з неглибокими ланцюгами за умов довільної корупції». У Hee-Kap Ahn і Kunihiko Sadakane, редактори, 32-й Міжнародний симпозіум з алгоритмів і обчислень (ISAAC 2021). Том 212 Leibniz International Proceedings in Informatics (LIPIcs), сторінки 74:1–74:16. Дагштуль, Німеччина (2021). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https:///doi.org/10.4230/LIPIcs.ISAAC.2021.74

[46] Адам Бене Воттс, Робін Котарі, Люк Шеффер і Авішай Тал. «Експоненціальне розділення між неглибокими квантовими ланцюгами та необмеженими неглибокими класичними ланцюгами». У матеріалах 51-го щорічного симпозіуму ACM SIGACT з теорії обчислень. Сторінки 515–526. STOC 2019Нью-Йорк, Нью-Йорк, США (2019). Асоціація обчислювальної техніки.
https: / / doi.org/ 10.1145 / 3313276.3316404

[47] Наталі Пархем. «Про потужність і обмеження неглибоких квантових схем». Магістерська робота. Університет Ватерлоо. (2022). url: https:///uwspace.uwaterloo.ca/handle/10012/18702.
https:///uwspace.uwaterloo.ca/handle/10012/18702

[48] Дмитро Маслов, Джин-Сун Кім, Сергій Бравий, Теодор Дж. Йодер і Сара Шелдон. «Квантова перевага для обчислень з обмеженим простором». Nature Physics 17, 894–897 (2021).
https://doi.org/10.1038/s41567-021-01271-7

[49] Фарід Аблаєв, Аїда Гайнутдінова, Марек Карпінскі, Крістофер Мур та Крістофер Поллетт. “Про обчислювальну потужність імовірнісної та квантової розгалуженої програми”. Інформація та обчислення 203, 145–162 (2005).
https:///doi.org/10.1016/j.ic.2005.04.003

[50] Д. Шеперд і М. Дж. Бремнер. “Тимчасово неструктуроване квантове обчислення”. Праці Лондонського королівського товариства, серія A 465, 1413–1439 (2009).
https: / / doi.org/ 10.1098 / rspa.2008.0443

[51] Деніел М. Грінбергер, Майкл А. Хорн і Антон Цайлінгер. «Вихід за межі теореми Белла». У Менасі Кафатосі, редакторі, Теорема Белла, Квантова теорія та концепції Всесвіту. Сторінки 69–72. Дордрехт (1989). Springer Нідерланди.
https://doi.org/10.1007/978-94-017-0849-4_10

[52] Діого Крус, Ромен Фурньє, Фаб’єн Греміон, Алікс Жаннеро, Кенічі Комагата, Тара Тошич, Ярла Тісбруммель, Чун Лам Чан, Ніколас Макріс, Марк-Андре Дюпертюі та Клеман Жаверзак-Галі. «Ефективні квантові алгоритми для станів GHZ і W та їх реалізація на квантовому комп’ютері IBM». Advanced Quantum Technologies 2, 1900015 (2019).
https:///doi.org/10.1002/qute.201900015

[53] Р. Ф. Вернер і М. М. Вольф. «Кореляційні нерівності для двох дихотомічних спостережуваних на один сайт». фіз. Rev. A 64, 032112 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.032112

[54] Райан О'Доннелл. “Аналіз булевих функцій”. Cambridge University Press. (2014). url: http:///www.cs.cmu.edu/ ./odonnell/papers/Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf.
http://www.cs.cmu.edu/~./odonnell/papers/Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf

[55] Анастасія Чистопольська та Володимир Васильович Подольський. «Складність дерева рішень щодо парності більша, ніж гранулярність» (2018). arXiv:1810.08668.
arXiv: 1810.08668

[56] А Канто і М Відео. “Симетричні булеві функції”. IEEE Transactions on Information Theory 51, 2791–2811 (2005).
https:///doi.org/10.1109/TIT.2005.851743

[57] Ларрі Дж. Стокмайер. “Про комбінаційну складність деяких симетричних булевих функцій”. Теорія математичних систем 10, 323–336 (1976).
https: / / doi.org/ 10.1007 / BF01683282

[58] Р. Ф. Арнольд і М. А. Харрісон. “Алгебраїчні властивості симетричних і частково симетричних булевих функцій”. IEEE Transactions on Electronic Computers EC-12, 244–251 (1963).
https:///doi.org/10.1109/PGEC.1963.263535

[59] Брейкен і Барт Преніл. “Про алгебраїчну імунність симетричних булевих функцій”. У Subhamoy Maitra, CE Veni Madhavan і Ramarathnam Venkatesan, редактори, Progress in Cryptology – INDOCRYPT 2005. Том 3797 конспектів лекцій з інформатики, сторінки 35–48. Берлін, Гейдельберг (2005). Шпрінгер Берлін Гейдельберг.
https:///doi.org/10.1007/11596219_4

[60] Гаррі Бурман і Рональд де Вольф. «Міри складності та складність дерева рішень: опитування». Теоретична інформатика 288, 21–43 (2002).
https://doi.org/10.1016/S0304-3975(01)00144-X

[61] Метью Емі, Дмитро Маслов, Мікеле Моска та Мартін Роттлер. «Алгоритм зустрічі посередині для швидкого синтезу квантових схем з оптимальною глибиною». IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32, 818–830 (2013).
https: / / doi.org/ 10.1109 / TCAD.2013.2244643

[62] Шенде В.В., Буллок С.С., Марков І.Л. “Синтез квантово-логічних схем”. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000–1010 (2006).
https: / / doi.org/ 10.1109 / TCAD.2005.855930

[63] Юха Дж. Вартіайнен, Мікко Мьоттенен і Мартті М. Саломаа. «Ефективна декомпозиція квантових воріт». фіз. Преподобний Летт. 92, 177902 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.92.177902

[64] Бей Цзен, Се Чень та Ісаак Л Чуан. «Операції напівкліффорда, структура ієрархії $mathcal{C}_{k}$ і складність воріт для відмовостійких квантових обчислень». фіз. Rev. A 77, 042313 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.042313

[65] Гері Дж. Муні, Чарльз Д. Хілл і Ллойд К. Л. Холленберг. «Оптимальний за вартістю однокубітний вентильний синтез в ієрархії Кліффорда». Квант 5, 396 (2021).
https://doi.org/10.22331/q-2021-02-15-396

[66] Надіш де Сільва. «Ефективна телепортація через квантові ворота у вищих вимірах». Праці Королівського товариства A 477, 20200865 (2021).
https: / / doi.org/ 10.1098 / rspa.2020.0865

[67] Даніель Готтесман та Ісаак Л Чуанг. «Демонстрація життєздатності універсальних квантових обчислень за допомогою телепортації та однокубітних операцій». Nature 402, 390–393 (1999).
https: / / doi.org/ 10.1038 / 46503

[68] Даніель Готтесман. “Уявлення Гейзенберга про квантові комп’ютери” (1998). arXiv:quant-ph/9807006.
arXiv: quant-ph / 9807006

[69] Вадим Ключников, Дмитро Маслов і Мікеле Моска. «Швидкий і ефективний точний синтез однокубітових унітарних елементів, створених Кліффордовим і t-гейтом». Квантова інформація. обчис. 13, 607–630 (2013). url: https:///dl.acm.org/doi/abs/10.5555/2535649.2535653.
https:///dl.acm.org/doi/abs/10.5555/2535649.2535653

[70] Ніколас Бруннер, Джеймс Шарам і Тамаш Вертеші. “Тестування структури багаточастинної заплутаності з дзвоновими нерівностями”. фіз. Преподобний Летт. 108, 110501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.108.110501

[71] Джулія Кемпе, Хіротада Кобаясі, Кейдзі Мацумото, Бен Тонер і Томас Відік. «Заплутані ігри важко приблизно оцінити». SIAM Journal on Computing 40, 848–877 (2011).
https: / / doi.org/ 10.1137 / 090751293

[72] Іхуй Квек, Еніт Каур і Марк М. Уайлд. «Оцінка багатовимірного сліду в постійній квантовій глибині». Квант 8, 1220 (2024).
https://doi.org/10.22331/q-2024-01-10-1220

[73] Пітер Селінджер. «Ефективна апроксимація однокубітних операторів Кліффорд+Т». Квантова інформація. обчис. 15, 159–180 (2015).

[74] Вадим Ключніков, Дмитро Маслов і Мікеле Моска. «Практична апроксимація однокубітних унітарних систем за допомогою однокубітових квантових Кліффорда та Т-схем». IEEE Transactions on Computers 65, 161–172 (2016).
https: / / doi.org/ 10.1109 / TC.2015.2409842

[75] Ніл Дж Росс. «Оптимальна апроксимація Z-поворотів CLIFFORD+V без анцил». Квантова інформація. обчис. 15, 932–950 (2015). url: https:///dl.acm.org/doi/abs/10.5555/2871350.2871354.
https:///dl.acm.org/doi/abs/10.5555/2871350.2871354

[76] Ітан Бернштейн і Умеш Вазірані. “Теорія квантової складності”. У матеріалах двадцять п’ятого щорічного симпозіуму ACM з теорії обчислень. Сторінки 11–20. STOC '93Нью-Йорк, Нью-Йорк, США (1993). Асоціація обчислювальної техніки.
https: / / doi.org/ 10.1145 / 167088.167097

[77] Алекс Бочаров, Мартін Роттлер і Кріста М Своре. “Ефективний синтез імовірнісних квантових схем з резервним відходом”. фіз. Rev. A 91, 052317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.052317

[78] Алекс Бочаров, Мартін Роттлер і Кріста М Своре. «Ефективний синтез універсальних квантових ланцюгів, що повторюються до успіху». фіз. Преподобний Летт. 114, 080502 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.080502

[79] Інго Вегенер. “Складність булевих функцій”. John Wiley $&$ Sons, Inc. США (1987).

[80] Геріберт Фолмер. «Вступ до складності схем: єдиний підхід». Springer Publishing Company, Incorporated. (2010). 1-е видання. url: https:///link.springer.com/book/10.1007/978-3-662-03927-4.
https://link.springer.com/book/10.1007/978-3-662-03927-4

[81] Р Смоленський. “Алгебраїчні методи в теорії нижніх меж для складності булевої схеми”. У матеріалах дев'ятнадцятого щорічного симпозіуму ACM з теорії обчислень. Сторінки 77–82. STOC '87Нью-Йорк, Нью-Йорк, США (1987). Асоціація обчислювальної техніки.
https: / / doi.org/ 10.1145 / 28395.28404

[82] Джайкумар Радхакрішнан. «Кращі межі для порогових формул». У [1991] Матеріали 32-го щорічного симпозіуму з основ інформатики. Сторінки 314–323. IEEE Computer Society (1991).
https:///doi.org/10.1109/SFCS.1991.185384

[83] Майкл Дж. Фішер, Альберт Р. Мейєр і Майкл С. Патерсон. “$Omega(Nlog n)$ Нижні межі довжини булевих формул”. SIAM J. Comput. 11, 416–427 (1982).
https: / / doi.org/ 10.1137 / 0211033

[84] Санджив Арора та Боаз Барак. “Комп’ютерна складність: сучасний підхід”. Cambridge University Press. США (2009). 1-е видання. url: https:///dl.acm.org/doi/abs/10.5555/1540612.
https:///dl.acm.org/doi/abs/10.5555/1540612

[85] Скотт Ааронсон. «Скільки структури потрібно для величезних квантових прискорень?» (2022). arXiv:2209.06930.
arXiv: 2209.06930

[86] Девід А. Баррінгтон. «Програми розгалуження розміру полінома обмеженої ширини розпізнають саме ті мови в NC1». Journal of Computer and System Sciences 38, 150–164 (1989).
https://doi.org/10.1016/0022-0000(89)90037-8

[87] Скотт Ааронсон і Алекс Архіпов. “Обчислювальна складність лінійної оптики”. У матеріалах сорок третього щорічного симпозіуму ACM з теорії обчислень. Сторінки 333–342. STOC '11Нью-Йорк, Нью-Йорк, США (2011). Асоціація обчислювальної техніки.
https: / / doi.org/ 10.1145 / 1993636.1993682

[88] Петро Шор. “Алгоритми поліноміального часу для розкладання на прості множники та дискретних логарифмів на квантовому комп’ютері”. SIAM Review 41, 303–332 (1999).
https: / / doi.org/ 10.1137 / S0036144598347011

[89] Деніел Р. Саймон. «Про силу квантових обчислень». SIAM Journal on Computing 26, 1474–1483 (1997).
https: / / doi.org/ 10.1137 / S0097539796298637

[90] Жиль Брассар, Гаррі Бурман, Ноа Лінден, Андре Аллан Мето, Ален Тап і Унгер Фальк. «Обмеження нелокальності в будь-якому світі, в якому комунікаційна складність не є тривіальною». фіз. Преподобний Летт. 96, 250401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.96.250401

[91] Вім ван Дам. “Неправдоподібні наслідки надсильної нелокальності”. Natural Computing 12, 9–12 (2013).
https://doi.org/10.1007/s11047-012-9353-6

[92] Метью Емі та Мікеле Моска. «Оптимізація T-Count і коди Ріда-Мюллера». IEEE Transactions on Information Theory 65, 4771–4784 (2019).
https:///doi.org/10.1109/TIT.2019.2906374

[93] Пітер Бюргіссер, Майкл Клаузен і Мохаммад Шокроллахі. “Алгебраїчна теорія складності”. Том 315. Springer Science & Business Media. (2013). url: https:///dl.acm.org/doi/abs/10.5555/1965416.
https:///dl.acm.org/doi/abs/10.5555/1965416

[94] Гуан Хао Лоу та Ісаак Л. Чуанг. “Оптимальне гамільтоніанське моделювання шляхом квантової обробки сигналів”. фіз. Преподобний Летт. 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[95] Чонван Хаа. “Декомпозиція періодичних функцій у квантовій обробці сигналів”. Квант 3, 190 (2019).
https://doi.org/10.22331/q-2019-10-07-190

[96] Скотт Ааронсон, Шалев Бен-Девід, Робін Котарі, Шравас Рао та Авішай Тал. «Ступінь проти приблизного ступеня та квантові наслідки теореми чутливості Хуанга». У матеріалах 53-го щорічного симпозіуму ACM SIGACT з теорії обчислень. Сторінки 1330–1342. STOC 2021Нью-Йорк, Нью-Йорк, США (2021). Асоціація обчислювальної техніки.
https: / / doi.org/ 10.1145 / 3406325.3451047

[97] Хао Хуан. “Індуковані підграфи гіперкубів і доказ гіпотези чутливості”. Annals of Mathematics 190, 949–955 (2019).
https:///doi.org/10.4007/annals.2019.190.3.6

[98] Андріс Амбайніс, Каспарс Балодіс, Олександр Бєловс, Трой Лі, Міклош Санта та Юріс Смотровс. «Розділення в складності запиту на основі функцій покажчика». J. ACM 64 (2017).
https: / / doi.org/ 10.1145 / 3106234

[99] Пітер Хоєр і Роберт Шпалек. «Квантові схеми з необмеженим розгортанням». У Helmut Alt і Michel Habib, редактори, STACS 2003. Сторінки 234–246. Берлін, Гейдельберг (2003). Шпрінгер Берлін Гейдельберг.
https://doi.org/10.1007/3-540-36494-3_22

[100] Остін К. Деніел, Ін'юе Чжу, С. Уерта Альдерете, Вікас Бучеммаварі, Алайна М. Грін, Нхунг Х. Нгуєн, Тайлер Г. Тертелл, Ендрю Чжао, Норберт М. Лінке та Акімаса Міяке. «Квантова обчислювальна перевага, підтверджена нелокальними іграми з циклічним станом кластера». фіз. Rev. Research 4, 033068 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033068

[101] Пол Херрінгер і Роберт Рауссендорф. “Класифікація вимірювального квантового дроту в стабілізаторі PEPS”. Квант 7, 1041 (2023).
https://doi.org/10.22331/q-2023-06-12-1041

[102] Абхішек Ананд. “Про потужність квантових і класичних схем з перемежуванням малої глибини”. Магістерська робота. Університет Ватерлоо. (2022). url: https:///uwspace.uwaterloo.ca/handle/10012/18805.
https:///uwspace.uwaterloo.ca/handle/10012/18805

[103] Джон Прескілл. «Квантові обчислення в епоху NISQ і за її межами». Квант 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[104] Бюлент Демірель, Вейкай Венг, Крістофер Талакер, Метті Хобан і Стефані Барз. «Кореляції для обчислень і обчислення для кореляцій». npj Квантова інформація 7, 1–8 (2021).
https://doi.org/10.1038/s41534-020-00354-2

[105] Маноранджан Суейн, Аміт Рай, Бікаш К. Бехера та Прасанта К. Паніграхі. “Експериментальна демонстрація порушень нерівностей Мерміна і Світличного для станів W і GHZ”. Квантова обробка інформації 18, 218 (2019).
https://doi.org/10.1007/s11128-019-2331-5

[106] Бо Янг, Руді Реймонд, Хіроші Імаі, Хюнсок Чанг і Хідефумі Хіраісі. «Тестування масштабованих нерівностей Белла для станів квантового графа на квантових пристроях IBM». IEEE Journal on Emerging and Selected Topics in Circuits and Systems 12, 638–647 (2022).
https:///doi.org/10.1109/JETCAS.2022.3201730

[107] Ф. Баккарі, Р. Аугусіак, І. Шупіч, Й. Тура, А. Асін. «Маштабовані нерівності дзвоника для станів графа кубітів і надійного самотестування». фіз. Преподобний Летт. 124, 020402 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.124.020402

[108] Кен Ікс Вей, Ісаак Лауер, Шрікант Срінівасан, Ніереджа Сундаресан, Дуглас Т. МакКлюр, Девід Тойлі, Девід С. МакКей, Джей М. Гамбетта та Сара Шелдон. «Перевірка багаточастинних заплутаних станів Грінбергера-Хорна-Цайлінгера за допомогою множинних квантових когерентностей». фіз. Rev. A 101, 032343 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.032343

[109] Вей-Цзя Хуан, Вей-Чен Чіен, Чіен-Хун Чо, Че-Чун Хуан, Цун-Вей Хуан і Чін-Рей Чанг. «Нерівності Мерміна кількох кубітів з ортогональними вимірюваннями на 53-кубітній системі IBM Q». Квантова інженерія 2, e45 (2020).
https:///doi.org/10.1002/que2.45

[110] Мерон Шеффер, Даніель Азсес та Емануеле Г. Далла Торре. «Гра в квантові нелокальні ігри з шістьма шумними кубітами в хмарі». Advanced Quantum Technologies 5, 2100081 (2022).
https:///doi.org/10.1002/qute.202100081

[111] Ведран Дунько, Теодорос Капурніотіс та Елхам Кашефі. «Квантово-розширені безпечні делеговані класичні обчислення». Квантова інформація. обчис. 16, 61–86 (2016).

[112] Стефані Барз, Ведран Дунько, Флоріан Шледерер, Меррітт Мур, Елхам Кашефі та Ян А. Волмслі. «Покращені делеговані обчислення за допомогою когерентності». фіз. Rev. A 93, 032339 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.032339

[113] Марко Клементі, Анна Паппа, Андреас Екштайн, Ієн Уолмслі, Елхем Кашефі та Стефані Барз. «Класичне багатостороннє обчислення з використанням квантових ресурсів». Physical Review A 96, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062317

[114] Насір Ахмед і Камісетті Рамамохан Рао. «Перетворення Уолша-Адамара». В Ортогональні перетворення для обробки цифрового сигналу. Сторінки 99–152. Springer (1975).

[115] Майкл А. Нільсен та Ісаак Л. Чуанг. «Квантові обчислення та квантова інформація: видання до 10-ї річниці». Cambridge University Press. (2010).
https:///doi.org/10.1017/CBO9780511976667

[116] Філіп Фейнсільвер і Єжи Коцик. “Поліноми Кравчука та матриці Кравчука”. Сторінки 115–141. Останні досягнення в галузі прикладної ймовірності. Спрингер США. Бостон, Массачусетс (2005).
https://doi.org/10.1007/0-387-23394-6_5

[117] Філіп Файнсільвер і Рене Шотт. «Трансформації та згортки Кравчука». Вісник математичних наукСтор. 1–19 (2018).
https://doi.org/10.1007/s13373-018-0132-2

[118] M. Stobińska, A. Buraczewski, M. Moore, WR Clements, JJ Renema, SW Nam, T. Gerrits, A. Lita, WS Kolthammer, A. Eckstein та IA Walmsley. «Квантова інтерференція забезпечує постійну обробку квантової інформації». Наукові досягнення 5, eaau9674 (2019).
https:///doi.org/10.1126/sciadv.aau9674

[119] Равіндран Каннан і Ахім Бахем. “Поліноміальні алгоритми для обчислення нормальних форм Сміта та Ерміта цілочисельної матриці”. SIAM Journal on Computing 8, 499–507 (1979).
https: / / doi.org/ 10.1137 / 0208040

[120] Джош Алман і Вірджинія Василевська Вільямс. «Удосконалений лазерний метод і швидше множення матриць». У матеріалах тридцять другого щорічного симпозіуму ACM-SIAM з дискретних алгоритмів. Сторінки 522–539. SODA '21USA (2021). Товариство промислової та прикладної математики.
https: / / doi.org/ 10.1137 / 1.9781611976465.32

Цитується

Ця стаття опублікована в Quantum під Creative Commons Attribution 4.0 International (CC на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.

Розповсюдження контенту та PR на основі SEO. Отримайте посилення сьогодні.
PlatoData.Network Vertical Generative Ai. Додайте собі сили. Доступ тут.
PlatoAiStream. Web3 Intelligence. Розширення знань. Доступ тут.
ПлатонЕСГ. вуглець, CleanTech, Енергія, Навколишнє середовище, Сонячна, Поводження з відходами. Доступ тут.
PlatoHealth. Розвідка про біотехнології та клінічні випробування. Доступ тут.
джерело: https://quantum-journal.org/papers/q-2024-04-09-1312/

Часова мітка: Квітень 9, 2024

Часова мітка: Грудень 7, 2022

Квантова перевага в квантових обчисленнях на основі часових плоских вимірювань

Перевидано Платоном

абстрактний

Популярне резюме

► Дані BibTeX

► Список літератури

Цитується

Більше від Квантовий журнал

Тестування ідентичності колекцій квантових станів: аналіз складності вибірки

Масштабована та гнучка класична тіньова томографія з тензорними мережами

Приборкання апроксимації обертової хвилі

Виробництво ентропії заплутаності в квантових нейронних мережах

Розпізнавання квантової фази за допомогою методів квантового ядра

Нетривіальні симетрії в квантових ландшафтах та їх стійкість до квантового шуму

Виклик до редакції 2023

Оцінка параметра QKD двоуніверсальним хешуванням

MQT Bench: порівняльний аналіз програмного забезпечення та інструментів автоматизації проектування для квантових обчислень

Масштабування алгоритму квантової наближеної оптимізації на апаратному забезпеченні на основі надпровідних кубітів

Про нас

Вертикальний пошук & Ai

платформа

Залишайтеся на зв'язку

рахунки