Fetching the paper…

Reading the bibliography…

2018

Sample complexity of device-independently certified "quantum supremacy"

Hangleiter, Dominik, Kliesch, Martin, Eisert, Jens et al.

Original
PDF
Post on X

Understand

Results on the hardness of approximate sampling are seen as important stepping stones towards a convincing demonstration of the superior computational power of quantum devices.

The most prominent suggestions for such experiments include boson sampling, IQP circuit sampling, and universal random circuit sampling.
A key challenge for any such demonstration is to certify the correct implementation.
For all these examples, and in fact for all sufficiently flat distributions, we show that any non-interactive certification from classical samples and a description of the target distribution requires exponentially many uses of the device.

Sample complexity of device-independently certified "quantum supremacy" · Around

Built on

A. W. Harrow and R. A. Low, Random quantum circuits are approximate 2-designs , Commun. Math. Phys. 291
Original
1919
Earlier work this paper cites.
L. Valiant, The complexity of computing the permanent , Theoretical Computer Science 8
1979
Earlier work this paper cites.
L. Stockmeyer, On approximation algorithms for # \# P , SIAM J. Comput. 14
1985
Earlier work this paper cites.
R. Lipton, New directions in testing , in Distributed Computing and Cryprography , Vol. 2 (AMS, 1991) pp. 191–202
1991
Earlier work this paper cites.
B. M. Terhal and D. P. DiVincenzo, Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games , Quant. Inf. Comp. 4
2004
Earlier work this paper cites.
N. Ermolova and S. G. Haggman, Simplified bounds for the complementary error function; application to the performance evaluation of signal-processing systems , in 2004 12th European Signal Processing Conference (2004) pp. 1087–1090
2004
Earlier work this paper cites.
T. Jiang, How many entries of a typical orthogonal matrix can be approximated by independent normals? Ann. Probab. 34
2006
Earlier work this paper cites.
D. Shepherd and M. J. Bremner, Temporally unstructured quantum computation , Proc. Roy. Soc. A 465
Original
2009
Earlier work this paper cites.
L. Trevisan, M. Tulsiani, and S. Vadhan, Regularity, boosting, and efficiently simulating every high-entropy distribution , in 2009 24th Annual IEEE Conference on Computational Complexity (2009) pp. 126–136
2009
Earlier work this paper cites.
G. Valiant and P. Valiant, A CLT and tight lower bounds for estimating entropy , Tech. Rep. 10-179 (2010) eCCC
2010
Earlier work this paper cites.
J. Preskill, Quantum computing and the entanglement frontier , Bull. Am. Phys. Soc. 58
Original
2013
Earlier work this paper cites.
J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X.-M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, Boson sampling on a photonic chip , Science 339
2013
Earlier work this paper cites.
M. Tillmann, B. Dakić, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, Experimental boson sampling , Nature Photonics 7
2013
Earlier work this paper cites.
M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White, Photonic boson sampling in a tunable circuit , Science 339
2013
Earlier work this paper cites.
A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvão, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, Integrated multimode interferometers with arbitrary designs for photonic boson sampling , Nature Photonics 7
2013
Earlier work this paper cites.
S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing , Applied and Numerical Harmonic Analysis (Springer New York, New York, NY, 2013)
2013
Earlier work this paper cites.

Similar

J. Carolan, J. D. A. Meinecke, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, On the experimental verification of quantum complexity in linear optics , Nature Photonics 8
Original
2014
Cited alongside, same era.
N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvão, and F. Sciarrino, Experimental validation of photonic boson sampling , Nature Photonics 8
Original
2014
Cited alongside, same era.
Y. Nakata, M. Koashi, and M. Murao, Generating a state t t -design by diagonal quantum circuits , New J. Phys. 16
Original
2014
Cited alongside, same era.
N. Wiebe, C. Granade, C. Ferrie, and D. G. Cory, Hamiltonian learning and certification using quantum resources , Phys. Rev. Lett. 112
Original
2014
Cited alongside, same era.

Then

O. Goldreich, Introduction to Property Testing (Cambridge University Press, Cambridge, 2017)
2017
Later among the works it cites.
J. Miller, S. Sanders, and A. Miyake, Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification , Phys. Rev. A 96
Original
2017
Later among the works it cites.
G. Valiant and P. Valiant, An automatic inequality prover and instance optimal identity testing , SIAM J. Comput. 46
2017
Later among the works it cites.
S. Aaronson and L. Chen, Complexity-Theoretic Foundations of Quantum Supremacy Experiments , in 32nd Computational Complexity Conference (CCC 2017) , Leibniz International Proceedings in Informatics (LIPIcs), Vol. 79, edited by R. O’Donnell (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017) pp. 22:1–22:67, arXiv:1612.05903
Original
2017
Later among the works it cites.
T. Morimae, Hardness of classically sampling the one-clean-qubit model with constant total variation distance error , Phys. Rev. A 96

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

L. Aolita, C. Gogolin, M. Kliesch, and J. Eisert, Reliable quantum certification of photonic state preparations , Nature Communications 6

Original

2015

Cited alongside, same era.

B. Fefferman and C. Umans, The Power of Quantum Fourier Sampling , (2015), arXiv:1507.05592 [quant-ph]

2015

Cited alongside, same era.

M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average-case complexity versus approximate simulation of commuting quantum computations , Phys. Rev. Lett. 117

2016

Cited alongside, same era.

M. Walschaers, J. Kuipers, J.-D. Urbina, K. Mayer, M. C. Tichy, K. Richter, and A. Buchleitner, Statistical benchmark for BosonSampling , New J. Phys. 18

2016

Cited alongside, same era.

S.-T. Wang and L.-M. Duan, Certification of Boson Sampling Devices with Coarse-Grained Measurements , (2016) , arXiv:1601.02627

2016

Cited alongside, same era.

F. G. S. L. Brandão, A. W. Harrow, and M. Horodecki, Local random quantum circuits are approximate polynomial-designs , Commun. Math. Phys. 346

2016

Cited alongside, same era.

A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Birchall, A. Montanaro, and A. Laing, Classical boson sampling algorithms with superior performance to near-term experiments , Nature Physics 13

2017

Cited alongside, same era.

M. J. Bremner, A. Montanaro, and D. J. Shepherd, Achieving quantum supremacy with sparse and noisy commuting quantum computations , Quantum 1

2017

Cited alongside, same era.

2017

Later among the works it cites.

P. Clifford and R. Clifford, The Classical Complexity of Boson Sampling , in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18 , SODA ’18 (Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2018) pp. 146–155, arXiv:1706.01260

2018

Closest in time.

M. Oszmaniec and D. J. Brod, Classical simulation of photonic linear optics with lost particles , New J. Phys. 20

2018

Closest in time.

J. Renema, V. Shchesnovich, and R. Garcia-Patron, Quantum-to-classical transition in many-body bosonic interference , (2018), arXiv:1809.01953

2018

Closest in time.

S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Characterizing quantum supremacy in near-term devices , Nature Physics 14

2018

Closest in time.

J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert, Architectures for quantum simulation showing a quantum speedup , Phys. Rev. X 8

2018

Closest in time.

D. Hangleiter, J. Bermejo-Vega, M. Schwarz, and J. Eisert, Anticoncentration theorems for schemes showing a quantum speedup , Quantum 2

2018

Closest in time.

A. Bouland, J. F. Fitzsimons, and D. E. Koh, Complexity classification of conjugated Clifford circuits , in 33rd Computational Complexity Conference (CCC 2018) , Leibniz International Proceedings in Informatics (LIPIcs), Vol. 102, edited by R. A. Servedio (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018) pp. 21:1–21:25, arXiv:1709.01805

2018

Closest in time.

D. Mills, A. Pappa, T. Kapourniotis, and E. Kashefi, Information theoretically secure hypothesis test for temporally unstructured quantum computation (extended abstract) , Electron. Proc. Theor. Comput. Sci. 266

2018

Closest in time.

Y. Takeuchi and T. Morimae, Verification of Many-Qubit States , Phys. Rev. X 8

2018

Closest in time.

A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, On the complexity and verification of quantum random circuit sampling , Nature Physics 15

2019

Closest in time.