[ad_1]
Pomiędzy podejściami NISQ (noisy intermediate scale quantum) bez żadnego dowodu na solidną przewagę kwantową a w pełni odpornymi na błędy obliczeniami kwantowymi, proponujemy schemat osiągnięcia możliwej do udowodnienia superpolinomialnej przewagi kwantowej (zgodnie z niektórymi powszechnie akceptowanymi przypuszczeniami dotyczącymi złożoności), która jest odporna na szum przy minimalnych wymaganiach dotyczących korekcji błędów. Wybieramy klasę problemów próbkowania z bramkami komutacyjnymi znanymi jako rzadkie obwody IQP (Instantaneous Quantum Polynomial-time) i zapewniamy ich odporną na błędy implementację poprzez wprowadzenie kodu tetrahelix. Ten nowy kod jest uzyskiwany przez połączenie kilku kodów czworościennych (kolorowych kodów 3D) i ma następujące właściwości: każda rzadka bramka IQP dopuszcza implementację poprzeczną, a głębokość obwodu logicznego można zamienić na jego szerokość. Łącząc te cechy, uzyskujemy implementację głębokości-1 dowolnego rzadkiego obwodu IQP aż do przygotowania zakodowanych stanów. Odbywa się to kosztem narzutu przestrzeni, który jest tylko polilogarytmiczny w szerokości oryginalnego obwodu. Ponadto pokazujemy, że przygotowanie stanu może być również wykonane na stałej głębokości z pojedynczym krokiem sprzężenia zwrotnego z obliczeń klasycznych. Nasza konstrukcja wykazuje zatem solidną, wielomianową przewagę kwantową dla problemu próbkowania zaimplementowanego w obwodzie o stałej głębokości z pojedynczą rundą pomiaru i sprzężenia zwrotnego.
Pomiędzy podejściami NISQ (noisy intermediate scale quantum) bez żadnego dowodu na solidną przewagę kwantową a w pełni odpornymi na błędy obliczeniami kwantowymi, proponujemy schemat pozwalający osiągnąć możliwą do udowodnienia superpolinomialną przewagę kwantową (zgodnie z niektórymi powszechnie akceptowanymi przypuszczeniami dotyczącymi złożoności), która jest odporna na szum przy minimalnych wymaganiach dotyczących korekcji błędów. Wybieramy klasę problemów próbkowania z bramkami komutacyjnymi znanymi jako rzadkie obwody IQP (Instantaneous Quantum Polynomial-time) i zapewniamy ich odporną na błędy implementację poprzez wprowadzenie kodu tetrahelix. Ten nowy kod jest uzyskiwany przez połączenie kilku kodów czworościennych (kolorowych kodów 3D) i ma następujące właściwości: każda rzadka bramka IQP dopuszcza implementację poprzeczną, a głębokość obwodu logicznego można zamienić na jego szerokość. Łącząc te cechy, uzyskujemy implementację głębokości-1 dowolnego rzadkiego obwodu IQP aż do przygotowania zakodowanych stanów. Odbywa się to kosztem narzutu przestrzeni, który jest tylko polilogarytmiczny w szerokości oryginalnego obwodu. Ponadto pokazujemy, że przygotowanie stanu może być również wykonane na stałej głębokości z pojedynczym krokiem sprzężenia zwrotnego z obliczeń klasycznych. Nasza konstrukcja wykazuje zatem solidną, wielomianową przewagę kwantową dla problemu próbkowania zaimplementowanego w obwodzie o stałej głębokości z pojedynczą rundą pomiaru i sprzężenia zwrotnego.
[1] Austin P Lund, Michael J Bremner i Timothy C Ralph. „Quantum sampling problems, bosonsampling and quantum supremacy”. npj Quantum Information 3, 1-8 (2017).
https://doi.org/10.1038/s41534-017-0018-2
[2] Ramis Movassagh. „ Twardość losowych obwodów kwantowych”. Nature Physics 19, 1719-1724 (2023).
https://doi.org/10.1038/s41567-023-02131-2
[3] Scott Aaronson i Alex Arkhipov. „Złożoność obliczeniowa optyki liniowej”. In Proceedings of the forty-third annual ACM symposium on Theory of computing. Pages 333-342. (2011).
https://doi.org/10.1145/1993636.1993682
[4] Adam Bouland, Bill Fefferman, Chinmay Nirkhe i Umesh Vazirani. „O złożoności i weryfikacji kwantowego losowego próbkowania obwodów”. Nature Physics 15, 159-163 (2019).
https://doi.org/10.1038/s41567-018-0318-2
[5] Dan Shepherd i Michael J Bremner. „Temporally unstructured quantum computation”. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465, 1413-1439 (2009).
https://doi.org/10.1098/rspa.2008.0443
[6] Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu i Umesh Vazirani. „ A polynomial-time classical algorithm for noisy random circuit sampling”. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Pages 945-957. (2023).
https://doi.org/10.1145/3564246.3585234
[7] Yiqing Zhou, E Miles Stoudenmire i Xavier Waintal. „Co ogranicza symulację komputerów kwantowych?”. Physical Review X 10, 041038 (2020).
https://doi.org/10.1103/PhysRevX.10.041038
[8] John C Napp, Rolando L La Placa, Alexander M Dalzell, Fernando GSL Brandao, and Aram W Harrow. „ Wydajna klasyczna symulacja losowych płytkich obwodów kwantowych 2d ”. Physical Review X 12, 021021 (2022).
https://doi.org/10.1103/PhysRevX.12.021021
[9] Xun Gao, Marcin Kalinowski, Chi-Ning Chou, Mikhail D Lukin, Boaz Barak, and Soonwon Choi. „Ograniczenia liniowej entropii krzyżowej jako miary przewagi kwantowej”. PRX Quantum 5, 010334 (2024).
https://doi.org/10.1103/PRXQuantum.5.010334
[10] Bill Fefferman, Soumik Ghosh, Michael Gullans, Kohdai Kuroiwa i Kunal Sharma. „Effect of non-unital noise on random circuit sampling ” (2023). arXiv:2306.16659.
arXiv:2306.16659
[11] John Preskill. „Obliczenia kwantowe w erze nisq i później”. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79
[12] Bryan Eastin i Emanuel Knill. „Restrictions on transversal encoded quantum gate sets”. Physical Review Letters 102, 110502 (2009).
https://doi.org/10.1103/PhysRevLett.102.110502
[13] Rawad Mezher, Joe Ghalbouni, Joseph Dgheim i Damian Markham. „ Odporne na błędy przyspieszenie kwantowe z obwodów kwantowych o stałej głębokości ”. Physical Review Research 2, 033444 (2020).
https://doi.org/10.1103/PhysRevResearch.2.033444
[14] Craig Gidney i Martin Ekerå. „How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits”. Quantum 5, 433 (2021).
https://doi.org/10.22331/q-2021-04-15-433
[15] Sergey Bravyi, David Gosset, Robert Koenig i Marco Tomamichel. „Przewaga kwantowa z zaszumionymi płytkimi obwodami”. Nature Physics 16, 1040-1045 (2020).
https://doi.org/10.1038/s41567-020-0948-z
[16] Michael J Bremner, Richard Jozsa i Dan J Shepherd. „Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy”. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, 459-472 (2011).
https://doi.org/10.1098/rspa.2010.0301
[17] Michael J Bremner, Ashley Montanaro i Dan J Shepherd. „Average-case complexity versus approximate simulation of commuting quantum computations”. Physical Review Letters 117, 080501 (2016).
https://doi.org/10.1103/PhysRevLett.117.080501
[18] Michael J Bremner, Ashley Montanaro i Dan J Shepherd. „Achieving quantum supremacy with sparse and noisy commuting quantum computations”. Quantum 1, 8 (2017).
https://doi.org/10.22331/q-2017-04-25-8
[19] Leslie Ann Goldberg i Heng Guo. „ The complexity of approximating complex-valued ising and tutte partition functions”. computational complexity 26, 765-833 (2017).
https://doi.org/10.1007/s00037-017-0162-2
[20] Keisuke Fujii i Tomoyuki Morimae. „Commuting quantum circuits and complexity of ising partition functions”. New Journal of Physics 19, 033003 (2017).
https://doi.org/10.1088/1367-2630/aa5fdb
[21] Daniel Gottesman. „Fault-tolerant quantum computation with constant overhead” (2014). arXiv:1310.2984.
arXiv:1310.2984
[22] Peter Høyer i Robert Špalek. „Quantum fan-out is powerful”. Theory of computing 1, 81-103 (2005).
https://doi.org/10.4086/toc.2005.v001a005
[23] Dorit Aharonov i Michael Ben-Or. „Fault-tolerant quantum computation with constant error”. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. Pages 176-188. (1997).
https://doi.org/10.1137/S0097539799359385
[24] Emanuel Knill, Raymond Laflamme, and Wojciech H Żurek. „Resilient quantum computation”. Science 279, 342-345 (1998).
https://doi.org/10.1126/science.279.5349.342
[25] Hector Bombin i Miguel-Angel Martin-Delgado. „Topological computation without braiding”. Physical Review Letters 98, 160502 (2007).
https://doi.org/10.1103/PhysRevLett.98.160502
[26] Aleksander Kubica i Michael E Beverland. „Uniwersalne bramki poprzeczne z kodami kolorów: A simplified approach”. Physical Review A 91, 032330 (2015).
https://doi.org/10.1103/PhysRevA.91.032330
[27] A Robert Calderbank i Peter W Shor. „Dobre kwantowe kody korekcji błędów istnieją”. Physical Review A 54, 1098 (1996).
https://doi.org/10.1103/PhysRevA.54.1098
[28] Andrew M Steane. „Error correcting codes in quantum theory”. Physical Review Letters 77, 793 (1996).
https://doi.org/10.1103/PhysRevLett.77.793
[29] Clare Horsman, Austin G Fowler, Simon Devitt i Rodney Van Meter. „Surface code quantum computing by lattice surgery”. New Journal of Physics 14, 123011 (2012).
https://doi.org/10.1088/1367-2630/14/12/123011
[30] Daniel Litwiński. „Gra kodów powierzchniowych: Wielkoskalowe obliczenia kwantowe z chirurgią kratową”. Quantum 3, 128 (2019).
https://doi.org/10.22331/q-2019-03-05-128
[31] Andrew J. Landahl i Ciaran Ryan-Anderson. „Quantum computing by color-code lattice surgery” (2014). arXiv:1407.5103.
arXiv:1407.5103
[32] Héctor Bombín. „Single-shot fault-tolerant quantum error correction”. Physical Review X 5, 031043 (2015).
https://doi.org/10.1103/PhysRevX.5.031043
[33] Héctor Bombín. „Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes”. New Journal of Physics 17, 083002 (2015).
https://doi.org/10.1088/1367-2630/17/8/083002
[34] H Bombin i MA Martin-Delgado. „Exact topological quantum order in d= 3 and beyond: Branyons and brane-net condensates”. Physical Review B 75, 075103 (2007).
https://doi.org/10.1103/PhysRevB.75.075103
[35] Hector Bombin i Miguel Angel Martin-Delgado. „Topologiczna destylacja kwantowa”. Physical Review Letters 97, 180501 (2006).
https://doi.org/10.1103/PhysRevLett.97.180501
[36] Christophe Vuillot. „ Obliczenia kwantowe odporne na błędy: Teoria i praktyka”. Praca doktorska. TU Delft. (2020).
https://doi.org/10.4233/uuid:7cb715f4-eaf0-4526-8552-9f97cc864383
[37] AH Boerdijk. „Some remarks concerning close-packing of equal spheres”. Philips Research Reports 7, 303-313 (1952).
[38] HSM Coxeter i JM Wills. „Regular complex polytopes”. Jahresbericht der Deutschen Mathematiker Vereinigung 96, 2-2 (1994).
https://doi.org/10.2307/1575843
[39] Christopher Chamberland, Aleksander Kubica, Theodore J Yoder i Guanyu Zhu. „ Trójkątne kody kolorów na trójwartościowych grafach z kubitami flagowymi ”. New Journal of Physics 22, 023019 (2020).
https://doi.org/10.1088/1367-2630/ab68fd
[40] Kaavya Sahay i Benjamin J Brown. „ Dekoder trójkątnego kodu koloru poprzez dopasowanie na pasku Möbiusa ”. PRX Quantum 3, 010310 (2022).
https://doi.org/10.1103/PRXQuantum.3.010310
[41] Aleksander Kubica i Nicolas Delfosse. „ Efektywne dekodery kodów kolorowych w wymiarach $d \ge 2$ z dekoderów kodów torycznych”. Quantum 7, 929 (2023).
https://doi.org/10.22331/q-2023-02-21-929
[42] Michael E Beverland, Aleksander Kubica i Krysta M Svore. „Koszt uniwersalności: Badanie porównawcze kosztów ogólnych destylacji stanów i przełączania kodów za pomocą kodów kolorów”. PRX Quantum 2, 020341 (2021).
https://doi.org/10.1103/PRXQuantum.2.020341
[43] Hector Bombin. „Transversal gates and error propagation in 3d topological codes ” (2018). arXiv:1810.09575.
arXiv:1810.09575
[44] Dan Browne, Elham Kashefi i Simon Perdrix. „Złożoność głębi obliczeniowej obliczeń kwantowych opartych na pomiarach”. In Theory of Quantum Computation, Communication, and Cryptography: 5th Conference, TQC 2010, Leeds, UK, April 13-15, 2010, Revised Selected Papers 5. Pages 35-46. Springer (2011).
https://doi.org/10.1007/978-3-642-18073-6_4
[45] Keisuke Fujii. „Noise threshold of quantum supremacy” (2016). arXiv:1610.03632.
arXiv:1610.03632
[46] Dolev Bluvstein, Simon J Evered, Alexandra A Geim, Sophie H Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, et al. „Logiczny procesor kwantowy oparty na rekonfigurowalnych macierzach atomów”. Nature 626, 58-65 (2024).
https://doi.org/10.1038/s41586-023-06927-3
[47] Gregoire de Gliniasty, Rawad Mezher i Damian Markham. W przygotowaniu.
[1] Dolev Bluvstein, Simon J. Evered, Alexandra A. Geim, Sophie H. Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, J. Pablo Bonilla Ataides, Nishad Maskara, Iris Cong, Xun Gao, Pedro Sales Rodriguez, Thomas Karolyshyn, Giulia Semeghini, Michael J. Gullans, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin, „Logical quantum processor based on reconfigurable atom arrays”, Nature 626 7997, 58 (2024).
[2] Dmitri Maslov, Sergey Bravyi, Felix Tripier, Andrii Maksymov i Joe Latone, „Fast classical simulation of Harvard/QuEra IQP circuits”, arXiv:2402.03211, (2024).
[3] Dominik Hangleiter, Marcin Kalinowski, Dolev Bluvstein, Madelyn Cain, Nishad Maskara, Xun Gao, Aleksander Kubica, Mikhail D. Lukin, and Michael J. Gullans, „Fault-tolerant compiling of classically hard IQP circuits on hypercubes”, arXiv:2404.19005, (2024).
[4] Joel Rajakumar, James D. Watson i Yi-Kai Liu, „Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth”, arXiv:2403.14607, (2024).
Powyższe cytaty pochodzą z SAO/NASA ADS (ostatnia pomyślna aktualizacja 2024-05-06 14:20:58). Lista może być niekompletna, ponieważ nie wszyscy wydawcy udostępniają odpowiednie i kompletne dane dotyczące cytowań.
Nie można pobrać Crossref cited-by data podczas ostatniej próby 2024-05-06 14:20:57: Nie można pobrać danych cited-by dla 10.22331/q-2024-05-06-1337 z Crossref. Jest to normalne, jeśli DOI został niedawno zarejestrowany.
[ad_2]