Zephyrnet Logosu

Tensör Temel Bileşen Analizi için Klasik ve Kuantum Algoritmaları

Tarih:

Matthew B.Hastings

Station Q, Microsoft Research, Santa Barbara, CA 93106-6105, ABD
Microsoft Quantum ve Microsoft Research, Redmond, WA 98052, ABD

Bu makaleyi ilginç mi buldunuz yoksa tartışmak mı istiyorsunuz? SciRate'e çığlık at veya yorum bırak.

Özet

Tensör temel bileşen analizindeki bir problem için spektral yöntemlere dayalı klasik ve kuantum algoritmaları sunuyoruz. Kuantum algoritması, en hızlı klasik spektral algoritmadan katlanarak daha küçük alan kullanırken bir $quartic$ hızlanma ve yalnızca polinom uzay kullanan klasik algoritmalara göre bir süper-polinom hızlanma elde eder. Sunduğumuz klasik algoritmalar, yakın zamanda Ref. [1]. Özellikle, kurtarma için gelişmiş bir eşiğimiz var ve sunduğumuz algoritmalar hem çift hem de tek dereceli tensörler için çalışıyor. Bu sonuçlar, büyük ölçekli çıkarım problemlerinin kuantum bilgisayarlar için gelecek vaat eden bir uygulama olduğunu göstermektedir.

► BibTeX verileri

► Referanslar

[1] Alexander S Wein, Ahmed El Alaoui ve Cristopher Moore. Kikuchi hiyerarşisi ve tensör pca. 2019.arXiv:1904.03858.
arXiv: 1904.03858

[2] Andrea Montanari ve Emile Richard. Tensör pca için istatistiksel bir model. Sinirsel Bilgi İşleme Sistemlerindeki Gelişmeler, sayfalar 2897–2905, 2014.

[3] Thibault Lesieur, Leo Miolane, Marc Lelarge, Florent Krzakala ve Lenka Zdeborova. Çivili tensör tahmininde istatistiksel ve hesaplamalı faz geçişleri. 2017'de IEEE Uluslararası Bilgi Teorisi Sempozyumu (ISIT). IEEE, haziran 2017. doi:10.1109/​isit.2017.8006580.
https:/​/​doi.org/10.1109/​isit.2017.8006580

[4] Samuel B Hopkins, Jonathan Shi ve David Steurer. Kareler toplamı kanıtları aracılığıyla tensör ana bileşen analizi. Learning Theory Konferansında, sayfalar 956–1006, 2015.

[5] Samuel B. Hopkins, Tselil Schramm, Jonathan Shi ve David Steurer. Kareler toplamı kanıtlarından hızlı spektral algoritmalar: tensör ayrışımı ve dikilmiş seyrek vektörler. Hesaplama Teorisi üzerine 48. Yıllık ACM SIGACT Sempozyumu Bildiri Kitabında – STOC 2016. ACM Press, 2016. doi:10.1145/​2897518.2897529.
https: / / doi.org/ 10.1145 / 2897518.2897529

[6] Vijay VSP Bhattiprolu, Mrinalkanti Ghosh, Euiwoong Lee, Venkatesan Guruswami ve Madhur Tulsiani. Birim küre üzerinde polinom optimizasyonu için çarpımsal yaklaşımlar. CoRR, abs/​1611.05998, 2016. URL: http://​/arxiv.org/​abs/1611.05998, arXiv:1611.05998.
arXiv: 1611.05998

[7] Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee ve Madhur Tulsiani. Küre üzerinde zayıf dekuplaj, polinom kıvrımlar ve yaklaşık optimizasyon. 2017'de IEEE 58. Yıllık Bilgisayar Biliminin Temelleri Sempozyumu (FOCS). IEEE, ekim 2017. doi:10.1109/​focs.2017.97.
https: / / doi.org/ 10.1109 / focs.2017.97

[8] RF Werner. Büyük sapmalar ve ortalama alan kuantum sistemleri. Kuantum Olasılığı ve İlgili Konular'da, sayfa 349–381. WORLD SCIENTIFIC, temmuz 1992. doi:10.1142/​9789814354783_0024.
https: / / doi.org/ 10.1142 / 9789814354783_0024

[9] Christina V. Kraus, Maciej Lewenstein ve J. Ignacio Cirac. Permütasyon simetrisine sahip fermiyonik kafes Hamiltonianlarının temel durumları. Physical Review A, 88(2), ağustos 2013. doi:10.1103/​physreva.88.022335.
https: / / doi.org/ 10.1103 / physreva.88.022335

[10] Fernando GSL Brandão ve Aram W. Harrow. Kuantum durumlarına ürün durumu yaklaşımları. Communications in Mathematical Physics, 342(1):47–80, Ocak 2016. doi:10.1007/​s00220-016-2575-1.
https:/​/​doi.org/​10.1007/​s00220-016-2575-1

[11] Scott Aaronson ve Lijie Chen. Kuantum üstünlüğü deneylerinin karmaşıklık-teorik temelleri. 32. Hesaplamalı Karmaşıklık Konferansında (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. arXiv:1612.05903.
arXiv: 1612.05903

[12] Madan Lal Mehta. Rastgele matrisler, cilt 142. Elsevier, 2004.

[13] James Demmel, Ioana Dumitriu ve Olga Holtz. Hızlı doğrusal cebir kararlıdır. Numerische Mathematik, 108(1):59–91, ekim 2007. doi:10.1007/​s00211-007-0114-x.
https: / / doi.org/ 10.1007 / s00211-007-0114-x

[14] Guang Hao Low ve Isaac L. Chuang. Kuantum sinyal işleme ile optimum Hamilton simülasyonu. fizik Rev. Lett., 118:010501, 2017. arXiv:1606.02685v2, doi:10.1103/​PhysRevLett.118.010501.
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501
arXiv: 1606.02685v2

[15] Guang Hao Low ve Isaac L Chuang. Qubitizasyon ile Hamilton simülasyonu. 2016. arXiv:1610.06546 https://​/doi.org/​10.22331/​q-2019-07-12-163.
https:/​/​doi.org/​10.22331/​q-2019-07-12-163
arXiv: 1610.06546

[16] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari ve Rolando D. Somma. Seyrek Hamiltoniyenleri simüle etmek için hassasiyette üstel iyileştirme. sayfalar 283–292, 2014. arXiv:1312.1414, doi:10.1145/​2591796.2591854.
https: / / doi.org/ 10.1145 / 2591796.2591854
arXiv: 1312.1414

[17] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari ve Rolando D. Somma. Kesik bir Taylor serisiyle Hamilton dinamiklerini simüle etmek. fizik Rev. Lett., 114:090502, 2015. arXiv:1412.4687, doi:10.1103/​PhysRevLett.114.090502.
https: / / doi.org/ 10.1103 / PhysRevLett.114.090502
arXiv: 1412.4687

[18] DW Berry, AM Childs ve R. Kothari. Tüm parametrelere neredeyse optimal bağımlılık ile Hamilton simülasyonu. 2015 yılında IEEE 56. Bilgisayar Biliminin Temelleri Yıllık Sempozyumu, sayfa 792–809, Ekim 2015. arXiv:1501.01715, doi:10.1109/​FOCS.2015.54.
https: / / doi.org/ 10.1109 / FOCS.2015.54
arXiv: 1501.01715

[19] Alexei Yu Kitaev, Alexander Shen ve Mikhail N Vyalyi. Klasik ve kuantum hesaplama, cilt 47. American Mathematical Society Providence, 2002. doi:10.1090/gsm/​047.
https: / / doi.org/ 10.1090 / gsm / 047

[20] Gilles Brassard, Peter Hoyer, Michele Mosca ve Alain Tapp. Kuantum genlik amplifikasyonu ve tahmini. Çağdaş Matematik, 305:53–74, 2002. doi:10.1090/​conm/​305.
https: / / doi.org/ 10.1090 / conm / 305

[21] Anthony Carbery ve James Wright. ${R^n}$'daki dışbükey cisimler üzerindeki polinomlar için dağıtımsal ve ${L^q}$ norm eşitsizlikleri. Mathematical Research Letters, 8(3):233–248, 2001. doi:10.4310/​mrl.2001.v8.n3.a1.
https:/​/​doi.org/​10.4310/​mrl.2001.v8.n3.a1

[22] Dave Wecker, Matthew B. Hastings, Nathan Wiebe, Bryan K. Clark, Chetan Nayak ve Matthias Troyer. Bir kuantum bilgisayarda güçlü bir şekilde ilişkili elektron modellerini çözme. Fiziksel İnceleme A, 92(6), Aralık 2015. doi:10.1103/​physreva.92.062318.
https: / / doi.org/ 10.1103 / physreva.92.062318

< p class="break">[23] Matthew B. Hastings. Kuantum maks-akış min-kesiminin asimptotikleri. Communications in Mathematical Physics, 351(1):387–418, Kasım 2016. doi:10.1007/​s00220-016-2791-8.
https:/​/​doi.org/​10.1007/​s00220-016-2791-8

Alıntılama

[1] Alexander S. Wein, Ahmed El Alaoui ve Cristopher Moore, "The Kikuchi Hiyerarşisi ve Tensor PCA", arXiv: 1904.03858.

Yukarıdaki alıntılar SAO / NASA REKLAMLARI (son başarıyla 2020-02-28 01:28:52) güncellendi. Tüm yayıncılar uygun ve eksiksiz alıntı verisi sağlamadığından liste eksik olabilir.

On Crossref'in alıntı yaptığı hizmet alıntı yapma çalışmaları ile ilgili veri bulunamadı (son deneme 2020-02-28 01:28:50).

Kaynak: https://quantum-journal.org/papers/q-2020-02-27-237/

spot_img

En Son İstihbarat

spot_img