Connect with us

Quantum

Love in the time of thermo

Published

on

An 81-year-old medical doctor has fallen off a ladder in his house. His pet bird hopped out of his reach, from branch to branch of a tree on the patio. The doctor followed via ladder and slipped. His servants cluster around him, the clamor grows, and he longs for his wife to join him before he dies. She arrives at last. He gazes at her face; utters, “Only God knows how much I loved you”; and expires.

I set the book down on my lap and looked up. I was nestled in a wicker chair outside the Huntington Art Gallery in San Marino, California. Busts of long-dead Romans kept me company. The lawn in front of me unfurled below a sky that—unusually for San Marino—was partially obscured by clouds. My final summer at Caltech was unfurling. I’d walked to the Huntington, one weekend afternoon, with a novel from Caltech’s English library.1

What a novel.

You may have encountered the phrase “love in the time of corona.” Several times. Per week. Throughout the past six months. Love in the Time of Cholera predates the meme by 35 years. Nobel laureate Gabriel García Márquez captured the inhabitants, beliefs, architecture, mores, and spirit of a Colombian city around the turn of the 20th century. His work transcends its setting, spanning love, death, life, obsession, integrity, redemption, and eternity. A thermodynamicist couldn’t ask for more-fitting reading.

Love in the Time of Cholera centers on a love triangle. Fermina Daza, the only child of a wealthy man, excels in her studies. She holds herself with poise and self-assurance, and she spits fire whenever others try to control her. The girl dazzles Florentino Ariza, a poet, who restructures his life around his desire for her. Fermina Daza’s pride impresses Dr. Juvenal Urbino, a doctor renowned for exterminating a cholera epidemic. After rejecting both men, Fermina Daza marries Dr. Juvenal Urbino. The two personalities clash, and one betrays the other, but they cling together across the decades. Florentino Ariza retains his obsession with Fermina Daza, despite having countless affairs. Dr. Juvenal Urbino dies by ladder, whereupon Florentino Ariza swoops in to win Fermina Daza over. Throughout the book, characters mistake symptoms of love for symptoms of cholera; and lovers block out the world by claiming to have cholera and self-quarantining.

As a thermodynamicist, I see the second law of thermodynamics in every chapter. The second law implies that time marches only forward, order decays, and randomness scatters information to the wind. García Márquez depicts his characters aging, aging more, and aging more. Many characters die. Florentino Ariza’s mother loses her memory to dementia or Alzheimer’s disease. A pawnbroker, she buys jewels from the elite whose fortunes have eroded. Forgetting the jewels’ value one day, she mistakes them for candies and distributes them to children.

The second law bites most, to me, in the doctor’s final words, “Only God knows how much I loved you.” Later, the widow Fermina Daza sighs, “It is incredible how one can be happy for so many years in the midst of so many squabbles, so many problems, damn it, and not really know if it was love or not.” She doesn’t know how much her husband loved her, especially in light of the betrayal that rocked the couple and a rumor of another betrayal. Her husband could have affirmed his love with his dying breath, but he refused: He might have loved her with all his heart, and he might not have loved her; he kept the truth a secret to all but God. No one can retrieve the information after he dies.2 

Love in the Time of Cholera—and thermodynamics—must sound like a mouthful of horseradish. But each offers nourishment, an appetizer and an entrée. According to the first law of thermodynamics, the amount of energy in every closed, isolated system remains constant: Physics preserves something. Florentino Ariza preserves his love for decades, despite Fermina Daza’s marrying another man, despite her aging.

The latter preservation can last only so long in the story: Florentino Ariza, being mortal, will die. He claims that his love will last “forever,” but he won’t last forever. At the end of the novel, he sails between two harbors—back and forth, back and forth—refusing to finish crossing a River Styx. I see this sailing as prethermalization: A few quantum systems resist thermalizing, or flowing to the physics analogue of death, for a while. But they succumb later. Florentino Ariza can’t evade the far bank forever, just as the second law of thermodynamics forbids his boat from functioning as a perpetuum mobile.

Though mortal within his story, Florentino Ariza survives as a book character. The book survives. García Márquez wrote about a country I’d never visited, and an era decades before my birth, 33 years before I checked his book out of the library. But the book dazzled me. It pulsed with the vibrancy, color, emotion, and intellect—with the fullness—of life. The book gained another life when the coronavius hit. Thermodynamics dictates that people age and die, but the laws of thermodynamics remain.3 I hope and trust—with the caveat about humanity’s not destroying itself—that Love in the Time of Cholera will pulse in 350 years. 

What’s not to love?

1Yes, Caltech has an English library. I found gems in it, and the librarians ordered more when I inquired about books they didn’t have. I commend it to everyone who has access.

2I googled “Only God knows how much I loved you” and was startled to see the line depicted as a hallmark of romance. Please tell your romantic partners how much you love them; don’t make them guess till the ends of their lives.

3Lee Smolin has proposed that the laws of physics change. If they do, the change seems to have to obey metalaws that remain constant.

Source: https://quantumfrontiers.com/2020/09/20/love-in-the-time-of-thermo/

Quantum

Self-testing of a single quantum device under computational assumptions

Published

on

Tony Metger1 and Thomas Vidick2

1Institute for Theoretical Physics, ETH Zürich, 8093 Zürich, Switzerland
2Department of Computing and Mathematical Sciences, California Institute of Technology, CA 91125, United States

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of $textit{multiple non-communicating}$ parties, which is difficult to enforce in practice, by a $textit{single computationally bounded}$ party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.

► BibTeX data

► References

[1] W. Aiello, S. Bhatt, R. Ostrovsky, and S. R. Rajagopalan. “Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP”, Automata, Languages and Programming – ICALP 2000, Lecture Notes in Computer Science, Springer, 463-474 (2000).
https:/​/​doi.org/​10.1007/​3-540-45022-X_39

[2] G. Alagic, A. M. Childs, A. B. Grilo, and S.-H. Hung. “Non-interactive classical verification of quantum computation”, Preprint (2019). arXiv:1911.08101.
arXiv:1911.08101

[3] M. Ben-Or, C. Crepeau, D. Gottesman, A. Hassidim, and A. Smith. “Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority”, IEEE 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 249-260 (2006).
https:/​/​doi.org/​10.1109/​FOCS.2006.68

[4] Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani, and T. Vidick. “A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device”, IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 320-331 (2018). arXiv:1804.00640v3.
https:/​/​doi.org/​10.1109/​FOCS.2018.00038
arXiv:1804.00640v3

[5] J. S. Bell. “On the Einstein Podolsky Rosen paradox”, Physics Physique Fizika 1, 195–200 (1964).
https:/​/​doi.org/​10.1103/​PhysicsPhysiqueFizika.1.195

[6] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani. “On the complexity and verification of quantum random circuit sampling”, Nature Physics 15, 159–163 (2019).
https:/​/​doi.org/​10.1038/​s41567-018-0318-2

[7] A. Broadbent and A. B. Grilo. “QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge”, IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 196–205 (2020).
https:/​/​doi.org/​10.1109/​FOCS46700.2020.00027

[8] Z. Brakerski, V. Koppula, U. Vazirani, and T. Vidick. “Simpler Proofs of Quantumness”, Preprint (2020). arXiv:2005.04826.
arXiv:2005.04826

[9] K. Bharti, M. Ray, A. Varvitsiotis, N. A. Warsi, A. Cabello, and L.-C. Kwek. “Robust Self-Testing of Quantum Systems via Noncontextuality Inequalities”, Phys. Rev. Lett. 122, 250403 (2019). arXiv:1812.07265.
https:/​/​doi.org/​10.1103/​PhysRevLett.122.250403
arXiv:1812.07265

[10] A. Cojocaru, L. Colisson, E. Kashefi, and P. Wallden. “QFactory: Classically-Instructed Remote Secret Qubits Preparation”, Advances in Cryptology – ASIACRYPT 2019, Lecture Notes in Computer Science, Springer, 615-645 (2019). arXiv:1904.06303.
https:/​/​doi.org/​10.1007/​978-3-030-34578-5_22
arXiv:1904.06303

[11] N.-H. Chia, K.-M. Chung, and T. Yamakawa. “Classical Verification of Quantum Computations with Efficient Verifier”, Preprint (2019). arXiv:1912.00990.
arXiv:1912.00990

[12] A. Coladangelo, A. B. Grilo, S. Jeffery, and T. Vidick. “Verifier-on-a-leash: New schemes for verifiable delegated quantum computation, with quasilinear resources”, Advances in Cryptology – EUROCRYPT 2019, Lecture Notes in Computer Science, Springer 11478 LNCS, 247-277 (2019). arXiv:1708.07359.
https:/​/​doi.org/​10.1007/​978-3-030-17659-4_9
arXiv:1708.07359

[13] C. Crépeau, D. Gottesman, and A. Smith. “Secure Multi-Party Quantum Computation”, Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 643-652 (2002).
https:/​/​doi.org/​10.1145/​509907.510000

[14] A. Coladangelo, K. T. Goh, and V. Scarani. “All pure bipartite entangled states can be self-tested”, Nature Communications 8, 15485 (2017). arXiv:1611.08062.
https:/​/​doi.org/​10.1038/​ncomms15485
arXiv:1611.08062

[15] R. Colbeck. Quantum and relativistic protocols for secure multi-party computation, PhD Thesis, University of Cambridge (2006). arXiv:0911.3814.
arXiv:0911.3814

[16] A. Coladangelo, T. Vidick, and T. Zhang. “Non-interactive zero-knowledge arguments for QMA, with preprocessing”, Annual International Cryptology Conference (CRYPTO), 799–828 (2020).
https:/​/​doi.org/​10.1007/​978-3-030-56877-1_28

[17] Y. Dodis, S. Halevi, R. D. Rothblum, and D. Wichs. “Spooky Encryption and Its Applications”, Advances in Cryptology – CRYPTO 2016, Lecture Notes in Computer Science, Springer, 93-122 (2016).
https:/​/​doi.org/​10.1007/​978-3-662-53015-3_4

[18] W. T. Gowers and O. Hatami. “Inverse and stability theorems for approximate representations of finite groups”, Sbornik: Mathematics 208, 1784 (2017).
https:/​/​doi.org/​10.1070/​SM8872

[19] A. Gheorghiu and T. Vidick. “Computationally-secure and composable remote state preparation”, IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 1024–1033 (2019).
https:/​/​doi.org/​10.1109/​FOCS.2019.00066

[20] Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen. “${MIP}^*={RE}$”, Preprint (2020). arXiv:2001.04383.
arXiv:2001.04383

[21] Y. T. Kalai, R. Raz, and R. D. Rothblum. “How to Delegate Computations: The Power of No-Signaling Proofs”, Proceedings of the 46th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 485-494 (2014).
https:/​/​doi.org/​10.1145/​2591796.2591809

[22] U. Mahadev. “Classical Verification of Quantum Computations”, IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 259-267 (2018). arXiv:1804.01082v2.
https:/​/​doi.org/​10.1109/​FOCS.2018.00033
arXiv:1804.01082v2

[23] T. Metger, Y. Dulek, A. Coladangelo, and R. Arnon-Friedman. “Device-independent quantum key distribution from computational assumptions”, Preprint (2020). arXiv:2010.04175.
arXiv:2010.04175

[24] C. A. Miller and Y. Shi. “Universal Security for Randomness Expansion from the Spot-Checking Protocol”, SIAM Journal on Computing 46, 1304-1335 (2017). arXiv:1411.6608.
https:/​/​doi.org/​10.1137/​15M1044333
arXiv:1411.6608

[25] D. Mayers and A. Yao. “Self Testing Quantum Apparatus”, Quantum Info. Comput. 4, 273-286 (2004). arXiv:quant-ph/​0307205.
arXiv:quant-ph/0307205
https:/​/​dl.acm.org/​doi/​10.5555/​2011827.2011830

[26] M. McKague, T. H. Yang, and V. Scarani. “Robust self-testing of the singlet”, Journal of Physics A: Mathematical and Theoretical 45, 455304 (2012).
https:/​/​doi.org/​10.1088/​1751-8113/​45/​45/​455304

[27] A. Natarajan and J. Wright. “NEEXP in MIP*”, IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 510-518 (2019). arXiv:1904.05870.
https:/​/​doi.org/​10.1109/​FOCS.2019.00039
arXiv:1904.05870

[28] S. Popescu and D. Rohrlich. “Which states violate Bell’s inequality maximally?”, Physics Letters A 169, 411–414 (1992).
https:/​/​doi.org/​10.1016/​0375-9601(92)90819-8

[29] R. Raz. “A parallel repetition theorem”, SIAM Journal on Computing 27, 763–803 (1998).
https:/​/​doi.org/​10.1137/​S0097539795280895

[30] O. Regev. “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography”, J. ACM 56 (2009).
https:/​/​doi.org/​10.1145/​1568318.1568324

[31] B. W. Reichardt, F. Unger, and U. Vazirani. “Classical command of quantum systems”, Nature 496, 456 (2013). arXiv:1209.0449.
https:/​/​doi.org/​10.1038/​nature12035
arXiv:1209.0449

[32] I. Šupić and J. Bowles. “Self-testing of quantum systems: a review”, Preprint (2019). arXiv:1904.10042.
https:/​/​doi.org/​10.22331/​q-2020-09-30-337
arXiv:1904.10042

[33] V. Scarani. Bell Nonlocality, Oxford University Press (2019).

[34] S. J. Summers and R. Werner. “Maximal violation of Bell’s inequalities is generic in quantum field theory”, Communications in Mathematical Physics 110, 247–259 (1987).
https:/​/​doi.org/​10.1007/​BF01207366

[35] T. Vidick. The complexity of entangled games. PhD thesis, 2011.
https:/​/​digitalassets.lib.berkeley.edu/​etd/​ucb/​text/​Vidick_berkeley_0028E_11907.pdf

[36] U. Vazirani and T. Vidick. “Certifiable Quantum Dice: Or, True Random Number Generation Secure against Quantum Adversaries”, Proceedings of the 44th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 61-76 (2012). arXiv:1111.6054.
https:/​/​doi.org/​10.1145/​2213977.2213984
arXiv:1111.6054

[37] T. Vidick and T. Zhang. “Classical proofs of quantum knowledge”, Preprint (2020). arXiv:2005.01691.
arXiv:2005.01691

[38] M. Wilde. “From Classical to Quantum Shannon Theory”, Preprint (2011). arXiv:1106.1445v8.
https:/​/​doi.org/​10.1017/​9781316809976.001
arXiv:1106.1445v8

Cited by

[1] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik, “Noisy intermediate-scale quantum (NISQ) algorithms”, arXiv:2101.08448.

[2] Alexandru Gheorghiu and Matty J. Hoban, “Estimating the entropy of shallow circuit outputs is hard”, arXiv:2002.12814.

[3] Thomas Vidick and Tina Zhang, “Classical proofs of quantum knowledge”, arXiv:2005.01691.

[4] Yu Cai, Baichu Yu, Pooja Jayachandran, Nicolas Brunner, Valerio Scarani, and Jean-Daniel Bancal, “Entanglement for any definition of two subsystems”, Physical Review A 103 5, 052432 (2021).

[5] Tony Metger, Yfke Dulek, Andrea Coladangelo, and Rotem Arnon-Friedman, “Device-independent quantum key distribution from computational assumptions”, arXiv:2010.04175.

[6] Tomoyuki Morimae, “Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center”, arXiv:2003.10712.

[7] Tomoyuki Morimae and Yuki Takeuchi, “Trusted center verification model and classical channel remote state preparation”, arXiv:2008.05033.

[8] Kishor Bharti, Maharshi Ray, Zhen-Peng Xu, Masahito Hayashi, Leong-Chuan Kwek, and Adán Cabello, “Graph-Theoretic Framework for Self-Testing in Bell Scenarios”, arXiv:2104.13035.

The above citations are from SAO/NASA ADS (last updated successfully 2021-09-16 17:11:41). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-09-16 17:11:40: Could not fetch cited-by data for 10.22331/q-2021-09-16-544 from Crossref. This is normal if the DOI was registered recently.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.

Source: https://quantum-journal.org/papers/q-2021-09-16-544/

Continue Reading

Quantum

Quantum algorithms and approximating polynomials for composed functions with shared inputs

Published

on

Mark Bun1, Robin Kothari2, and Justin Thaler3

1Boston University
2Microsoft Quantum
3Georgetown University

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be an $m$-bit Boolean function and consider an $n$-bit function $F$ obtained by applying $f$ to conjunctions of possibly overlapping subsets of $n$ variables. If $f$ has quantum query complexity $Q(f)$, we give an algorithm for evaluating $F$ using $tilde{O}(sqrt{Q(f) cdot n})$ quantum queries. This improves on the bound of $O(Q(f) cdot sqrt{n})$ that follows by treating each conjunction independently, and our bound is tight for worst-case choices of $f$. Using completely different techniques, we prove a similar tight composition theorem for the approximate degree of $f$.
By recursively applying our composition theorems, we obtain a nearly optimal $tilde{O}(n^{1-2^{-d}})$ upper bound on the quantum query complexity and approximate degree of linear-size depth-$d$ AC$^0$ circuits. As a consequence, such circuits can be PAC learned in subexponential time, even in the challenging agnostic setting. Prior to our work, a subexponential-time algorithm was not known even for linear-size depth-3 AC$^0$ circuits.
As an additional consequence, we show that AC$^0 circ oplus$ circuits of depth $d+1$ require size $tilde{Omega}(n^{1/(1- 2^{-d})}) geq omega(n^{1+ 2^{-d}} )$ to compute the Inner Product function even on average. The previous best size lower bound was $Omega(n^{1+4^{-(d+1)}})$ and only held in the worst case (Cheraghchi et al., JCSS 2018).

► BibTeX data

► References

[1] Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, and Alon Rosen. Candidate weak pseudorandom functions in AC$^0 circ mathsf{MOD}_2$. In Proceedings of the 5th conference on Innovations in theoretical computer science, ITCS ’14, pages 251–260, 2014.
https:/​/​doi.org/​10.1145/​2554797.2554821

[2] Miklos Ajtai and Michael Ben-Or. A theorem on probabilistic constant depth computations. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC ’84, pages 471–474, 1984.
https:/​/​doi.org/​10.1145/​800057.808715

[3] Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang. Any AND-OR formula of size $N$ can be evaluated in time $N^{1/​2 + o(1)}$ on a quantum computer. SIAM Journal on Computing, 39(6):2513–2530, 2010.
https:/​/​doi.org/​10.1137/​080712167

[4] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510–1523, 1997.
https:/​/​doi.org/​10.1137/​S0097539796300933

[5] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001.
https:/​/​doi.org/​10.1145/​502090.502097

[6] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4-5):493–505, 1998.
3.0.CO;2-P”>https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P

[7] Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka. Bounds for small-error and zero-error quantum algorithms. In 40th Annual Symposium on Foundations of Computer Science, pages 358–368, 1999.
https:/​/​doi.org/​10.1109/​sffcs.1999.814607

[8] Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan. On the power of statistical zero knowledge. In 58th Annual Symposium on Foundations of Computer Science (FOCS 2017), pages 708–719, 2017.
https:/​/​doi.org/​10.1109/​focs.2017.71

[9] Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288(1):21–43, 2002.
https:/​/​doi.org/​10.1016/​S0304-3975(01)00144-X

[10] Mark Bun, Robin Kothari, and Justin Thaler. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 297–310, 2018.
https:/​/​doi.org/​10.1145/​3188745.3188784

[11] Mark Bun, Robin Kothari, and Justin Thaler. Quantum algorithms and approximating polynomials for composed functions with shared inputs. In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 662–678, 2019.
https:/​/​doi.org/​10.1137/​1.9781611975482.42

[12] Paul Beame and Widad Machmouchi. The quantum query complexity of AC$^0$. Quantum Information & Computation, 12(7-8):670–676, 2012.

[13] Harry Buhrman, Ilan Newman, Hein Röhrig, and Ronald de Wolf. Robust polynomials and quantum algorithms. Theory of Computing Systems, 40(4):379–395, 2007.
https:/​/​doi.org/​10.1007/​s00224-006-1313-z

[14] Jehoshua Bruck and Roman Smolensky. Polynomial threshold functions, AC$^0$ functions, and spectral norms. SIAM Journal on Computing, 21(1):33–42, 1992.
https:/​/​doi.org/​10.1137/​0221003

[15] Mark Bun and Justin Thaler. A nearly optimal lower bound on the approximate degree of AC$^0$. In IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS 2017), pages 1–12, 2017.
https:/​/​doi.org/​10.1109/​FOCS.2017.10

[16] Mark Bun and Justin Thaler. Guest column: Approximate degree in classical and quantum computing. SIGACT News, 51(4):48–72, January 2021.
https:/​/​doi.org/​10.1145/​3444815.3444825

[17] Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo. Discrete-query quantum algorithm for NAND trees. Theory of Computing, 5:119–123, 2009.
https:/​/​doi.org/​10.4086/​toc.2009.v005a005

[18] Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie. AC0 $circ$ MOD2 lower bounds for the Boolean inner product. In LIPIcs-Leibniz International Proceedings in Informatics, volume 55. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2016.35

[19] Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability of small depth circuits. In International Workshop on Parameterized and Exact Computation, pages 75–85, 2009.
https:/​/​doi.org/​10.1007/​978-3-642-11269-0_6

[20] Andrew M. Childs, Shelby Kimmel, and Robin Kothari. The quantum query complexity of read-many formulas. In 20th Annual European Symposium on Algorithms (ESA 2012), pages 337–348, 2012.
https:/​/​doi.org/​10.1007/​978-3-642-33090-2_30

[21] Shiva Chaudhuri and Jaikumar Radhakrishnan. Deterministic restrictions in circuit complexity. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, STOC ’96, pages 30–36, 1996.
https:/​/​doi.org/​10.1145/​237814.237824

[22] Gil Cohen and Igor Shinkar. The complexity of DNF of parities. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 47–58, 2016.
https:/​/​doi.org/​10.1145/​2840728.2840734

[23] Ning Ding, Yanli Ren, and Dawu Gu. PAC learning depth-3 AC$^0$ circuits of bounded top fanin. In Proceedings of the 28th International Conference on Algorithmic Learning Theory, volume 76 of Proceedings of Machine Learning Research, pages 667–680, 2017. URL: http:/​/​proceedings.mlr.press/​v76/​ding17a.html.
http:/​/​proceedings.mlr.press/​v76/​ding17a.html

[24] Michael Ezra and Ron D. Rothblum. Small circuits imply efficient Arthur-Merlin protocols. Technical Report TR21-127, Electronic Colloquium on Computational Complexity (ECCC), 2021. URL: https:/​/​eccc.weizmann.ac.il/​report/​2021/​127/​.
https:/​/​eccc.weizmann.ac.il/​report/​2021/​127/​

[25] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4(1):169–190, 2008.
https:/​/​doi.org/​10.4086/​toc.2008.v004a008

[26] Yuval Filmus, Hamed Hatami, Steven Heilman, Elchanan Mossel, Ryan O’Donnell, Sushant Sachdeva, Andrew Wan, and Karl Wimmer. Real analysis in computer science: A collection of open problems, 2014. URL: https:/​/​simons.berkeley.edu/​sites/​default/​files/​openprobsmerged.pdf.
https:/​/​simons.berkeley.edu/​sites/​default/​files/​openprobsmerged.pdf

[27] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC ’96, pages 212–219, 1996.
https:/​/​doi.org/​10.1145/​237814.237866

[28] Peter Høyer, Troy Lee, and Robert Špalek. Negative weights make adversaries stronger. In Proceedings of the 39th Symposium on Theory of Computing (STOC 2007), pages 526–535, 2007.
https:/​/​doi.org/​10.1145/​1250790.1250867

[29] Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 37(6):1777–1805, 2008.
https:/​/​doi.org/​10.1137/​060649057

[30] Adam Klivans, Pravesh Kothari, and Igor C. Oliveira. Constructing hard functions using learning algorithms. In IEEE Conference on Computational Complexity (CCC 2013), pages 86–97, 2013.
https:/​/​doi.org/​10.1109/​CCC.2013.18

[31] Michal Koucký, Clemens Lautemann, Sebastian Poloczek, and Denis Therien. Circuit lower bounds via Ehrenfeucht-Fraisse games. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), pages 190–201, 07 2006.
https:/​/​doi.org/​10.1109/​CCC.2006.12

[32] Swastik Kopparty. AC0 lower bounds and pseudorandomness. Lecture notes of “Topics in Complexity Theory and Pseudorandomness (Spring 2013)” at Rutgers University. http:/​/​sites.math.rutgers.edu/​ sk1233/​courses/​topics-S13/​lec4.pdf (Retrieved July 12, 2018), 2013.
http:/​/​sites.math.rutgers.edu/​~sk1233/​courses/​topics-S13/​lec4.pdf

[33] Michal Koucký. Circuit complexity of regular languages. Theory of Computing Systems, 45(4):865–879, 2009.
https:/​/​doi.org/​10.1007/​s00224-009-9180-z

[34] Adam R. Klivans and Rocco A. Servedio. Learning DNF in time $2^{{tilde O}(n^{1/​3})}$. Journal of Computer and System Sciences, 68(2):303–318, 2004.
https:/​/​doi.org/​10.1016/​j.jcss.2003.07.007

[35] Michael J. Kearns, Robert E. Schapire, and Linda M. Sellie. Toward efficient agnostic learning. Machine Learning, 17(2-3):115–141, 1994.
https:/​/​doi.org/​10.1007/​bf00993468

[36] Wee Sun Lee, Peter L. Bartlett, and Robert C. Williamson. On efficient agnostic learning of linear combinations of basis functions. In Proceedings of the eighth annual conference on Computational learning theory, pages 369–376, 1995.
https:/​/​doi.org/​10.1145/​225298.225343

[37] Troy Lee. Slides for the paper “improved quantum query algorithms for triangle finding and associativity testing” by T. Lee, F. Magniez, M. Santha. Available at http:/​/​research.cs.rutgers.edu/​ troyjlee/​troy_triangle.pdf (Retrieved July 11, 2018), 2012.
http:/​/​research.cs.rutgers.edu/​~troyjlee/​troy_triangle.pdf

[38] Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science, 3(4):263–399, 2009.
https:/​/​doi.org/​10.1561/​0400000040

[39] Noam Nisan. Shortest formula for an $n$-term monotone CNF. Theoretical Computer Science Stack Exchange, 2011. https:/​/​cstheory.stackexchange.com/​q/​7087 (version: 2011-06-23).
https:/​/​cstheory.stackexchange.com/​q/​7087

[40] Noam Nisan and Mario Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4:301–313, 1994.
https:/​/​doi.org/​10.1007/​BF01263419

[41] Igor C. Carboni Oliveira and Rahul Santhanam. Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. In 32nd Computational Complexity Conference (CCC 2017), volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:49, 2017.
https:/​/​doi.org/​10.4230/​LIPIcs.CCC.2017.18

[42] Alexander A Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333–338, 1987.

[43] Ben Reichardt. Reflections for quantum query algorithms. In SODA ’11: Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms, pages 560–569, 2011.
https:/​/​doi.org/​10.1137/​1.9781611973082.44

[44] Alexander A. Razborov and Alexander A. Sherstov. The sign-rank of AC$^0$. SIAM Journal on Computing, 39(5):1833–1855, 2010.
https:/​/​doi.org/​10.1137/​080744037

[45] Prabhakar Ragde and Avi Wigderson. Linear-size constant-depth polylog-threshold circuits. Information Processing Letters, 39(3):143–146, 1991.
https:/​/​doi.org/​10.1016/​0020-0190(91)90110-4

[46] Alexander A. Sherstov. The pattern matrix method. SIAM Journal on Computing, 40(6):1969–2000, 2011.
https:/​/​doi.org/​10.1137/​080733644

[47] Alexander A. Sherstov. Strong direct product theorems for quantum communication and query complexity. In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC 2011), pages 41–50, 2011.
https:/​/​doi.org/​10.1145/​1993636.1993643

[48] Alexander A. Sherstov. The intersection of two halfspaces has high threshold degree. SIAM Journal on Computing, 42(6):2329–2374, 2013.
https:/​/​doi.org/​10.1137/​100785260

[49] Alexander A. Sherstov. Making polynomials robust to noise. Theory of Computing, 9:593–615, 2013.
https:/​/​doi.org/​10.4086/​toc.2013.v009a018

[50] Alexander A. Sherstov. The power of asymmetry in constant-depth circuits. In IEEE 56th Annual Symposium on Foundations of Computer Science, pages 431–450, 2015.
https:/​/​doi.org/​10.1109/​FOCS.2015.34

[51] Alexander A. Sherstov. Algorithmic polynomials. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), 2018.
https:/​/​doi.org/​10.1145/​3188745.3188958

[52] Rahul Santhanam and Srikanth Srinivasan. On the limits of sparsification. In International Colloquium on Automata, Languages, and Programming, pages 774–785. Springer, 2012.
https:/​/​doi.org/​10.1007/​978-3-642-31594-7_65

[53] Rocco A. Servedio and Li-Yang Tan. What Circuit Classes Can Be Learned with Non-Trivial Savings? In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1–30:21, 2017.
https:/​/​doi.org/​10.4230/​LIPIcs.ITCS.2017.30

[54] Rocco A Servedio and Emanuele Viola. On a special case of rigidity. Technical Report TR12-144, Electronic Colloquium on Computational Complexity (ECCC), 2012. URL: https:/​/​eccc.weizmann.ac.il/​report/​2012/​144/​.
https:/​/​eccc.weizmann.ac.il/​report/​2012/​144/​

[55] Avishay Tal. The bipartite formula complexity of inner-product is quadratic. Technical Report TR16-181, Electronic Colloquium on Computational Complexity (ECCC), 2016. URL: https:/​/​eccc.weizmann.ac.il/​report/​2016/​181/​.
https:/​/​eccc.weizmann.ac.il/​report/​2016/​181/​

[56] Avishay Tal. Formula lower bounds via the quantum method. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pages 1256–1268, 2017.
https:/​/​doi.org/​10.1145/​3055399.3055472

[57] Avishay Tal. Personal communication, 2018.

[58] Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, Nov 1984.
https:/​/​doi.org/​10.1145/​1968.1972

Cited by

[1] Scott Aaronson, Daniel Grier, and Luke Schaeffer, “A Quantum Query Complexity Trichotomy for Regular Languages”, arXiv:1812.04219.

[2] Kamil Khadiev and Liliya Safina, “Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs”, arXiv:1804.09950.

The above citations are from SAO/NASA ADS (last updated successfully 2021-09-16 14:44:06). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-09-16 14:44:04: Could not fetch cited-by data for 10.22331/q-2021-09-16-543 from Crossref. This is normal if the DOI was registered recently.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.

Source: https://quantum-journal.org/papers/q-2021-09-16-543/

Continue Reading

Quantum

Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size

Published

on

Jahan Claes1,2 and Wim van Dam1,3,4

1QC Ware Corporation, Palo Alto, CA USA
2Department of Physics and Institute for Condensed Matter Theory, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA
3Department of Computer Science, University of California, Santa Barbara, CA USA
4Department of Physics, University of California, Santa Barbara, CA USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

This paper studies the application of the Quantum Approximate Optimization Algorithm (QAOA) to spin-glass models with random multi-body couplings in the limit of a large number of spins. We show that for such mixed-spin models the performance of depth $1$ QAOA is independent of the specific instance in the limit of infinite sized systems and we give an explicit formula for the expected performance. We also give explicit expressions for the higher moments of the expected energy, thereby proving that the expected performance of QAOA concentrates.

► BibTeX data

► References

[1] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014. URL https:/​/​arxiv.org/​abs/​1411.4028.
arXiv:1411.4028

[2] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The quantum approximate optimization algorithm and the Sherrington-Kirkpatrick model at infinite size. arXiv preprint arXiv:1910.08187, 2019. URL https:/​/​arxiv.org/​abs/​1910.08187.
arXiv:1910.08187

[3] Andrea Montanari. Optimization of the Sherrington–Kirkpatrick hamiltonian. SIAM Journal on Computing, 0 (0): FOCS19–1, 2021. 10.1137/​20M132016X.
https:/​/​doi.org/​10.1137/​20M132016X

[4] Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Optimization of mean-field spin glasses. arXiv preprint arXiv:2001.00904, 2020. URL https:/​/​arxiv.org/​abs/​2001.00904.
arXiv:2001.00904

[5] Ahmed El Alaoui and Andrea Montanari. Algorithmic thresholds in mean field spin glasses. arXiv preprint arXiv:2009.11481, 2020. URL https:/​/​arxiv.org/​abs/​2009.11481.
arXiv:2009.11481

[6] Zhang Jiang, Eleanor G Rieffel, and Zhihui Wang. Near-optimal quantum circuit for Grover’s unstructured search using a transverse field. Physical Review A, 95 (6): 062317, 2017. 10.1103/​PhysRevA.95.062317.
https:/​/​doi.org/​10.1103/​PhysRevA.95.062317

[7] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G Rieffel. Quantum approximate optimization algorithm for maxcut: A fermionic view. Physical Review A, 97 (2): 022304, 2018. 10.1103/​PhysRevA.97.022304.
https:/​/​doi.org/​10.1103/​PhysRevA.97.022304

[8] Asier Ozaeta, Wim van Dam, and Peter L. McMahon. Expectation values from the single-layer quantum approximate optimization algorithm on Ising problems. arXiv preprint arXiv:2012.03421, 2020. URL https:/​/​arxiv.org/​abs/​2012.03421.
arXiv:2012.03421

[9] Gavin E Crooks. Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv preprint arXiv:1811.08419, 2018. URL https:/​/​arxiv.org/​abs/​1811.08419.
arXiv:1811.08419

[10] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X, 10 (2): 021067, 2020. 10.1103/​PhysRevX.10.021067.
https:/​/​doi.org/​10.1103/​PhysRevX.10.021067

[11] Fernando GSL Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances. arXiv preprint arXiv:1812.04170, 2018. URL https:/​/​arxiv.org/​abs/​1812.04170.
arXiv:1812.04170

[12] David Sherrington and Scott Kirkpatrick. Solvable model of a spin-glass. Physical Review Letters, 35 (26): 1792, 1975. 10.1103/​PhysRevLett.35.1792.
https:/​/​doi.org/​10.1103/​PhysRevLett.35.1792

[13] Giorgio Parisi. A sequence of approximated solutions to the SK model for spin glasses. Journal of Physics A: Mathematical and General, 13 (4): L115, 1980. 10.1088/​0305-4470/​13/​4/​009.
https:/​/​doi.org/​10.1088/​0305-4470/​13/​4/​009

[14] Michel Talagrand. The Parisi formula. Annals of mathematics, pages 221–263, 2006. 10.4007/​annals.2006.163.221.
https:/​/​doi.org/​10.4007/​annals.2006.163.221

[15] Dmitry Panchenko. The Sherrington-Kirkpatrick model: an overview. Journal of Statistical Physics, 149 (2): 362–383, 2012. 10.1007/​s10955-012-0586-7.
https:/​/​doi.org/​10.1007/​s10955-012-0586-7

[16] Dmitry Panchenko. The Sherrington-Kirkpatrick model. Springer Science & Business Media, 2013. 10.1007/​978-1-4614-6289-7.
https:/​/​doi.org/​10.1007/​978-1-4614-6289-7

[17] Antonio Auffinger, Wei-Kuo Chen, et al. Parisi formula for the ground state energy in the mixed $ p $-spin model. Annals of Probability, 45 (6B): 4617–4631, 2017. 10.1214/​16-AOP1173.
https:/​/​doi.org/​10.1214/​16-AOP1173

[18] Dmitry Panchenko et al. The Parisi formula for mixed $p$-spin models. Annals of Probability, 42 (3): 946–958, 2014. 10.1214/​12-AOP800.
https:/​/​doi.org/​10.1214/​12-AOP800

[19] Leo Zhou, Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. The quantum approximate optimization algorithm and the Sherrington-Kirkpatrick model at infinite size. Talk presented at QIP, 2021. URL https:/​/​youtu.be/​UP-Zuke7IUg.
https:/​/​youtu.be/​UP-Zuke7IUg

Cited by

[1] V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte, “Parameter concentrations in quantum approximate optimization”, Physical Review A 104 1, L010401 (2021).

[2] E. Campos, D. Rabinovich, V. Akshay, and J. Biamonte, “Training Saturation in Layerwise Quantum Approximate Optimisation”, arXiv:2106.13814.

[3] Jordi R. Weggemans, Alexander Urech, Alexander Rausch, Robert Spreeuw, Richard Boucherie, Florian Schreck, Kareljan Schoutens, Jiří Minář, and Florian Speelman, “Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach”, arXiv:2106.11672.

The above citations are from SAO/NASA ADS (last updated successfully 2021-09-15 16:50:26). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-09-15 16:50:24: Could not fetch cited-by data for 10.22331/q-2021-09-15-542 from Crossref. This is normal if the DOI was registered recently.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.

Source: https://quantum-journal.org/papers/q-2021-09-15-542/

Continue Reading

Quantum

Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size

Published

on

Jahan Claes1,2 and Wim van Dam1,3,4

1QC Ware Corporation, Palo Alto, CA USA
2Department of Physics and Institute for Condensed Matter Theory, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA
3Department of Computer Science, University of California, Santa Barbara, CA USA
4Department of Physics, University of California, Santa Barbara, CA USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

This paper studies the application of the Quantum Approximate Optimization Algorithm (QAOA) to spin-glass models with random multi-body couplings in the limit of a large number of spins. We show that for such mixed-spin models the performance of depth $1$ QAOA is independent of the specific instance in the limit of infinite sized systems and we give an explicit formula for the expected performance. We also give explicit expressions for the higher moments of the expected energy, thereby proving that the expected performance of QAOA concentrates.

► BibTeX data

► References

[1] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014. URL https:/​/​arxiv.org/​abs/​1411.4028.
arXiv:1411.4028

[2] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The quantum approximate optimization algorithm and the Sherrington-Kirkpatrick model at infinite size. arXiv preprint arXiv:1910.08187, 2019. URL https:/​/​arxiv.org/​abs/​1910.08187.
arXiv:1910.08187

[3] Andrea Montanari. Optimization of the Sherrington–Kirkpatrick hamiltonian. SIAM Journal on Computing, 0 (0): FOCS19–1, 2021. 10.1137/​20M132016X.
https:/​/​doi.org/​10.1137/​20M132016X

[4] Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Optimization of mean-field spin glasses. arXiv preprint arXiv:2001.00904, 2020. URL https:/​/​arxiv.org/​abs/​2001.00904.
arXiv:2001.00904

[5] Ahmed El Alaoui and Andrea Montanari. Algorithmic thresholds in mean field spin glasses. arXiv preprint arXiv:2009.11481, 2020. URL https:/​/​arxiv.org/​abs/​2009.11481.
arXiv:2009.11481

[6] Zhang Jiang, Eleanor G Rieffel, and Zhihui Wang. Near-optimal quantum circuit for Grover’s unstructured search using a transverse field. Physical Review A, 95 (6): 062317, 2017. 10.1103/​PhysRevA.95.062317.
https:/​/​doi.org/​10.1103/​PhysRevA.95.062317

[7] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G Rieffel. Quantum approximate optimization algorithm for maxcut: A fermionic view. Physical Review A, 97 (2): 022304, 2018. 10.1103/​PhysRevA.97.022304.
https:/​/​doi.org/​10.1103/​PhysRevA.97.022304

[8] Asier Ozaeta, Wim van Dam, and Peter L. McMahon. Expectation values from the single-layer quantum approximate optimization algorithm on Ising problems. arXiv preprint arXiv:2012.03421, 2020. URL https:/​/​arxiv.org/​abs/​2012.03421.
arXiv:2012.03421

[9] Gavin E Crooks. Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv preprint arXiv:1811.08419, 2018. URL https:/​/​arxiv.org/​abs/​1811.08419.
arXiv:1811.08419

[10] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X, 10 (2): 021067, 2020. 10.1103/​PhysRevX.10.021067.
https:/​/​doi.org/​10.1103/​PhysRevX.10.021067

[11] Fernando GSL Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances. arXiv preprint arXiv:1812.04170, 2018. URL https:/​/​arxiv.org/​abs/​1812.04170.
arXiv:1812.04170

[12] David Sherrington and Scott Kirkpatrick. Solvable model of a spin-glass. Physical Review Letters, 35 (26): 1792, 1975. 10.1103/​PhysRevLett.35.1792.
https:/​/​doi.org/​10.1103/​PhysRevLett.35.1792

[13] Giorgio Parisi. A sequence of approximated solutions to the SK model for spin glasses. Journal of Physics A: Mathematical and General, 13 (4): L115, 1980. 10.1088/​0305-4470/​13/​4/​009.
https:/​/​doi.org/​10.1088/​0305-4470/​13/​4/​009

[14] Michel Talagrand. The Parisi formula. Annals of mathematics, pages 221–263, 2006. 10.4007/​annals.2006.163.221.
https:/​/​doi.org/​10.4007/​annals.2006.163.221

[15] Dmitry Panchenko. The Sherrington-Kirkpatrick model: an overview. Journal of Statistical Physics, 149 (2): 362–383, 2012. 10.1007/​s10955-012-0586-7.
https:/​/​doi.org/​10.1007/​s10955-012-0586-7

[16] Dmitry Panchenko. The Sherrington-Kirkpatrick model. Springer Science & Business Media, 2013. 10.1007/​978-1-4614-6289-7.
https:/​/​doi.org/​10.1007/​978-1-4614-6289-7

[17] Antonio Auffinger, Wei-Kuo Chen, et al. Parisi formula for the ground state energy in the mixed $ p $-spin model. Annals of Probability, 45 (6B): 4617–4631, 2017. 10.1214/​16-AOP1173.
https:/​/​doi.org/​10.1214/​16-AOP1173

[18] Dmitry Panchenko et al. The Parisi formula for mixed $p$-spin models. Annals of Probability, 42 (3): 946–958, 2014. 10.1214/​12-AOP800.
https:/​/​doi.org/​10.1214/​12-AOP800

[19] Leo Zhou, Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. The quantum approximate optimization algorithm and the Sherrington-Kirkpatrick model at infinite size. Talk presented at QIP, 2021. URL https:/​/​youtu.be/​UP-Zuke7IUg.
https:/​/​youtu.be/​UP-Zuke7IUg

Cited by

[1] V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte, “Parameter concentrations in quantum approximate optimization”, Physical Review A 104 1, L010401 (2021).

[2] E. Campos, D. Rabinovich, V. Akshay, and J. Biamonte, “Training Saturation in Layerwise Quantum Approximate Optimisation”, arXiv:2106.13814.

[3] Jordi R. Weggemans, Alexander Urech, Alexander Rausch, Robert Spreeuw, Richard Boucherie, Florian Schreck, Kareljan Schoutens, Jiří Minář, and Florian Speelman, “Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach”, arXiv:2106.11672.

The above citations are from SAO/NASA ADS (last updated successfully 2021-09-15 16:50:26). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-09-15 16:50:24: Could not fetch cited-by data for 10.22331/q-2021-09-15-542 from Crossref. This is normal if the DOI was registered recently.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.

Source: https://quantum-journal.org/papers/q-2021-09-15-542/

Continue Reading
Crowdfunding4 days ago

Conister Bank Lends More to Time Finance

Esports5 days ago

NBA 2K22 Lightning Green Animation: How to Claim

Esports4 days ago

Rocket League Championship Series (RLCS) is expanding to more regions, features new format and $6 million prize pool for 2021-22 season

Esports3 days ago

NBA 2K22 The Game Quest Explained

Esports5 days ago

NBA 2K22 MyCareer Takeover Perks: Which to Use

Esports4 days ago

The VCS hasn’t given up on Worlds 2021, continues to work with Riot to find a solution to travel restrictions, reports say

Esports2 days ago

Shiny Zacian and Zamazenta promotion announced for Pokémon Brilliant Diamond, Shining Pearl preorders in South Korea

Esports5 days ago

Best Shooting Badges in NBA 2K22: Which to Use

Esports3 days ago

Riot to launch new client that houses all of the company’s desktop titles in one hub, rollout begins next week

Esports4 days ago

New 2021 Tin of Ancient Battles content confirms Yu-Gi-Oh! TCG is finally getting Crossout Designator, lots of good reprints

Cyber Security3 days ago

How To Choose The Right Sales Training Software For Your Team?

Energy3 days ago

Technipaq Partners with DuPont™ Tyvek® and Freepoint Eco-Systems to Reduce and Recycle Medical Packaging Plastic Waste

Esports2 days ago

How to download Deltarune Chapter 2

Esports4 days ago

New 2021 Tin of Ancient Battles content confirms Yu-Gi-Oh! TCG is finally getting Crossout Designator, lots of good reprints

Energy3 days ago

Kontrol Technologies to Participate in Virtual Energy Conference on September 21st, 2021

Esports5 days ago

Riot lowers Ryze’s Q AP ratio, nerfs Soraka’s ultimate healing in detailed preview for League’s Patch 11.19

Energy3 days ago

Momentum Manufacturing Group’s Strength Earns Third Straight Vermont Business Growth Award

Energy3 days ago

Teamsters Denounce Billionaire John Catsimatidis For Firing Striking Workers

Esports4 days ago

Rocket League Championship Series (RLCS) is expanding to more regions, features new format and $6 million prize pool for 2021-22 season

Esports4 days ago

Rocket League Championship Series (RLCS) is expanding to more regions, features new format and $6 million prize pool for 2021-22 season

Trending

Copyright © 2020 Plato Technologies Inc.