The DOI matches its Crossref record; 61 of the 61 references it cites were found in a registry or an index.
Unconditionally verifiable blind quantum computation
Open accessAbstract
Blind quantum computing (BQC) allows a client to have a server carry out a quantum computation for them such that the client's input, output, and computation remain private. A desirable property for any BQC protocol is verification, whereby the client can verify with high probability whether the server has followed the instructions of the protocol or if there has been some deviation resulting in a corrupted output state. A verifiable BQC protocol can be viewed as an interactive proof system leading to consequences for complexity theory. We previously proposed [A. Broadbent, J. Fitzsimons, and E. Kashefi, in Proceedings of the 50th Annual Symposium on Foundations of Computer Science, Atlanta, 2009 (IEEE, Piscataway, 2009), p. 517] a universal and unconditionally secure BQC scheme where the client only needs to be able to prepare single qubits in separable states randomly chosen from a finite set and send them to the server, who has the balance of the required quantum computational resources. In this paper we extend that protocol with additional functionality allowing blind computational basis measurements, which we use to construct another verifiable BQC protocol based on a different class of resource states. We rigorously prove that the probability of failing to detect an incorrect output is exponentially small in a security parameter, while resource overhead remains polynomial in this parameter. This resource state allows entangling gates to be performed between arbitrary pairs of logical qubits with only constant overhead. This is a significant improvement on the original scheme, which required that all computations to be performed must first be put into a nearest-neighbor form, incurring linear overhead in the number of qubits. Such an improvement has important consequences for efficiency and fault-tolerance thresholds.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1983) · Communications of the ACM · doi:10.1145/357980.358017 · Cited by 13,012
Fully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806
Raussendorf, R., & Briegel, H. J. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.5188 · Cited by 4,477
Georgescu, I. M., Ashhab, S., & Nori, F. (2014) · Reviews of Modern Physics · doi:10.1103/revmodphys.86.153 · Cited by 2,932
(1978) · Cited by 1,875
Efficient Fully Homomorphic Encryption from (Standard) LWE
Brakerski, Z., & Vaikuntanathan, V. (2011) · 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.12 · Cited by 1,449
Multiparty entanglement in graph states
Hein, M., Eisert, J., & Briegel, H. J. (2004) · Physical Review A · doi:10.1103/physreva.69.062311 · Cited by 915
The computational complexity of linear optics
Aaronson, S., & Arkhipov, A. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993682 · Cited by 874
Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes
Smart, N. P., & Vercauteren, F. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13013-7_25 · Cited by 808
Topological fault-tolerance in cluster state quantum computation
Raussendorf, R., Harrington, J., & Goyal, K. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/199 · Cited by 617
Advances in Cryptology: Proceedings of Crypto 84
Blakley, G. R., & Chaum, D. (1985) · Medical Entomology and Zoology · Cited by 516
Demonstration of Blind Quantum Computing
Barz, S., Kashefi, E., Broadbent, A., Fitzsimons, J. F., Zeilinger, A., & Walther, P. (2012) · Science · doi:10.1126/science.1214707 · Cited by 475
Self-citationGraph states for quantum secret sharing
Markham, D., & Sanders, B. C. (2008) · Physical Review A · doi:10.1103/physreva.78.042309 · Cited by 451
A fault-tolerant one-way quantum computer
Raussendorf, R., Harrington, J., & Goyal, K. (2006) · Annals of Physics · doi:10.1016/j.aop.2006.01.012 · Cited by 397
Optimal encryption of quantum bits
Boykin, P. O., & Roychowdhury, V. (2003) · Physical Review A · doi:10.1103/physreva.67.042317 · Cited by 337
Classical command of quantum systems
Reichardt, B. W., Unger, F., & Vazirani, U. (2013) · Nature · doi:10.1038/nature12035 · Cited by 294
Authentication of quantum messages
Barnum, H., Crepeau, C., Gottesman, D., Smith, A., & Tapp, A. (2003) · The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. · doi:10.1109/sfcs.2002.1181969 · Cited by 272
Secure assisted quantum computation
Childs, A. M. (2005) · Quantum Information and Computation · doi:10.26421/qic5.6-4 · Cited by 264
Interactive Proofs For Quantum ComputationsPreprint
Aharonov, D., Ben-Or, M., Eban, E., & Mahadev, U. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0810.5375 · Cited by 242
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Bremner, M. J., Jozsa, R., Shepherd, D. J., et al. (2010) · Cited by 216
Ambainis, A., Mosca, M., Tapp, A., & De Wolf, R. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892142 · Cited by 214
On hiding information from an oracle
Abadi, M., Feigenbaum, J., & Kilian, J. (1989) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(89)90018-4 · Cited by 200
Danos, V., Kashefi, E., & Panangaden, P. (2007) · Journal of the ACM · doi:10.1145/1219092.1219096 · Cited by 195
Self-citationBlind quantum computation protocol in which Alice only makes measurements
Morimae, T., & Fujii, K. (2013) · Physical Review A · doi:10.1103/physreva.87.050301 · Cited by 185
Computational Power of Correlations
Anders, J., & Browne, D. E. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.050502 · Cited by 184
Determinism in the one-way model
Danos, V., & Kashefi, E. (2006) · Physical Review A · doi:10.1103/physreva.74.052310 · Cited by 176
Self-citationParallelizing quantum circuits
Broadbent, A., & Kashefi, E. (2009) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.12.046 · Cited by 167
Self-citationQuantum computing on encrypted data
Fisher, K. A. G., Broadbent, A., Shalm, L. K., Yan, Z., Lavoie, J., Prevedel, R., Jennewein, T., & Resch, K. J. (2014) · Nature Communications · doi:10.1038/ncomms4074 · Cited by 157
Experimental verification of quantum computation
Barz, S., Fitzsimons, J. F., Kashefi, E., & Walther, P. J. (2013) · Nature Physics · doi:10.1038/nphys2763 · Cited by 150
Self-citationUnified derivations of measurement-based schemes for quantum computation
Childs, A. M., Leung, D., & Nielsen, M. A. (2005) · Physical Review A · doi:10.1103/physreva.71.032318 · Cited by 149
A polynomial quantum algorithm for approximating the Jones polynomial
Aharonov, D., Jones, V. F. R., & Landau, Z. A. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132579 · Cited by 147
Robustness and device independence of verifiable blind quantum computing
Gheorghiu, A., Kashefi, E., & Wallden, P. (2015) · New Journal of Physics · doi:10.1088/1367-2630/17/8/083040 · Cited by 132
Self-citationBroadbent, A., Gutoski, G., & Stebila, D. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40084-1_20 · Cited by 126
Generalized flow and determinism in measurement-based quantum computation
Browne, D. E., Kashefi, E., Mhalla, M., & Perdrix, S. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/8/250 · Cited by 126
Self-citationBlind topological measurement-based quantum computation
Morimae, T., & Fujii, K. (2012) · Nature Communications · doi:10.1038/ncomms2043 · Cited by 126
Secure assisted quantum computation
Childs, A. M. (2005) · CERN Document Server (European Organization for Nuclear Research) · doi:10.5555/2011670.2011674 · Cited by 123
Efficient Universal Blind Quantum Computation
Giovannetti, V., Maccone, L., Morimae, T., & Rudolph, T. (2013) · Physical Review Letters · doi:10.1103/physrevlett.111.230501 · Cited by 118
ARRIGHI, P., & SALVAIL, L. (2006) · International Journal of Quantum Information · doi:10.1142/s0219749906002171 · Cited by 118
Optimal Blind Quantum Computation
Mantri, A., Pérez-Delgado, C. A., & Fitzsimons, J. F. (2013) · Physical Review Letters · doi:10.1103/physrevlett.111.230502 · Cited by 116
Self-citationBlind Quantum Computing with Weak Coherent Pulses
Dunjko, V., Kashefi, E., & Leverrier, A. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.200502 · Cited by 111
Self-citationComposable Security of Delegated Quantum Computation
Dunjko, V., Fitzsimons, J. F., Portmann, C., & Renner, R. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-45608-8_22 · Cited by 99
Self-citationFundamentals of universality in one-way quantum computation
Nest, M. V. D., Dür, W., Miyake, A., & Briegel, H. J. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/204 · Cited by 97
Quantum Walks with Encrypted Data
Rohde, P. P., Fitzsimons, J. F., & Gilchrist, A. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.150501 · Cited by 92
Self-citationA quantum approach to homomorphic encryption
Tan, S.-H., Kettlewell, J. A., Ouyang, Y., Chen, L., & Fitzsimons, J. F. (2016) · Scientific Reports · doi:10.1038/srep33467 · Cited by 89
Self-citationDevice-Independent Verifiable Blind Quantum ComputationPreprint
Hajdušek, M., Pérez-Delgado, C. A., & Fitzsimons, J. F. (2015) · Kent Academic Repository (University of Kent) · doi:10.48550/arxiv.1502.02563 · Cited by 83
Self-citationTriple-server blind quantum computation using entanglement swapping
Li, Q., Chan, W. H., Wu, C., & Wen, Z. (2014) · Physical Review A · doi:10.1103/physreva.89.040302 · Cited by 83
Ancilla-driven universal blind quantum computation
Sueki, T., Koshiba, T., & Morimae, T. (2013) · Physical Review A · doi:10.1103/physreva.87.060301 · Cited by 79
Limitations on information-theoretically-secure quantum homomorphic encryption
Yu, L. Z., Pérez-Delgado, C. A., & Fitzsimons, J. F. (2014) · Physical Review A · doi:10.1103/physreva.90.050303 · Cited by 77
Self-citationQuantum homomorphic encryption from quantum codes
Ouyang, Y., Tan, S.-H., & Fitzsimons, J. F. (2018) · Physical Review A · doi:10.1103/physreva.98.042334 · Cited by 74
Self-citationContinuous-Variable Blind Quantum Computation
Morimae, T. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.230502 · Cited by 70
Computational Depth Complexity of Measurement-Based Quantum Computation
Browne, D. E., Kashefi, E., & Perdrix, S. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-18073-6_4 · Cited by 62
Self-citationRobustness and device independence of verifiable blind quantum computing
Gheorghiu, A., Kashefi, E., & Wallden, P. (2015) · HAL · Cited by 58
Self-citationA quantum approach to homomorphic encryption
Tan, S. H., Kettlewell, J. A., Ouyang, Y., Chen, L., & Fitzsimons, J. F. (2016) · White Rose Research Online (University of Leeds, The University of Sheffield, University of York) · Cited by 57
Self-citationParsimonious and robust realizations of unitary maps in the one-way model
Danos, V., Kashefi, E., & Panangaden, P. (2005) · Physical Review A · doi:10.1103/physreva.72.064301 · Cited by 55
Self-citationMosca, M., & Stebila, D. (2010) · Contemporary mathematics - American Mathematical Society · doi:10.1090/conm/523/10311 · Cited by 54
Ground state blind quantum computation on AKLT state
Morimae, T., Dunjko, V., & Kashefi, E. (2015) · Quantum Information and Computation · doi:10.26421/qic15.3-4-2 · Cited by 50
Self-citationIterated Gate Teleportation and Blind Quantum Computation
Pérez-Delgado, C. A., & Fitzsimons, J. F. (2015) · Physical Review Letters · doi:10.1103/physrevlett.114.220502 · Cited by 47
Self-citationFault-Tolerant Operations for Universal Blind Quantum Computation
Chien, C.-H., Meter, R. V., & Kuo, S. (2015) · ACM Journal on Emerging Technologies in Computing Systems · doi:10.1145/2700248 · Cited by 36
How to Compute on Encrypted Data
Vaikuntanathan, V. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-34931-7_1 · Cited by 10
QMIP = MIP*Preprint
Broadbent, A., Fitzsimons, J. F., & Kashefi, E. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1004.1130 · Cited by 4
Self-citation
Cited by
Advances in quantum cryptography
Pirandola, S., Andersen, U. L., Banchi, L., Berta, M., Bunandar, D., Colbeck, R., Englund, D., Gehring, T., Lupo, C., Ottaviani, C., et al. (2020) · Advances in Optics and Photonics · doi:10.1364/aop.361502 · Cited by 2,033
Photonic quantum information processing: a review
Flamini, F., Spagnolo, N., & Sciarrino, F. (2019) · Reports on Progress in Physics · doi:10.1088/1361-6633/aad5b2 · Cited by 770
Security in quantum cryptography
Portmann, C., & Renner, R. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.025008 · Cited by 390
Quantum simulation and computing with Rydberg-interacting qubits
Morgado, M., & Whitlock, S. (2021) · AVS Quantum Science · doi:10.1116/5.0036562 · Cited by 370
Quantum certification and benchmarking
Eisert, J., Hangleiter, D., Walk, N., Roth, I., Markham, D., Parekh, R., Chabaud, U., & Kashefi, E. (2020) · Nature Reviews Physics · doi:10.1038/s42254-020-0186-4 · Cited by 342
Self-citation
Metadata
- Authors
- Fitzsimons, J. F., & Kashefi, E.
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2017-07-05
- Volume
- 96
- Issue
- 1
- ISSN
- 0556-2791 (ISSN-L)
- 2469-9926
- 2469-9934
- OpenAlex
- W58322429
- Cited by
- 277
- References
- 61
- FWCI
- 13.78
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.