Connect with us

Quantum

A quantum walk down memory lane

Published

on

In elementary and middle school, I felt an affinity for the class three years above mine. Five of my peers had siblings in that year. I carpooled with a student in that class, which partnered with mine in holiday activities and Grandparents’ Day revues. Two students in that class stood out. They won academic-achievement awards, represented our school in science fairs and speech competitions, and enrolled in rigorous high-school programs.

Those students came to mind as I grew to know David Limmer. David is an assistant professor of chemistry at the University of California, Berkeley. He studies statistical mechanics far from equilibrium, using information theory. Though a theorist ardent about mathematics, he partners with experimentalists. He can pass as a physicist and keeps an eye on topics as far afield as black holes. According to his faculty page, I discovered while writing this article, he’s even three years older than I. 

I met David in the final year of my PhD. I was looking ahead to postdocking, as his postdoc fellowship was fading into memory. The more we talked, the more I thought, I’d like to be like him.

Playground

I had the good fortune to collaborate with David on a paper published by Physical Review A this spring (as an Editors’ Suggestion!). The project has featured in Quantum Frontiers as the inspiration for a rewriting of “I’m a little teapot.” 

We studied a molecule prevalent across nature and technologies. Such molecules feature in your eyes, solar-fuel-storage devices, and more. The molecule has two clumps of atoms. One clump may rotate relative to the other if the molecule absorbs light. The rotation switches the molecule from a “closed” configuration to an “open” configuration.

Molecular switch

These molecular switches are small, quantum, and far from equilibrium; so modeling them is difficult. Making assumptions offers traction, but many of the assumptions disagreed with David. He wanted general, thermodynamic-style bounds on the probability that one of these molecular switches would switch. Then, he ran into me.

I traffic in mathematical models, developed in quantum information theory, called resource theories. We use resource theories to calculate which states can transform into which in thermodynamics, as a dime can transform into ten pennies at a bank. David and I modeled his molecule in a resource theory, then bounded the molecule’s probability of switching from “closed” to “open.” I accidentally composed a theme song for the molecule; you can sing along with this post.

That post didn’t mention what David and I discovered about quantum clocks. But what better backdrop for a mental trip to elementary school or to three years into the future?

I’ve blogged about autonomous quantum clocks (and ancient Assyria) before. Autonomous quantum clocks differ from quantum clocks of another type—the most precise clocks in the world. Scientists operate the latter clocks with lasers; autonomous quantum clocks need no operators. Autonomy benefits you if you want for a machine, such as a computer or a drone, to operate independently. An autonomous clock in the machine ensures that, say, the computer applies the right logical gate at the right time.

What’s an autonomous quantum clock? First, what’s a clock? A clock has a degree of freedom (e.g., a pair of hands) that represents the time and that moves steadily. When the clock’s hands point to 12 PM, you’re preparing lunch; when the clock’s hands point to 6 PM, you’re reading Quantum Frontiers. An autonomous quantum clock has a degree of freedom that represents the time fairly accurately and moves fairly steadily. (The quantum uncertainty principle prevents a perfect quantum clock from existing.)

Suppose that the autonomous quantum clock constitutes one part of a machine, such as a quantum computer, that the clock guides. When the clock is in one quantum state, the rest of the machine undergoes one operation, such as one quantum logical gate. (Experts: The rest of the machine evolves under one Hamiltonian.) When the clock is in another state, the rest of the machine undergoes another operation (evolves under another Hamiltonian).

Clock 2

Physicists have been modeling quantum clocks using the resource theory with which David and I modeled our molecule. The math with which we represented our molecule, I realized, coincided with the math that represents an autonomous quantum clock.

Think of the molecular switch as a machine that operates (mostly) independently and that contains an autonomous quantum clock. The rotating clump of atoms constitutes the clock hand. As a hand rotates down a clock face, so do the nuclei rotate downward. The hand effectively points to 12 PM when the switch occupies its “closed” position. The hand effectively points to 6 PM when the switch occupies its “open” position.

The nuclei account for most of the molecule’s weight; electrons account for little. They flit about the landscape shaped by the atomic clumps’ positions. The landscape governs the electrons’ behavior. So the electrons form the rest of the quantum machine controlled by the nuclear clock.

Clock 1

Experimentalists can create and manipulate these molecular switches easily. For instance, experimentalists can set the atomic clump moving—can “wind up” the clock—with ultrafast lasers. In contrast, the only other autonomous quantum clocks that I’d read about live in theory land. Can these molecules bridge theory to experiment? Reach out if you have ideas!

And check out David’s theory lab on Berkeley’s website and on Twitter. We all need older siblings to look up to.

Source: https://quantumfrontiers.com/2020/07/26/a-quantum-walk-down-memory-lane/

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

Esports3 days ago

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

Esports5 days ago

Best Shooting Badges in NBA 2K22: Which to Use

Esports4 days ago

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

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

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

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

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

Trending

Copyright © 2020 Plato Technologies Inc.