Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
On ELFs, Deterministic Encryption, and Correlated-Input Security Read chapter Read first chapter

2019 | OriginalPaper | Chapter

Verifier-on-a-Leash: New Schemes for Verifiable Delegated Quantum Computation, with Quasilinear Resources

Authors : Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery, Thomas Vidick

Published in: Advances in Cryptology – EUROCRYPT 2019

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The problem of reliably certifying the outcome of a computation performed by a quantum device is rapidly gaining relevance. We present two protocols for a classical verifier to verifiably delegate a quantum computation to two non-communicating but entangled quantum provers. Our protocols have near-optimal complexity in terms of the total resources employed by the verifier and the honest provers, with the total number of operations of each party, including the number of entangled pairs of qubits required of the honest provers, scaling as \(O(g\log g)\) for delegating a circuit of size g. This is in contrast to previous protocols, whose overhead in terms of resources employed, while polynomial, is far beyond what is feasible in practice. Our first protocol requires a number of rounds that is linear in the depth of the circuit being delegated, and is blind, meaning neither prover can learn the circuit or its input. The second protocol is not blind, but requires only a constant number of rounds of interaction.
Our main technical innovation is an efficient rigidity theorem which allows a verifier to test that two entangled provers perform measurements specified by an arbitrary m-qubit tensor product of single-qubit Clifford observables on their respective halves of m shared EPR pairs, with a robustness that is independent of m. Our two-prover classical-verifier delegation protocols are obtained by combining this rigidity theorem with a single-prover quantum-verifier protocol for the verifiable delegation of a quantum computation, introduced by Broadbent.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter On Quantum Advantage in Information Theoretic Single-Server PIR
next chapter Ring Signatures: Logarithmic-Size, No Setup—from Standard Assumptions
Footnotes
1
Using results of Ji [Ji16], this allows the protocol to be single-round. Alternatively, the state can be created by a single prover and teleported to the others with the help of the verifier, resulting in a two-round protocol.
 
2
Blindness is a property of delegation protocols, which informally states that the prover learns nothing about the verifier’s private circuit.
 
3
The \(\log g\) overhead is due to the complexity of sampling from the right distribution in rigidity tests. We leave the possibility of removing this by derandomization for future work. Another source of overhead is in achieving blindness: in order to hide the circuit, we encode it as part of the input to a universal circuit, introducing a factor of \(O(\log g)\) overhead.
 
4
Here, we consider the decomposition of the attack as a sum of tensors of Pauli \(A = \sum _k \sum _{Q \in \{I,X,Z,Y\}} \alpha _{k,Q} Q\).
 
5
We make the assumption that the players employ a pure-state strategy for convenience, but it is easy to check that all proofs extend to the case of a mixed strategy. Moreover, it is always possible to consider (as we do) projective strategies only by applying Naimark’s dilation theorem, and adding an auxiliary local system to each player as necessary, since no bound is assumed on the dimension of their systems.
 
6
See [RUV12, Appendix A] for an extended discussion of this issue, with a similar resolution to ours.
 
7
One must ensure that a prover does not realize if the alternative protocol is executed instead of the original; this is easily enforced by only interacting with any of the provers at specific, publicly decided times.
 
Literature
[ABE10]
Aharonov, D., Ben-Or, M., Eban, E.: Interactive proofs for quantum computations. In: Proceedings of the First Symposium on Innovations in Computer Science (ICS 2010), pp. 453–469 (2010)
[ADSS17]
Alagic, G., Dulek, Y., Schaffner, C., Speelman, F.: Quantum fully homomorphic encryption with verification (2017). arXiv preprint arXiv:​1708.​09156
[Bel64]
[BFGH10]
Bera, D., Fenner, S.A., Green, F., Homer, S.: Efficient universal quantum circuits. Quantum Inf. Comput. 10(1&2), 16–27 (2010)MathSciNetMATH
[Bro18]
[BvCA18]
Bowles, J., Šupić, I., Cavalcanti, D., Acín, A.: Self-testing of Pauli observables for device-independent entanglement certification (2018). arXiv:​1801.​10446
[Cas17]
Castelvecchi, D.: IBM’s quantum cloud computer goes commercial. Nat. News 543(7644) (2017)CrossRef
[CHSH69]
Clauser, J.F., Horne, M.A., Shimony, A., Holt, R.A.: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23, 880–884 (1969)CrossRef
[DSS16]
[FH15]
[FH17]
Fujii, K., Hayashi, M.: Verifiable fault tolerance in measurement-based quantum computation. Phys. Rev. A 96, 030301 (2017)CrossRef
[Fit16]
Fitzsimons, J.F.: Private quantum computation: an introduction to blind quantum computing and related protocols (2016). arXiv preprint arXiv:​1611.​10107
[FK17]
Fitzsimons, J.F., Kashefi, E.: Unconditionally verifiable blind quantum computation. Phys. Rev. A 96(012303) (2017). arXiv preprint arXiv:​1203.​5217
[GKW15]
Gheorghiu, A., Kashefi, E., Wallden, P.: Robustness and device independence of verifiable blind quantum computing. New J. Phys. 17 (2015)CrossRef
[Gri17]
[HH16]
[HM15]
Hayashi, M., Morimae, T.: Verifiable measurement-only blind quantum computing with stabilizer testing. Phys. Rev. Lett. 115, 220502 (2015)CrossRef
[HPDF15]
Hajdušek, M., Pérez-Delgado, C.A., Fitzsimons, J.F.: Device-independent verifiable blind quantum computation (2015). arXiv preprint arXiv:​1502.​02563
[HZM+17]
Huang, H.-L., et al.: Experimental blind quantum computing for a classical client. Phys. Rev. Lett. 119, 050503 (2017)CrossRef
[Ji16]
Ji, Z.: Classical verification of quantum proofs. In: Proceedings of the Forty-eighth Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), pp. 885–898 (2016)
[Mah17]
[Mah18]
[McK16]
McKague, M.: Interactive proofs for BQP via self-tested graph states. Theory Comput. 12(3), 1–42 (2016). arXiv preprint arXiv:​1309.​5675
[MF16]
[Mon16]
Montanaro, A.: Quantum algorithms: an overview. npj Quantum Inf. 2(15023) (2016)
[Mor14]
Morimae, T.: Verification for measurement-only blind quantum computing. Phys. Rev. A 89 (2014)
[MTH17]
[MY04]
[NV17]
Natarajan, A., Vidick, T.: A quantum linearity test for robustly verifying entanglement. In: Proceedings of the Forty-Ninth Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pp. 1003–1015 (2017)
[RUV12]
Reichardt, B.W., Unger, F., Vazirani, U.: A classical leash for a quantum system: command of quantum systems via rigidity of CHSH games (2012). arXiv preprint arXiv:​1209.​0448
[RUV13]
[Slo16]
Slofstra, W.: Tsirelson’s problem and an embedding theorem for groups arising from non-local games (2016). arXiv preprint arXiv:​1606.​03140
Metadata
Title
Verifier-on-a-Leash: New Schemes for Verifiable Delegated Quantum Computation, with Quasilinear Resources
Authors
Andrea Coladangelo
Alex B. Grilo
Stacey Jeffery
Thomas Vidick
Copyright Year
2019
Book
Advances in Cryptology – EUROCRYPT 2019

Print ISBN: 978-3-030-17658-7

Electronic ISBN: 978-3-030-17659-4

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-17659-4_9

Premium Partner

    Image Credits