Connect with us

Quantum

Spacetime Quantum Reference Frames and superpositions of proper times

Published

on

Flaminia Giacomini

Perimeter Institute for Theoretical Physics, 31 Caroline St. N, Waterloo, Ontario, N2L 2Y5, Canada

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

Abstract

In general relativity, the description of spacetime relies on idealised rods and clocks, which identify a reference frame. In any concrete scenario, reference frames are associated to physical systems, which are ultimately quantum in nature. A relativistic description of the laws of physics hence needs to take into account such quantum reference frames (QRFs), through which spacetime can be given an operational meaning.

Here, we introduce the notion of a spacetime quantum reference frame, associated to a quantum particle in spacetime. Such formulation has the advantage of treating space and time on equal footing, and of allowing us to describe the dynamical evolution of a set of quantum systems from the perspective of another quantum system, where the parameter in which the rest of the physical systems evolves coincides with the proper time of the particle taken as the QRF. Crucially, the proper times in two different QRFs are not related by a standard transformation, but they might be in a quantum superposition one with respect to the other.

Concretely, we consider a system of $N$ relativistic quantum particles in a weak gravitational field, and introduce a timeless formulation in which the global state of the $N$ particles appears “frozen”, but the dynamical evolution is recovered in terms of relational quantities. The position and momentum Hilbert space of the particles is used to fix the QRF via a transformation to the local frame of the particle such that the metric is locally inertial at the origin of the QRF. The internal Hilbert space corresponds to the clock space, which keeps the proper time in the local frame of the particle. Thanks to this fully relational construction we show how the remaining particles evolve dynamically in the relational variables from the perspective of the QRF. The construction proposed here includes the Page-Wootters mechanism for non interacting clocks when the external degrees of freedom are neglected. Finally, we find that a quantum superposition of gravitational redshifts and a quantum superposition of special-relativistic time dilations can be observed in the QRF.

► BibTeX data

► References

[1] Yakir Aharonov and Leonard Susskind. Charge Superselection Rule. Phys. Rev., 155: 1428–1431, 1967a. 10.1103/​PhysRev.155.1428. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRev.155.1428.
https:/​/​doi.org/​10.1103/​PhysRev.155.1428

[2] Yakir Aharonov and Leonard Susskind. Observability of the sign change of spinors under $2{pi}$ rotations. Phys. Rev., 158: 1237–1238, 1967b. 10.1103/​PhysRev.158.1237. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRev.158.1237.
https:/​/​doi.org/​10.1103/​PhysRev.158.1237

[3] Y. Aharonov and T. Kaufherr. Quantum frames of reference. Phys. Rev. D, 30: 368–385, 1984. 10.1103/​PhysRevD.30.368. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevD.30.368.
https:/​/​doi.org/​10.1103/​PhysRevD.30.368

[4] Stephen D. Bartlett, Terry Rudolph, and Robert W. Spekkens. Reference frames, superselection rules, and quantum information. Rev. Mod. Phys., 79: 555–609, 2007. 10.1103/​RevModPhys.79.555. URL https:/​/​link.aps.org/​doi/​10.1103/​RevModPhys.79.555.
https:/​/​doi.org/​10.1103/​RevModPhys.79.555

[5] Stephen D. Bartlett, Terry Rudolph, Robert W. Spekkens, and Peter S. Turner. Quantum communication using a bounded-size quantum reference frame. New J. Phys., 11 (6): 063013, 2009. 10.1088/​1367-2630/​11/​6/​063013. URL http:/​/​stacks.iop.org/​1367-2630/​11/​i=6/​a=063013.
https:/​/​doi.org/​10.1088/​1367-2630/​11/​6/​063013
http:/​/​stacks.iop.org/​1367-2630/​11/​i=6/​a=063013

[6] Gilad Gour and Robert W Spekkens. The resource theory of quantum reference frames: manipulations and monotones. New J. Phys., 10 (3): 033023, 2008. 10.1088/​1367-2630/​10/​3/​033023. URL http:/​/​stacks.iop.org/​1367-2630/​10/​i=3/​a=033023.
https:/​/​doi.org/​10.1088/​1367-2630/​10/​3/​033023
http:/​/​stacks.iop.org/​1367-2630/​10/​i=3/​a=033023

[7] Alexei Kitaev, Dominic Mayers, and John Preskill. Superselection rules and quantum protocols. Phys. Rev. A, 69 (5): 052326, 2004. 10.1103/​PhysRevA.69.052326.
https:/​/​doi.org/​10.1103/​PhysRevA.69.052326

[8] Matthew C. Palmer, Florian Girelli, and Stephen D. Bartlett. Changing quantum reference frames. Phys. Rev. A, 89: 052121, 2014. 10.1103/​PhysRevA.89.052121. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.89.052121.
https:/​/​doi.org/​10.1103/​PhysRevA.89.052121

[9] Stephen D Bartlett, Terry Rudolph, Robert W Spekkens, and Peter S Turner. Degradation of a quantum reference frame. New J. Phys., 8 (4): 58, 2006. 10.1088/​1367-2630/​8/​4/​058. URL http:/​/​stacks.iop.org/​1367-2630/​8/​i=4/​a=058.
https:/​/​doi.org/​10.1088/​1367-2630/​8/​4/​058
http:/​/​stacks.iop.org/​1367-2630/​8/​i=4/​a=058

[10] Alexander R. H. Smith, Marco Piani, and Robert B. Mann. Quantum reference frames associated with noncompact groups: The case of translations and boosts and the role of mass. Phys. Rev. A, 94: 012333, 2016. 10.1103/​PhysRevA.94.012333. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.94.012333.
https:/​/​doi.org/​10.1103/​PhysRevA.94.012333

[11] David Poulin and Jon Yard. Dynamics of a quantum reference frame. New J. Phys., 9 (5): 156, 2007. 10.1088/​1367-2630/​9/​5/​156. URL http:/​/​stacks.iop.org/​1367-2630/​9/​i=5/​a=156.
https:/​/​doi.org/​10.1088/​1367-2630/​9/​5/​156
http:/​/​stacks.iop.org/​1367-2630/​9/​i=5/​a=156

[12] Florian Girelli and David Poulin. Quantum reference frames and deformed symmetries. Phys. Rev. D, 77: 104012, 2008. 10.1103/​PhysRevD.77.104012. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevD.77.104012.
https:/​/​doi.org/​10.1103/​PhysRevD.77.104012

[13] Michael Skotiniotis, Borzu Toloui, Ian T. Durham, and Barry C. Sanders. Quantum Frameness for $CPT$ Symmetry. Phys. Rev. Lett., 111: 020504, 2013. 10.1103/​PhysRevLett.111.020504. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.111.020504.
https:/​/​doi.org/​10.1103/​PhysRevLett.111.020504

[14] David Poulin. Toy model for a relational formulation of quantum theory. Int. J. Theor. Phys., 45 (7): 1189–1215, 2006. 10.1007/​s10773-006-9052-0.
https:/​/​doi.org/​10.1007/​s10773-006-9052-0

[15] Takayuki Miyadera, Leon Loveridge, and Paul Busch. Approximating relational observables by absolute quantities: a quantum accuracy-size trade-off. J. Phys. A, 49 (18): 185301, 2016. 10.1088/​1751-8113/​49/​18/​185301. URL http:/​/​stacks.iop.org/​1751-8121/​49/​i=18/​a=185301.
https:/​/​doi.org/​10.1088/​1751-8113/​49/​18/​185301
http:/​/​stacks.iop.org/​1751-8121/​49/​i=18/​a=185301

[16] L. Loveridge, P. Busch, and T. Miyadera. Relativity of quantum states and observables. EPL (Europhysics Letters), 117 (4): 40004, 2017. 10.1209/​0295-5075/​117/​40004. URL http:/​/​stacks.iop.org/​0295-5075/​117/​i=4/​a=40004.
https:/​/​doi.org/​10.1209/​0295-5075/​117/​40004
http:/​/​stacks.iop.org/​0295-5075/​117/​i=4/​a=40004

[17] Leon Loveridge, Takayuki Miyadera, and Paul Busch. Symmetry, reference frames, and relational quantities in quantum mechanics. Found. Phys., 48 (2): 135–198, 2018. 10.1007/​s10701-018-0138-3.
https:/​/​doi.org/​10.1007/​s10701-018-0138-3

[18] Jacques Pienaar. A relational approach to quantum reference frames for spins. arXiv:1601.07320, 2016.
arXiv:1601.07320

[19] Renato M Angelo, Nicolas Brunner, Sandu Popescu, Anthony J Short, and Paul Skrzypczyk. Physics within a quantum reference frame. J. Phys. A, 44 (14): 145304, 2011. 10.1088/​1751-8113/​44/​14/​145304. URL https:/​/​doi.org/​10.1088/​1751-8113/​44/​14/​145304.
https:/​/​doi.org/​10.1088/​1751-8113/​44/​14/​145304

[20] R M Angelo and A D Ribeiro. Kinematics and dynamics in noninertial quantum frames of reference. J. Phys. A, 45 (46): 465306, 2012. 10.1088/​1751-8113/​45/​46/​465306. URL https:/​/​doi.org/​10.1088/​1751-8113/​45/​46/​465306.
https:/​/​doi.org/​10.1088/​1751-8113/​45/​46/​465306

[21] S. T. Pereira and R. M. Angelo. Galilei covariance and Einstein’s equivalence principle in quantum reference frames. Phys. Rev. A, 91: 022107, 2015. 10.1103/​PhysRevA.91.022107. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.91.022107.
https:/​/​doi.org/​10.1103/​PhysRevA.91.022107

[22] Bryce S DeWitt. Quantum theory of gravity. I. The canonical theory. Phys. Rev., 160 (5): 1113, 1967. 10.1103/​PhysRev.160.1113.
https:/​/​doi.org/​10.1103/​PhysRev.160.1113

[23] C Rovelli. Quantum reference systems. Class. Quant. Grav., 8 (2): 317, 1991. 10.1088/​0264-9381/​8/​2/​012. URL http:/​/​stacks.iop.org/​0264-9381/​8/​i=2/​a=012.
https:/​/​doi.org/​10.1088/​0264-9381/​8/​2/​012
http:/​/​stacks.iop.org/​0264-9381/​8/​i=2/​a=012

[24] Carlo Rovelli. Relational quantum mechanics. Int. J. Theor. Phys., 35 (8): 1637–1678, 1996. 10.1007/​BF02302261.
https:/​/​doi.org/​10.1007/​BF02302261

[25] Flaminia Giacomini, Esteban Castro-Ruiz, and Časlav Brukner. Quantum mechanics and the covariance of physical laws in quantum reference frames. Nat. Commun., 10 (1): 494, 2019a. 10.1038/​s41467-018-08155-0. URL https:/​/​doi.org/​10.1038/​s41467-018-08155-0.
https:/​/​doi.org/​10.1038/​s41467-018-08155-0

[26] Augustin Vanrietvelde, Philipp A Höhn, Flaminia Giacomini, and Esteban Castro-Ruiz. A change of perspective: switching quantum reference frames via a perspective-neutral framework. Quantum, 4: 225, 2020. 10.22331/​q-2020-01-27-225.
https:/​/​doi.org/​10.22331/​q-2020-01-27-225

[27] Augustin Vanrietvelde, Philipp A Höhn, and Flaminia Giacomini. Switching quantum reference frames in the N-body problem and the absence of global relational perspectives. arXiv:1809.05093, 2018.
arXiv:1809.05093

[28] Jianhao M. Yang. Switching Quantum Reference Frames for Quantum Measurement. Quantum, 4: 283, June 2020. 10.22331/​q-2020-06-18-283. URL https:/​/​doi.org/​10.22331/​q-2020-06-18-283.
https:/​/​doi.org/​10.22331/​q-2020-06-18-283

[29] Flaminia Giacomini, Esteban Castro-Ruiz, and Časlav Brukner. Relativistic quantum reference frames: the operational meaning of spin. Phys. Rev. Lett., 123 (9): 090404, 2019b. 10.1103/​PhysRevLett.123.090404.
https:/​/​doi.org/​10.1103/​PhysRevLett.123.090404

[30] Lucas F. Streiter, Flaminia Giacomini, and Časlav Brukner. Relativistic bell test within quantum reference frames. Phys. Rev. Lett., 126: 230403, Jun 2021. 10.1103/​PhysRevLett.126.230403. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.126.230403.
https:/​/​doi.org/​10.1103/​PhysRevLett.126.230403

[31] Anne-Catherine de la Hamette and Thomas D. Galley. Quantum reference frames for general symmetry groups. Quantum, 4: 367, November 2020. 10.22331/​q-2020-11-30-367. URL https:/​/​doi.org/​10.22331/​q-2020-11-30-367.
https:/​/​doi.org/​10.22331/​q-2020-11-30-367

[32] Marius Krumm, Philipp A. Hoehn, and Markus P. Mueller. Quantum reference frame transformations as symmetries and the paradox of the third particle. arXiv:2011.01951, 2020.
arXiv:2011.01951

[33] Angel Ballesteros, Flaminia Giacomini, and Giulia Gubitosi. The group structure of dynamical transformations between quantum reference frames. Quantum, 5: 470, 2021. 10.22331/​q-2021-06-08-470.
https:/​/​doi.org/​10.22331/​q-2021-06-08-470

[34] Don N. Page and William K. Wootters. Evolution without evolution: Dynamics described by stationary observables. Phys. Rev. D, 27: 2885, 1983. 10.1103/​PhysRevD.27.2885.
https:/​/​doi.org/​10.1103/​PhysRevD.27.2885

[35] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum time. Phys. Rev. D, 92 (4): 045033, 2015. 10.1103/​PhysRevD.92.045033.
https:/​/​doi.org/​10.1103/​PhysRevD.92.045033

[36] Esteban Castro-Ruiz, Flaminia Giacomini, Alessio Belenchia, and Časlav Brukner. Quantum clocks and the temporal localisability of events in the presence of gravitating quantum systems. Nat. Commun., 11 (1): 1–12, 2020. 10.1038/​s41467-020-16013-1.
https:/​/​doi.org/​10.1038/​s41467-020-16013-1

[37] Flaminia Giacomini and Časlav Brukner. Einstein’s Equivalence principle for superpositions of gravitational fields and quantum reference frames. arXiv:2012.13754, 2020.
arXiv:2012.13754

[38] Philipp A. Höhn and Augustin Vanrietvelde. How to switch between relational quantum clocks. New J. Phys., 22 (12): 123048, 2020. 10.1088/​1367-2630/​abd1ac.
https:/​/​doi.org/​10.1088/​1367-2630/​abd1ac

[39] Philipp A Höhn. Switching internal times and a new perspective on the `wave function of the universe’. Universe, 5 (5): 116, 2019. 10.3390/​universe5050116.
https:/​/​doi.org/​10.3390/​universe5050116

[40] Alexander R. H. Smith and Mehdi Ahmadi. Quantizing time: Interacting clocks and systems. Quantum, 3: 160, 2019. 10.22331/​q-2019-07-08-160.
https:/​/​doi.org/​10.22331/​q-2019-07-08-160

[41] Philipp A. Höhn, Alexander R. H. Smith, and Maximilian P. E. Lock. The Trinity of Relational Quantum Dynamics. arXiv:1912.00033, 2019.
arXiv:1912.00033

[42] Philipp A. Hoehn, Alexander R. H. Smith, and Maximilian P. E. Lock. Equivalence of Approaches to Relational Quantum Dynamics in Relativistic Settings. Front. in Phys., 9: 181, 2021. 10.3389/​fphy.2021.587083.
https:/​/​doi.org/​10.3389/​fphy.2021.587083

[43] Alexander R. H. Smith and Mehdi Ahmadi. Quantum clocks observe classical and quantum time dilation. Nat. Commun., 11 (1): 1–9, 2020. 10.1038/​s41467-020-18264-4.
https:/​/​doi.org/​10.1038/​s41467-020-18264-4

[44] Lucien Hardy. The Construction Interpretation: Conceptual Roads to Quantum Gravity. arXiv:1807.10980, 2020.
arXiv:1807.10980

[45] Magdalena Zych, Fabio Costa, and Timothy C Ralph. Relativity of quantum superpositions. arXiv:1809.04999, 2018.
arXiv:1809.04999

[46] C. J. Isham. Canonical quantum gravity and the problem of time. volume 409, pages 157–287. 1993.

[47] Carlo Rovelli. Quantum Gravity. Cambridge University Press, 2004. 10.1017/​CBO9780511755804.
https:/​/​doi.org/​10.1017/​CBO9780511755804

[48] Karel V Kuchař. Time and interpretations of quantum gravity. Int. J. Mod. Phys. D, 20 (supp01): 3–86, 2011. 10.1142/​S0218271811019347.
https:/​/​doi.org/​10.1142/​S0218271811019347

[49] Carlo Rovelli. Quantum mechanics without time: a model. Phys. Rev. D, 42 (8): 2638, 1990. 10.1103/​PhysRevD.42.2638.
https:/​/​doi.org/​10.1103/​PhysRevD.42.2638

[50] Michael Reisenberger and Carlo Rovelli. Spacetime states and covariant quantum theory. Phys. Rev. D, 65 (12): 125016, 2002. 10.1103/​PhysRevD.65.125016.
https:/​/​doi.org/​10.1103/​PhysRevD.65.125016

[51] Frank Hellmann, Mauricio Mondragon, Alejandro Perez, and Carlo Rovelli. Multiple-event probability in general-relativistic quantum mechanics. Phys. Rev. D, 75 (8): 084033, 2007. 10.1103/​PhysRevD.75.084033.
https:/​/​doi.org/​10.1103/​PhysRevD.75.084033

[52] Magdalena Zych, Łukasz Rudnicki, and Igor Pikovski. Gravitational mass of composite systems. Phys. Rev. D, 99 (10): 104029, 2019. 10.1103/​PhysRevD.99.104029.
https:/​/​doi.org/​10.1103/​PhysRevD.99.104029

[53] Magdalena Zych, Fabio Costa, Igor Pikovski, and Časlav Brukner. Quantum interferometric visibility as a witness of general relativistic proper time. Nat. Commun., 2: 505, 2011. 10.1038/​ncomms1498.
https:/​/​doi.org/​10.1038/​ncomms1498

[54] Igor Pikovski, Magdalena Zych, Fabio Costa, and Časlav Brukner. Time dilation in quantum systems and decoherence. New J. Phys., 19 (2): 025011, 2017. 10.1088/​1367-2630/​aa5d92. URL http:/​/​stacks.iop.org/​1367-2630/​19/​i=2/​a=025011.
https:/​/​doi.org/​10.1088/​1367-2630/​aa5d92
http:/​/​stacks.iop.org/​1367-2630/​19/​i=2/​a=025011

[55] Magdalena Zych, Igor Pikovski, Fabio Costa, and Časlav Brukner. General relativistic effects in quantum interference of “clocks”. In Journal of Physics: Conference Series, volume 723, page 012044. IOP Publishing, 2016. 10.1088/​1742-6596/​723/​1/​012044.
https:/​/​doi.org/​10.1088/​1742-6596/​723/​1/​012044

[56] Igor Pikovski, Magdalena Zych, Fabio Costa, and Časlav Brukner. Universal decoherence due to gravitational time dilation. Nat. Phys., 11 (8): 668, 2015. 10.1038/​nphys3366.
https:/​/​doi.org/​10.1038/​nphys3366

[57] A. Ashtekar. Lectures on nonperturbative canonical gravity, volume 6. 1991. 10.1142/​1321.
https:/​/​doi.org/​10.1142/​1321

[58] Donald Marolf. Refined algebraic quantization: Systems with a single constraint. Banach Center Publications, 39, 09 1995. 10.4064/​-39-1-331-344.
https:/​/​doi.org/​10.4064/​-39-1-331-344

[59] James B. Hartle and Donald Marolf. Comparing formulations of generalized quantum mechanics for reparametrization – invariant systems. Phys.Rev., D56: 6247–6257, 1997. 10.1103/​PhysRevD.56.6247.
https:/​/​doi.org/​10.1103/​PhysRevD.56.6247

[60] Achim Kempf and John R Klauder. On the implementation of constraints through projection operators. J Phys A, 34 (5): 1019, 2001. 10.1088/​0305-4470/​34/​5/​307.
https:/​/​doi.org/​10.1088/​0305-4470/​34/​5/​307

[61] Guglielmo M Tino. Testing gravity with cold atom interferometry: Results and prospects. Quantum Science and Technology, 2020. 10.1088/​2058-9565/​abd83e.
https:/​/​doi.org/​10.1088/​2058-9565/​abd83e

[62] Philippe Allard Guérin and Časlav Brukner. Observer-dependent locality of quantum events. New J. Phys., 20 (10): 103031, 2018. 10.1088/​1367-2630/​aae742. URL http:/​/​stacks.iop.org/​1367-2630/​20/​i=10/​a=103031.
https:/​/​doi.org/​10.1088/​1367-2630/​aae742
http:/​/​stacks.iop.org/​1367-2630/​20/​i=10/​a=103031

[63] Piotr T. Grochowski, Alexander R. H. Smith, Andrzej Dragan, and Kacper Dębski. Quantum time dilation in atomic spectra. Phys. Rev. Research, 3: 023053, Apr 2021. 10.1103/​PhysRevResearch.3.023053. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevResearch.3.023053.
https:/​/​doi.org/​10.1103/​PhysRevResearch.3.023053

[64] GM Tino, L Cacciapuoti, S Capozziello, G Lambiase, and F Sorrentino. Precision gravity tests and the Einstein Equivalence Principle. Prog. Part. Nucl. Phys., page 103772, 2020. 10.1016/​j.ppnp.2020.103772.
https:/​/​doi.org/​10.1016/​j.ppnp.2020.103772

[65] Esteban Castro Ruiz, Flaminia Giacomini, and Časlav Brukner. Entanglement of quantum clocks through gravity. PNAS, 114 (12): E2303–E2309, 2017. ISSN 0027-8424. 10.1073/​pnas.1616427114. URL https:/​/​www.pnas.org/​content/​114/​12/​E2303.
https:/​/​doi.org/​10.1073/​pnas.1616427114
https:/​/​www.pnas.org/​content/​114/​12/​E2303

[66] Flavio Mercati. Shape dynamics: Relativity and relationalism. Oxford University Press, 2018. 10.1093/​oso/​9780198789475.001.0001.
https:/​/​doi.org/​10.1093/​oso/​9780198789475.001.0001

[67] Julian Barbour, Tim Koslowski, and Flavio Mercati. Identification of a gravitational arrow of time. Phys. Rev. Lett., 113 (18): 181101, 2014. 10.1103/​PhysRevLett.113.181101.
https:/​/​doi.org/​10.1103/​PhysRevLett.113.181101

Cited by

[1] Philipp A. Hoehn, Maximilian P. E. Lock, Shadi Ali Ahmad, Alexander R. H. Smith, and Thomas D. Galley, “Quantum Relativity of Subsystems”, arXiv:2103.01232.

[2] Philipp A. Hoehn, Marius Krumm, and Markus P. Mueller, “Internal quantum reference frames for finite Abelian groups”, arXiv:2107.07545.

The above citations are from SAO/NASA ADS (last updated successfully 2021-07-24 01:43:51). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2021-07-24 01:43:49).

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

Source: https://quantum-journal.org/papers/q-2021-07-22-508/

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
Esports5 days ago

NBA 2K22 MyCareer: How to Get a Shoe Deal

Crowdfunding2 days ago

Conister Bank Lends More to Time Finance

Esports4 days ago

How to craft a weapon in Fortnite Chapter 2, season 8

Oceania
Esports5 days ago

lol123 scrape by Rooster to claim final IEM Fall Oceania Closed Qualifier spot

Esports4 days ago

How to complete a Sideways Encounter in Fortnite

Aerospace5 days ago

Potential component defect to delay next Virgin Galactic flight

Esports3 days ago

NBA 2K22 Lightning Green Animation: How to Claim

Esports5 days ago

Na’Vi win ESL Pro League Season 14 in five-map thriller against Vitality to complete $1 million Intel Grand Slam

Ukraine
Esports5 days ago

s1mple claims third consecutive MVP in EPL victory

Esports5 days ago

The best dunkers in NBA 2K22

Aerospace4 days ago

Photos: SpaceX rocket arrives on launch pad for Inspiration4 mission

HRTech4 days ago

Amazon launches educational benefits for frontline staff

Esports5 days ago

AVE and Trasko emerge victorious from CIS IEM Fall open qualifier

Big Data5 days ago

China to break up Ant’s Alipay and force creation of separate loans app – FT

HRTech4 days ago

How Crompton is using the ‘Power of Language’ to create a high-engagement culture

Esports4 days ago

Imperial round out IEM Fall SA closed qualifier team list

Cleantech5 days ago

Bringing Solar & Tesla Batteries To Restaurants In New Orleans To “Stay Lit,” And How You Can Help

HRTech4 days ago

Competing with Self

Esports4 days ago

All Maps in Battlefield 2042

Cleantech4 days ago

Is A Tesla Model S Plaid Fully Submersible? (VIDEO)

Trending

Copyright © 2020 Plato Technologies Inc.