Quantum Goemans-Williamson Algorithm With The Hadamard Test And Approximate Amplitude Constraints

Újra kiadta Platón

Követő: 0

Taylor L. Patti^1,2, Jean Kossaifi², Anima Anandkumar^3,2és Susanne F. Yelin¹

¹Fizikai Tanszék, Harvard Egyetem, Cambridge, Massachusetts 02138, USA
²NVIDIA, Santa Clara, California 95051, USA
³Számítástechnikai és Matematikai Tudományok Tanszék (CMS), California Institute of Technology (Caltech), Pasadena, CA 91125 USA

Érdekesnek találja ezt a cikket, vagy szeretne megvitatni? Scite vagy hagyjon megjegyzést a SciRate-en.

Absztrakt

A félig meghatározott programok olyan optimalizálási módszerek, amelyek sokféle alkalmazással rendelkeznek, például nehéz kombinatorikus problémák közelítésére. Az egyik ilyen félig meghatározott program a Goemans-Williamson algoritmus, egy népszerű egész szám relaxációs technika. Bemutatunk egy variációs kvantum algoritmust a Goemans-Williamson algoritmushoz, amely csak $n{+}1$ qubitet, állandó számú áramkör-előkészítést és $text{poly}(n)$ elvárási értékeket használ a félig meghatározott programok közelítő megoldására. legfeljebb $N=2^n$ változókkal és $M sim O(N)$ megszorításokkal. A hatékony optimalizálás úgy érhető el, hogy az objektív mátrixot megfelelően paraméterezett unitáriusként kódolják, amely egy segéd qubitre vonatkozik, ez a technika a Hadamard-teszt. A Hadamard-teszt lehetővé teszi, hogy optimalizáljuk a célfüggvényt úgy, hogy a kiegészítő qubit egyetlen várható értékét becsüljük meg, ahelyett, hogy exponenciálisan sok várható értéket külön-külön becsülnénk meg. Hasonlóképpen szemléltetjük, hogy a félig meghatározott programozási megszorítások hatékonyan érvényesíthetők egy második Hadamard-teszt megvalósításával, valamint egy polinomszámú Pauli-sztring amplitúdó megszorítással. Protokollunk hatékonyságát a Goemans-Williamson algoritmus hatékony kvantummegvalósításának kidolgozásával demonstráljuk különféle NP-nehéz problémákra, beleértve a MaxCut-ot is. Módszerünk felülmúlja az analóg klasszikus módszerek teljesítményét a GSet könyvtár jól tanulmányozott MaxCut-problémáinak sokféle részében.

Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Kiemelt kép: HTAAC-QSDP diagramja a Goemans-Williamson algoritmushoz $n=3$ nem kiegészítő qubittel. a) $N$ változók klasszikus problémája (itt egy $N$-csúcs MaxCut probléma, ahol $N=8$). A $W$ súlymátrixot az egységes $U_W$ generálására használják. b) A Hadamard-tesztet a célfüggvény és a populációegyensúlyozási korlátok hatékony értékelésére használják. A $n$-qubit állapot $|psirangle = U_V|mathbf{0}rangle$ egy $U_V$ variációs kvantumáramkörrel készül. Az $n+1$-edik (kiegészítő) qubit a következőképpen van inicializálva: $(|0rangle -i |1rangle)/sqrt{2}$. Ezt követően a Hadamard-tesztet hajtják végre: $U_W$ egy ellenőrzött egységként valósul meg, amely a segéd qubitre vonatkozik, amelyet ezután mérve kiszámítja a $langle sigma_{n+1} rangle_{W,t} = text{Im} [langle psi|U_W|psi rangle]$ vagy $langle sigma_{n+1} rangle_{P,t} = szöveg{Im}[langle psi|U_P|psi rangle]$. c) A $M=2^n$ SDP amplitúdó megszorítások megszorításai hozzávetőlegesen csak $m sim text{poly}(n)$ Pauli string megszorításokkal érvényesülnek. Ezeket úgy számítjuk ki, hogy összegyűjtjük a $n$-qubit Pauli-$z$ méréseket, és marginális statisztikák segítségével megbecsüljük a $m$ várható értékeket.

Népszerű összefoglaló

A félig meghatározott programok lehetővé teszik számunkra a nehéz problémák széles skálájának közelítését, beleértve az NP-nehéz problémákat is. Az egyik ilyen félig meghatározott program a Goemans-Williamson algoritmus, amely képes megoldani olyan nehéz problémákat, mint például a MaxCut. Bemutatunk egy variációs kvantum algoritmust a Goemans-Williamson algoritmushoz, amely mindössze $n{+}1$ qubitet, állandó számú áramkör-előkészítést és polinomiális számú elvárási értéket használ, hogy megközelítőleg megoldja a félig meghatározott programokat exponenciális számú változók és megszorítások. A problémát kvantumáramkörbe (vagy unitérba) kódoljuk, és egyetlen segédkubiton olvassuk ki, a Hadamard-teszt néven ismert technikát. Hasonlóképpen szemléltetjük, hogy a problémamegszorítások kényszeríthetők 1) egy második Hadamard-teszttel és 2) egy polinomszámú Pauli-sztring kényszerrel. Protokollunk hatékonyságát a Goemans-Williamson algoritmus hatékony kvantummegvalósításának kidolgozásával demonstráljuk különféle NP-nehéz problémákra, beleértve a MaxCut-ot is. Módszerünk felülmúlja az analóg klasszikus módszerek teljesítményét a jól tanulmányozott MaxCut problémák egy változatos részhalmazában.

► BibTeX adatok

@cikk{Patti2023quantumgoemans, doi = {10.22331/q-2023-07-12-1057}, url = {https://doi.org/10.22331/q-2023-07-12-1057}, cím { = {Quantum G}oemans-{W}illiamson {A} algoritmus az {H}adamard {T}est és {A}közelítő {A}mplitúdó {C}megszorításokkal}, szerző = {Patti, Taylor L. és Kossaifi, Jean és Anandkumar, Anima és Yelin, Susanne F.}, folyóirat = {{Quantum}}, issn = {2521-327X}, kiadó = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}} , kötet = {7}, oldalak = {1057}, hónap = júl, év = {2023} }

► Referenciák

[1] Stephen P. Boyd és Lieven Vandenberghe. „Konvex optimalizálás”. Cambridge Press. (2004).
https:///doi.org/10.1017/CBO9780511804441

[2] Michel X. Goemans. „Félig határozott programozás a kombinatorikus optimalizálásban”. Matematikai programozás 79, 143–161 (1997).
https:///doi.org/10.1007/BF02614315

[3] Lieven Vandenberghe és Stephen Boyd. „A félig meghatározott programozás alkalmazásai”. Applied Numerical Mathematics 29, 283–299 (1999).
https://doi.org/10.1016/S0168-9274(98)00098-1

[4] Wenjun Li, Yang Ding, Yongjie Yang, R. Simon Sherratt, Jong Hyuk Park és Jin Wang. „Alapvető np-kemény problémák paraméterezett algoritmusai: felmérés”. Emberközpontú számítástechnika és információtudomány 10, 29 (2020).
https:///doi.org/10.1186/s13673-020-00226-w

[5] Christoph Helmberg. „Félig meghatározott programozás kombinatorikus optimalizáláshoz”. Konrad-Zuse-Zentrum fur Informationstechnik Berlin. (2000).
https:///doi.org/10.1007/BF02614315

[6] Michel X. Goemans és David P. Williamson. „Továbbfejlesztett közelítési algoritmusok maximális vágási és kielégítési problémákhoz félig meghatározott programozással”. J. ACM 42, 1115–1145 (1995).
https:///doi.org/10.1145/227683.227684

[7] Florian A. Potra és Stephen J. Wright. „Belső pont módszerek”. Journal of Computational and Applied Mathematics 124, 281–302 (2000).
https://doi.org/10.1016/S0377-0427(00)00433-7

[8] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan és Zhao Song. "Gyorsabb belső pont módszer a félig meghatározott programozáshoz". 2020-ban az IEEE 61. éves szimpóziuma a számítástechnika alapjairól (FOCS). 910–918. oldal. IEEE (2020).
https:///doi.org/10.1109/FOCS46700.2020.00089

[9] Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao és Ruizhe Zhang. „Az sdp gyorsabb megoldása: robusztus ipm keretrendszer és hatékony megvalósítás”. 2022-ben az IEEE 63. éves szimpóziuma a számítástechnika alapjairól (FOCS). 233–244. oldal. IEEE (2022).
https:///doi.org/10.1109/FOCS54457.2022.00029

[10] David P. Williamson és David B. Shmoys. „A közelítő algoritmusok tervezése”. Cambridge University Press. (2011).
https:///doi.org/10.1017/CBO9780511921735

[11] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn és mások. „Kvantumoptimalizálás variációs algoritmusok segítségével rövid távú kvantumeszközökön”. Quantum Science and Technology 3, 030503 (2018).
https:///doi.org/10.1088/2058-9565/aab822

[12] Edward Farhi, Jeffrey Goldstone, Sam Gutmann és Michael Sipser. „Kvantumszámítás adiabatikus evolúcióval” (2000). arXiv:quant-ph/0001106.
arXiv:quant-ph/0001106

[13] Tameem Albash és Daniel A. Lidar. „Adiabatikus kvantumszámítás”. Rev. Mod. Phys. 90, 015002 (2018).
https:///doi.org/10.1103/RevModPhys.90.015002

[14] Sepehr Ebadi, Alexander Keesling, Madelyn Cain, Tout T Wang, Harry Levine, Dolev Bluvstein, Giulia Semeghini, Ahmed Omran, JG Liu, Rhine Samajdar és mások. „A maximális független halmaz kvantumoptimalizálása Rydberg atomtömbök segítségével”. Science 376, 1209–1215 (2022).
https:///doi.org/10.1126/science.abo6587

[15] Tadashi Kadowaki és Hidetoshi Nishimori. „Kvantum lágyítás a keresztirányú feldolgozási modellben”. Phys. Rev. E 58, 5355–5363 (1998).
https:///doi.org/10.1103/PhysRevE.58.5355

[16] Elizabeth Gibney. „D-hullám frissítés: Hogyan használják a tudósok a világ legvitatottabb kvantumszámítógépét”. Nature 541 (2017).
https:///doi.org/10.1038/541447b

[17] Edward Farhi, Jeffrey Goldstone és Sam Gutmann. „A kvantumközelítő optimalizálási algoritmus”. arXiv (2014). arXiv:1411.4028.
https:///doi.org/10.48550/arXiv.1411.4028
arXiv: 1411.4028

[18] Juan M Arrazola, Ville Bergholm, Kamil Brádler, Thomas R Bromley, Matt J Collins, Ish Dhand, Alberto Fumagalli, Thomas Gerrits, Andrey Goussev, Lukas G Helt és mások. „Kvantumáramkörök sok fotonnal egy programozható nanofotonikus chipen”. Nature 591, 54–60 (2021).
https://doi.org/10.1038/s41586-021-03202-1

[19] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore és Xiaodi Wu. „Kvantum SDP-megoldók: Nagy gyorsítások, optimalitás és alkalmazások a kvantumtanuláshoz”. 46. Nemzetközi Kollokvium Automatákról, Nyelvekről és Programozásról (ICALP 2019) 132, 27:1–27:14 (2019).
https:///doi.org/10.4230/LIPIcs.ICALP.2019.27

[20] Joran Van Apeldoorn és Gilyén András. „Fejlesztések a kvantum-sdp-megoldásban alkalmazásokkal”. In Proceedings of the 46th International Colloquium on Automata, Languages and Programming (2019).
https:///doi.org/10.4230/LIPICS.ICALP.2019.99

[21] Joran van Apeldoorn, Andràs Gilyèn, Sander Gribling és Ronald de Wolf. „Kvantum sdp-megoldók: jobb felső és alsó határok”. Quantum 4, 230 (2020).
https://doi.org/10.22331/q-2020-02-14-230

[22] Fernando GSL Brandão és Krysta M. Svore. „Kvantumgyorsítások félig meghatározott programok megoldásához”. 2017-ben az IEEE 58. éves szimpóziuma a számítástechnika alapjairól (FOCS). 415–426. oldal. (2017).
https:///doi.org/10.1109/FOCS.2017.45

[23] Fernando GS L. Brandão, Richard Kueng és Daniel Stilck França. "Gyorsabb kvantum- és klasszikus SDP-közelítések másodfokú bináris optimalizáláshoz". Quantum 6, 625 (2022).
https://doi.org/10.22331/q-2022-01-20-625

[24] Dhrumil Patel, Patrick J. Coles és Mark M. Wilde. „Változatos kvantum-algoritmusok félig meghatározott programozáshoz” (2021). arXiv:2112.08859.
arXiv: 2112.08859

[25] Anirban N. Chowdhury, Guang Hao Low és Nathan Wiebe. „Változatos kvantum-algoritmus kvantumgibbs-állapotok elkészítéséhez” (2020). arXiv:2002.00055.
arXiv: 2002.00055

[26] Taylor L Patti, Omar Shehab, Khadijeh Najafi és Susanne F Yelin. „Markov-lánc monte carlo javított variációs kvantum algoritmusok”. Quantum Science and Technology 8, 015019 (2022).
https:///doi.org/10.1088/2058-9565/aca821

[27] Youle Wang, Guangxi Li és Xin Wang. „Változatos kvantumgibbs-állapot-előkészítés csonka taylor-sorozattal”. Physical Review Applied 16, 054035 (2021).
https:///doi.org/10.1103/PhysRevApplied.16.054035

[28] Sanjeev Arora, Elad Hazan és Satyen Kale. „A szorzósúlyok frissítési módszere: egy meta-algoritmus és alkalmazások”. Theory of Computing 8, 121–164 (2012).
https:///doi.org/10.4086/toc.2012.v008a006

[29] Iordanis Kerenidis és Anupam Prakash. „Kvantumbelső pont módszer lps-hez és sdps-hez”. ACM Transactions on Quantum Computing 1 (2020).
https:///doi.org/10.1145/3406306

[30] Brandon Augustino, Giacomo Nannicini, Terlaky Tamás és Luis F. Zuluaga. „Kvantumbelső pont módszerek félig meghatározott optimalizáláshoz” (2022). arXiv:2112.06025.
arXiv: 2112.06025

[31] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio és Patrick J. Coles. „Variációs kvantum algoritmusok”. Nature Reviews Physics 3, 625–644 (2021).
https://doi.org/10.1038/s42254-021-00348-9

[32] Kishor Bharti, Tobias Haug, Vlatko Vedral és Leong-Chuan Kwek. „Zajos, közepes léptékű kvantum algoritmus félig meghatározott programozáshoz”. Phys. Rev. A 105, 052445 (2022).
https:///doi.org/10.1103/PhysRevA.105.052445

[33] Lennart Bittel és Martin Kliesch. "A variációs kvantum algoritmusok képzése np-nehéz." Phys. Rev. Lett. 127, 120502 (2021).
https:///doi.org/10.1103/PhysRevLett.127.120502

[34] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush és Hartmut Neven. „Kivár fennsíkok kvantum-neurális hálózatok képzési tájain”. Nature Communications 9, 4812 (2018).
https://doi.org/10.1038/s41467-018-07090-4

[35] Carlos Ortiz Marrero, Mária Kieferová és Nathan Wiebe. „Az összefonódás okozta terméketlen fennsíkok”. PRX Quantum 2, 040316 (2021).
https:///doi.org/10.1103/PRXQuantum.2.040316

[36] Taylor L. Patti, Khadijeh Najafi, Xun Gao és Susanne F. Yelin. „Az összefonódás meddő fennsík enyhítését tervezte”. Phys. Rev. Res. 3, 033090 (2021).
https:///doi.org/10.1103/PhysRevResearch.3.033090

[37] Arthur Pesah, M. Cerezo, Samson Wang, Tyler Volkoff, Andrew T. Sornborger és Patrick J. Coles. „A meddő fennsíkok hiánya a kvantumkonvolúciós neurális hálózatokban”. Phys. Rev. X 11, 041011 (2021).
https:///doi.org/10.1103/PhysRevX.11.041011

[38] Dorit Aharonov, Vaughan Jones és Zeph Landau. „Polinomiális kvantum-algoritmus a Jones-polinom közelítésére”. Algorithmica 55, 395–421 (2009).
https://doi.org/10.1007/s00453-008-9168-0

[39] Clayton W. parancsnok. „Maximális vágási probléma, max-vágás-maximális vágási probléma, max-vágás”. 1991–1999. oldal. Springer USA. Boston, MA (2009).
https://doi.org/10.1007/978-0-387-74759-0_358

[40] Steven J. Benson, Yinyu Yeb és Xiong Zhang. „Vegyes lineáris és félig meghatározott programozás kombinatorikus és másodfokú optimalizáláshoz”. Optimization Methods and Software 11, 515–544 (1999).
https:///doi.org/10.1080/10556789908805761

[41] Changhui Choi és Yinyu Ye. „Ritka félig határozott programok megoldása kettős skálázási algoritmussal iteratív megoldóval”. Kézirat, Vezetéstudományi Tanszék, Iowa Egyetem, Iowa City, IA 52242 (2000). url: web.stanford.edu/ yyye/yyye/cgsdp1.pdf.
https:///web.stanford.edu/~yyye/yyye/cgsdp1.pdf

[42] Angelika Wiegele. „Biq mac library – közepes méretű max-cut és kvadratikus 0-1 programozási példányok gyűjteménye”. Alpen-Adria-Universität Klagenfurt (2007). url: biqmac.aau.at/biqmaclib.pdf.
https:///biqmac.aau.at/biqmaclib.pdf

[43] Stefan H. Schmieta. „A vegyes félhatáros-kvadratikus-lineáris programok dimacs könyvtára”. 7. DIMACS megvalósítási kihívás (2007). url: http:///archive.dimacs.rutgers.edu.
http:///archive.dimacs.rutgers.edu

[44] Yoshiki Matsuda. „A maximális vágási probléma összehasonlítása a szimulált bifurkációs gépen”. Közepes (2019). url: medium.com/toshiba-sbm/benchmarking-the-max-cut-problem-on-the-simulated-bifurcation-machine-e26e1127c0b0.
https:///medium.com/toshiba-sbm/benchmarking-the-max-cut-problem-on-the-simulated-bifurcation-machine-e26e1127c0b0

[45] RM Karp. „Reducibilitás a kombinatorikus problémák között”. Springer USA. Boston, MA (1972).

[46] Dimitri P Bertsekas. „Korlátozott optimalizálás és lagrange szorzó módszerek”. Akadémiai sajtó. (1982).
https://doi.org/10.1016/C2013-0-10366-2

[47] G Mauro D'Ariano, Matteo GA Paris és Massimiliano F Sacchi. „Kvantumtomográfia”. Advances in imaging and elektronphysics 128, 206–309 (2003).
https:///doi.org/10.48550/arXiv.quant-ph/0302028
arXiv:quant-ph/0302028

[48] Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D'Ariano, Stefano Facchini és Paolo Perinotti. „Optimális kvantumtomográfia”. IEEE Journal of Selected Topics in Quantum Electronics 15, 1646–1660 (2009).
https:///doi.org/10.1109/JSTQE.2009.2029243

[49] Max S. Kaznady és Daniel FV James. „Numerikus stratégiák kvantumtomográfiához: A teljes optimalizálás alternatívái”. Phys. Rev. A 79, 022109 (2009).
https:///doi.org/10.1103/PhysRevA.79.022109

[50] Javier Peña. „Elsőrendű módszerek konvergenciája a konvex konjugátumon keresztül”. Operations Research Letters 45, 561–564 (2017).
https:///doi.org/10.1016/j.orl.2017.08.013

[51] Alan Frieze és Mark Jerrum. "Továbbfejlesztett közelítési algoritmusok maxk-cut és max felezéshez". Algorithmica 18, 67–81 (1997).
https:///doi.org/10.1007/BF02523688

[52] Clark David Thompson. „A vlsi komplexitáselmélete”. PhD értekezés. Carnegie Mellon Egyetem. (1980). url: dl.acm.org/doi/10.5555/909758.
https:///dl.acm.org/doi/10.5555/909758

[53] Chu Min Li és Felip Manya. „Maxsat, kemény és lágy korlátok”. In Handbook of Satisfiability. 903–927. oldal. IOS Press (2021).
https://doi.org/10.3233/978-1-58603-929-5-613

[54] Nicholas J Higham. „A legközelebbi korrelációs mátrix kiszámítása – pénzügyi probléma”. IMA Journal of Numerical Analysis 22, 329–343 (2002).
https:///doi.org/10.1093/imanum/22.3.329

[55] Tadayoshi Fushiki. „Pozitív félig meghatározott korrelációs mátrixok becslése konvex másodfokú félig határozott programozással”. Neural Computation 21, 2028–2048 (2009).
https:///doi.org/10.1162/neco.2009.04-08-765

[56] Todd MJ. „A keresési irányok tanulmányozása primál-kettős belsőpontos módszerekben a félig meghatározott programozáshoz”. Optimalizálási módszerek és szoftverek 11, 1–46 (1999).
https:///doi.org/10.1080/10556789908805745

[57] Roger Fletcher. „Büntető funkciók”. Matematikai programozás A technika állása: Bonn 1982, 87–114. oldal (1983).
https://doi.org/10.1007/978-3-642-68874-4_5

[58] Robert M Freund. „Büntetés- és akadálymódszerek a korlátozott optimalizáláshoz”. Lecture Notes, Massachusetts Institute of Technology (2004). url: ocw.mit.edu/courses/15-084j-nonlinear-programming-spring-2004.
https:///ocw.mit.edu/courses/15-084j-nonlinear-programming-spring-2004

[59] Eric Ricardo Anschuetz. „Kritikus pontok a kvantumgeneratív modellekben”. Nemzetközi Tanulási Reprezentációk Konferencián. (2022). url: openreview.net/forum?id=2f1z55GVQN.
https:///openreview.net/forum?id=2f1z55GVQN

[60] Amir Beck. „Elsőrendű módszerek az optimalizálásban”. SZIÁM. (2017).
https:///doi.org/10.1137/1.9781611974997

[61] Sanjeev Arora és Satyen Kale. „A félig meghatározott programok kombinatorikus, primál-kettős megközelítése”. J. ACM 63 (2016).
https:///doi.org/10.1145/2837020

[62] Taylor L. Patti, Jean Kossaifi, Susanne F. Yelin és Anima Anandkumar. „Tensorly-quantum: Kvantumgépi tanulás tenzoros módszerekkel” (2021). arXiv:2112.10239.
arXiv: 2112.10239

[63] Jean Kossaifi, Yannis Panagakis, Anima Anandkumar és Maja Pantic. „Tensorly: Tensor learning in python”. Journal of Machine Learning Research 20, 1–6 (2019). url: http:///jmlr.org/papers/v20/18-277.html.
http:///jmlr.org/papers/v20/18-277.html

[64] cuQuantum csapat. „Nvidia/cuquantum: cuquantum v22.11” (2022).

[65] Diederik P. Kingma és Jimmy Ba. „Adam: A metódus a sztochasztikus optimalizáláshoz” (2017). arXiv:1412.6980.
arXiv: 1412.6980

[66] Brahim Chaourar. „Lineáris idő algoritmus a maximális vágási probléma egy változatához soros párhuzamos gráfokban”. Advances in Operations Research (2017).
https:///doi.org/10.1155/2017/1267108

[67] Jurij Makarycsev. „A kuratowski-féle gráf síksági kritériumának rövid bizonyítéka”. Journal of Graph Theory 25, 129–131 (1997).
<a href="https://doi.org/10.1002/(SICI)1097-0118(199706)25:23.0.CO;2-O”>https://doi.org/10.1002/(SICI)1097-0118(199706)25:2<129::AID-JGT4>3.0.CO;2-O

[68] Bollobás Béla. „A véletlen gráfok fejlődése – az óriási komponens”. 130–159. oldal. Cambridge-i tanulmányok haladó matematikából. Cambridge University Press. (2001). 2 kiadás.
https:///doi.org/10.1017/CBO9780511814068.008

[69] Sanjeev Arora, David Karger és Marek Karpinski. „Polinomiális időközelítési sémák np-kemény problémák sűrű példányaihoz”. Journal of Computer and System Sciences 58, 193–210 (1999).
https:///doi.org/10.1006/jcss.1998.1605

[70] Rick Durrett. „Erdös–rényi véletlen gráfok”. 27–69. oldal. Cambridge sorozat a statisztikai és valószínűségi matematikában. Cambridge University Press. (2006).
https:///doi.org/10.1017/CBO9780511546594.003

[71] Gary Chartrand és Ping Zhang. „Kromatikus gráfelmélet”. Taylor és Francis. (2008).
https:///doi.org/10.1201/9781584888017

[72] John van de Wetering. „Zx-számítás a dolgozó kvantuminformatikusoknak” (2020). arXiv:2012.13966.
arXiv: 2012.13966

[73] Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons és Seyon Sivarajah. „Fázisos modulszintézis sekély áramkörökhöz”. Electronic Proceedings in Theoretical Computer Science 318, 213–228 (2020).
https:///doi.org/10.4204/eptcs.318.13

[74] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe és Shuchen Zhu. „Az ügetőhiba elmélete kommutátor skálázással”. Phys. Rev. X 11, 011020 (2021).
https:///doi.org/10.1103/PhysRevX.11.011020

[75] Joseph W Britton, Brian C Sawyer, Adam C Keith, CC Joseph Wang, James K Freericks, Hermann Uys, Michael J Biercuk és John J Bollinger. "Műszaki kétdimenziós kölcsönhatások egy csapdába esett ion kvantumszimulátorban, több száz pörgetéssel." Nature 484, 489–492 (2012).
https:///doi.org/10.1038/nature10981

[76] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, Harry Levine, Ahmed Omran, Hannes Pichler, Soonwon Choi, Alexander S Zibrov, Manuel Endres, Markus Greiner és mások. „Sok test dinamikájának szondázása 51 atomos kvantumszimulátoron”. Nature 551, 579–584 (2017).
https:///doi.org/10.1038/nature24622

[77] Gheorghe-Sorin Paraoanu. „A szupravezető áramkörök felhasználásával végzett kvantumszimuláció legújabb eredményei”. Journal of Low Temperature Physics 175, 633–654 (2014).
https://doi.org/10.1007/s10909-014-1175-8

[78] Katsuki Fujisawa, Hitoshi Sato, Satoshi Matsuoka, Toshio Endo, Makoto Yamashita és Maho Nakata. „Nagy teljesítményű általános megoldó rendkívül nagy léptékű félig meghatározott programozási problémákhoz”. In SC '12: A nagy teljesítményű számítástechnikával, hálózatépítéssel, tárolással és elemzéssel foglalkozó nemzetközi konferencia anyaga. 1–11. oldal. (2012).
https:///doi.org/10.1109/SC.2012.67

[79] Adrian S. Lewis és Michael L. Overton. „Sajátérték optimalizálás”. Acta Numerica 5, 149–190 (1996).
https:///doi.org/10.1017/S0962492900002646

[80] Xiaosi Xu, Jinzhao Sun, Suguru Endo, Ying Li, Simon C. Benjamin és Xiao Yuan. „Variációs algoritmusok lineáris algebrához”. Science Bulletin 66, 2181–2188 (2021).
https:///doi.org/10.1016/j.scib.2021.06.023

Idézi

Nem sikerült lekérni Az adatok által hivatkozott kereszthivatkozás utolsó próbálkozáskor 2023-07-12 14:07:40: Nem sikerült lekérni a 10.22331/q-2023-07-12-1057 hivatkozás által hivatkozott adatokat a Crossref-től. Ez normális, ha a DOI-t nemrég regisztrálták. Tovább SAO/NASA HIRDETÉSEK művekre hivatkozó adat nem található (utolsó próbálkozás 2023-07-12 14:07:40).

Ez a tanulmány a Quantumban jelent meg Creative Commons Nevezd meg 4.0 International (CC BY 4.0) engedély. A szerzői jog az eredeti szerzői jog tulajdonosainál marad, például a szerzőknél vagy intézményeiknél.

SEO által támogatott tartalom és PR terjesztés. Erősödjön még ma.
PlatoData.Network Vertical Generative Ai. Erősítse meg magát. Hozzáférés itt.
PlatoAiStream. Web3 Intelligence. Felerősített tudás. Hozzáférés itt.
PlatoESG. Autóipar / elektromos járművek, Carbon, CleanTech, Energia, Környezet, Nap, Hulladékgazdálkodás. Hozzáférés itt.
BlockOffsets. A környezetvédelmi ellentételezési tulajdon korszerűsítése. Hozzáférés itt.
Forrás: https://quantum-journal.org/papers/q-2023-07-12-1057/

Időbélyeg: Július 12, 2023

Időbélyeg: 30. április 2024.

Kvantum Goemans-Williamson algoritmus Hadamard teszttel és közelítő amplitúdó megszorításokkal

Újra kiadta Platón

Absztrakt

Népszerű összefoglaló

► BibTeX adatok

► Referenciák

Idézi

Még több Quantum Journal

Gyorsan keveredő Markov-lánc bármely réses kvantum-sok testből álló rendszerből

Szinergikus kvantumhiba-csökkentés véletlenszerű fordítással és nulla zaj extrapolációval a variációs kvantum-sajátmegoldóhoz

Kvantumkapuk véletlenszerű univerzális halmazainak mátrixkoncentrációs egyenlőtlenségei és hatékonysága

Az összefonódás szerepéről a qudit alapú áramkör-tömörítésben

Továbbfejlesztett gravitációs összefonódás modulált optomechanikával

A kritikus kvantumhőmérséklet és megvalósíthatósága spinrendszerekben

A kvantum-inkompatibilitás különböző fogalmainak egyesítése a kommunikációs erőforrás-elméletek szigorú hierarchiájává

Tetszőleges méretű, valóban összefonódott alterek univerzális felépítése

Az extrém kvantumosság ortonormális alapjai

Pauli topológiai alrendszer kódjai az Abeli anyon elméletekből

Kvantumcsatornák közelítése teljesen pozitív, kis Kraus-rangú térképekkel

Rólunk

Vertical Search & Ai

Emelvény

Maradjon kapcsolatban

Fiók