The DOI matches its Crossref record; 155 of the 155 references it cites were found in a registry or an index.
Nonlocality and communication complexity
Open accessAbstract
Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles such as the superposition principle, entanglement, and interference. Until recently the common notion of computing was based on classical mechanics and did not take into account all the possibilities that physically realizable computing devices offer in principle. The field gained momentum after Shor developed an efficient algorithm for factoring numbers, demonstrating the potential computing powers that quantum computing devices can unleash. In this review the information counterpart of computing is studied. It was realized early on by Holevo that quantum bits, the quantum mechanical counterpart of classical bits, cannot be used for efficient transformation of information in the sense that arbitrary $k$-bit messages cannot be compressed into messages of $k\ensuremath{-}1$ qubits. The abstract form of the distributed computing setting is called communication complexity. It studies the amount of information, in terms of bits or in our case qubits, that two spatially separated computing devices need to exchange in order to perform some computational task. Surprisingly, quantum mechanics can be used to obtain dramatic advantages for such tasks. The area of quantum communication complexity is reviewed and it is shown how it connects the foundational physics questions regarding nonlocality with those of communication complexity studied in theoretical computer science. The first examples exhibiting the advantage of the use of qubits in distributed information-processing tasks were based on nonlocality tests. However, by now the field has produced strong and interesting quantum protocols and algorithms of its own that demonstrate that entanglement, although it cannot be used to replace communication, can be used to reduce the communication exponentially. In turn, these new advances yield a new outlook on the foundations of physics and could even yield new proposals for experiments that test the foundations of physics.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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 Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb01338.x · Cited by 88,486
A Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb00917.x · Cited by 48,949
Quantum Computation and Quantum Information
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
Quantum computation and quantum information
Law, J. (2001) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/505482.505499 · Cited by 18,842
Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
Einstein, A., Podolsky, B., & Rosen, N. (1935) · Physical Review · doi:10.1103/physrev.47.777 · Cited by 16,654
Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
Bennett, C. H., Brassard, G., Crépeau, C., Jozsa, R., Peres, A., & Wootters, W. K. (1993) · Physical Review Letters · doi:10.1103/physrevlett.70.1895 · Cited by 13,703
On the Einstein Podolsky Rosen paradox
Bell, J. S. (1964) · Physics Physique Fizika · doi:10.1103/physicsphysiquefizika.1.195 · Cited by 12,252
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Quantum cryptography: Public key distribution and coin tossing
Bennett, C. H., & Brassard, G. (2014) · Theoretical Computer Science · doi:10.1016/j.tcs.2014.05.025 · Cited by 8,299
Quantum cryptography: Public key distribution and coin tossing
Bennett, C. H., & Brassard, G. (2020) · arXiv · doi:10.48550/arxiv.2003.06557 · Cited by 8,299
Proposed Experiment to Test Local Hidden-Variable Theories
Clauser, J. F., Horne, M. A., Shimony, A., & Holt, R. A. (1969) · Physical Review Letters · doi:10.1103/physrevlett.23.880 · Cited by 7,573
Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
Bennett, C. H., & Wiesner, S. J. (1992) · Physical Review Letters · doi:10.1103/physrevlett.69.2881 · Cited by 5,470
Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model
Werner, R. F. (1989) · Physical Review A · doi:10.1103/physreva.40.4277 · Cited by 4,062
Experimental Test of Bell's Inequalities Using Time- Varying Analyzers
Aspect, A., Dalibard, J., & Roger, G. (1982) · Physical Review Letters · doi:10.1103/physrevlett.49.1804 · Cited by 3,942
Quantum information and computation
Bennett, C. H., & DiVincenzo, D. P. (2000) · Nature · doi:10.1038/35005001 · Cited by 3,263
Discussion of Probability Relations between Separated Systems
Schrödinger, E. (1935) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100013554 · Cited by 3,124
Concentrating partial entanglement by local operations
Bennett, C. H., Bernstein, H. J., Popescu, S., & Schumacher, B. (1996) · Physical Review A · doi:10.1103/physreva.53.2046 · Cited by 3,111
Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels
Bennett, C. H., Brassard, G., Popescu, S., Schumacher, B., Smolin, J. A., & Wootters, W. K. (1996) · Physical Review Letters · doi:10.1103/physrevlett.76.722 · Cited by 2,961
Bhatia, R. (1996) · Cited by 2,847
Rapid solution of problems by quantum computation
Deutsch, D., & Jozsa, R. (1992) · Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences · doi:10.1098/rspa.1992.0167 · Cited by 2,700
Aspect, A., Grangier, P., & Roger, G. (1982) · Physical Review Letters · doi:10.1103/physrevlett.49.91 · Cited by 2,687
Bhatia, R. (1997) · Graduate Texts in Mathematics · doi:10.1007/978-1-4612-0653-8 · Cited by 2,336
Experimental Tests of Realistic Local Theories via Bell's Theorem
Aspect, A., Grangier, P., & Roger, G. (1981) · Physical Review Letters · doi:10.1103/physrevlett.47.460 · Cited by 2,251
Gisin, N., & Thew, R. (2007) · Nature Photonics · doi:10.1038/nphoton.2007.22 · Cited by 2,147
Experimental Test of Local Hidden-Variable Theories
Freedman, S. J., & Clauser, J. F. (1972) · Physical Review Letters · doi:10.1103/physrevlett.28.938 · Cited by 1,999
Quantum generalizations of Bell's inequality
Cirel'son, B. S. (1980) · Letters in Mathematical Physics · doi:10.1007/bf00417500 · Cited by 1,788
Quantum amplitude amplification and estimation
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002) · Contemporary Mathematics · doi:10.1090/conm/305/05215 · Cited by 1,680
Violation of Bell's Inequality under Strict Einstein Locality Conditions
Weihs, G., Jennewein, T., Simon, C., Weinfurter, H., & Zeilinger, A. (1998) · Physical Review Letters · doi:10.1103/physrevlett.81.5039 · Cited by 1,643
Bell’s Theorem, Quantum Theory and Conceptions of the Universe
(1989) · doi:10.1007/978-94-017-0849-4 · Cited by 1,632
(2005) · Complexity Theory · doi:10.1007/3-540-27477-4_15 · Cited by 1,629
Quantum nonlocality as an axiom
Popescu, S., & Rohrlich, D. (1994) · Foundations of Physics · doi:10.1007/bf02058098 · Cited by 1,562
Device-independent security of quantum cryptography against collective attacks
Acín, A., Brunner, N., Gisin, N., Massar, S., Pironio, S., & Scarani, V. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.230501 · Cited by 1,537
Self-citationGreenberger, D. M., Horne, M. A., & Zeilinger, A. (1989) · Bell’s Theorem, Quantum Theory and Conceptions of the Universe · doi:10.1007/978-94-017-0849-4_10 · Cited by 1,513
Experimental entanglement of four particles
Sackett, C. A., Kielpinski, D., King, B. E., Langer, C., Meyer, V., Myatt, C. J., Rowe, M., Turchette, Q. A., Itano, W. M., Wineland, D. J., et al. (2000) · Nature · doi:10.1038/35005011 · Cited by 1,436
Experimental test of quantum nonlocality in three-photon Greenberger–Horne–Zeilinger entanglement
Pan, J.-W., Bouwmeester, D., Daniell, M., Weinfurter, H., & Zeilinger, A. (2000) · Nature · doi:10.1038/35000514 · Cited by 1,209
Buhrman, H., Cleve, R., Watrous, J., & de Wolf, R. (2001) · Physical Review Letters · doi:10.1103/physrevlett.87.167902 · Cited by 1,190
Self-citationSchumacher, B. (1995) · Physical Review A · doi:10.1103/physreva.51.2738 · Cited by 1,090
Hidden variables and the two theorems of John Bell
Mermin, N. D. (1993) · Reviews of Modern Physics · doi:10.1103/revmodphys.65.803 · Cited by 1,078
Experimental violation of a Bell's inequality with efficient detection
Rowe, M. A., Kielpinski, D., Meyer, V., Sackett, C. A., Itano, W. M., Monroe, C., & Wineland, D. J. (2001) · Nature · doi:10.1038/35057215 · Cited by 1,043
Some complexity questions related to distributive computing(Preliminary Report)
Yao, A. C.-C. (1979) · Proceedings of the eleventh annual ACM symposium on Theory of computing - STOC '79 · doi:10.1145/800135.804414 · Cited by 1,042
Bell Inequalities for Arbitrarily High-Dimensional Systems
Collins, D., Gisin, N., Linden, N., Massar, S., & Popescu, S. (2002) · Physical Review Letters · doi:10.1103/physrevlett.88.040404 · Cited by 981
Self-citationProbability relations between separated systems
Schrödinger, E. (1936) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100019137 · Cited by 979
Violation of Bell Inequalities by Photons More Than 10 km Apart
Tittel, W., Brendel, J., Zbinden, H., & Gisin, N. (1998) · Physical Review Letters · doi:10.1103/physrevlett.81.3563 · Cited by 963
No Signaling and Quantum Key Distribution
Barrett, J., Hardy, L., & Kent, A. (2005) · Physical Review Letters · doi:10.1103/physrevlett.95.010503 · Cited by 918
(1960) · The Computer Journal · doi:10.1093/comjnl/3.2.75 · Cited by 915
Simple unified form for the major no-hidden-variables theorems
Mermin, N. D. (1990) · Physical Review Letters · doi:10.1103/physrevlett.65.3373 · Cited by 753
A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
Navascués, M., Pironio, S., & Acín, A. (2008) · New Journal of Physics · doi:10.1088/1367-2630/10/7/073013 · Cited by 721
Step-by-Step Engineered Multiparticle Entanglement
Rauschenbeutel, A., Nogues, G., Osnaghi, S., Bertet, P., Brune, M., Raimond, J.-M., & Haroche, S. (2000) · Science · doi:10.1126/science.288.5473.2024 · Cited by 645
Experimental Two-Photon, Three-Dimensional Entanglement for Quantum Communication
Vaziri, A., Weihs, G., & Zeilinger, A. (2002) · Physical Review Letters · doi:10.1103/physrevlett.89.240401 · Cited by 638
Chi-Chih Yao, A. (2002) · Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science · doi:10.1109/sfcs.1993.366852 · Cited by 633
Hidden-Variable Example Based upon Data Rejection
Pearle, P. M. (1970) · Physical Review D · doi:10.1103/physrevd.2.1418 · Cited by 619
Nonlocal correlations as an information-theoretic resource
Barrett, J., Linden, N., Massar, S., Pironio, S., Popescu, S., & Roberts, D. (2005) · Physical Review A · doi:10.1103/physreva.71.022101 · Cited by 616
Self-citationProposed Experiment to Test Local Hidden Variable Theories.
Clauser, J. F., Horne, M. A., Shimony, A., & Holt, R. A. (1970) · Physical Review Letters · doi:10.1103/physrevlett.24.549 · Cited by 575
Bounding the Set of Quantum Correlations
Navascués, M., Pironio, S., & Acín, A. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.010401 · Cited by 551
Quantum Amplitude Amplification and Estimation
Gilles Brassard, A., Høyer, P., Mosca, M., & Tapp, A. (2000) · doi:10.48550/arxiv.quant-ph/0005055 · Cited by 514
All-multipartite Bell-correlation inequalities for two dichotomic observables per site
Werner, R. F., & Wolf, M. M. (2001) · Physical Review A · doi:10.1103/physreva.64.032112 · Cited by 498
Kushilevitz, E., & Nisan, N. (1996) · Cambridge University Press eBooks · doi:10.1017/cbo9780511574948 · Cited by 477
Bell’s Theorem for General N-Qubit States
Żukowski, M., & Brukner, Č. (2002) · Physical Review Letters · doi:10.1103/physrevlett.88.210401 · Cited by 422
Substituting quantum entanglement for communication
Cleve, R., & Buhrman, H. (1997) · Physical Review A · doi:10.1103/physreva.56.1201 · Cited by 416
Self-citationLimit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial
Brassard, G., Buhrman, H., Linden, N., Méthot, A. A., Tapp, A., & Unger, F. (2006) · Physical Review Letters · doi:10.1103/physrevlett.96.250401 · Cited by 404
Self-citationGeneral properties of nonsignaling theories
Masanes, L., Acin, A., & Gisin, N. (2006) · Physical Review A · doi:10.1103/physreva.73.012112 · Cited by 401
A relevant two qubit Bell inequality inequivalent to the CHSH inequality
Collins, D., & Gisin, N. (2004) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/37/5/021 · Cited by 393
Bell Inequality Violation with Two Remote Atomic Qubits
Matsukevich, D. N., Maunz, P., Moehring, D. L., Olmschenk, S., & Monroe, C. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.150404 · Cited by 392
Quantum vs. classical communication and computation
Buhrman, H., Cleve, R., & Wigderson, A. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276713 · Cited by 389
Self-citationQuantum analogues of the Bell inequalities. The case of two spatially separated domains
Tsirel'son, B. S. (1987) · Journal of Soviet Mathematics · doi:10.1007/bf01663472 · Cited by 381
Distribution of Time-Bin Entangled Qubits over 50 km of Optical Fiber
Marcikic, I., de Riedmatten, H., Tittel, W., Zbinden, H., Legré, M., & Gisin, N. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.180502 · Cited by 343
Communication Cost of Simulating Bell Correlations
Toner, B. F., & Bacon, D. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.187904 · Cited by 338
Symposium on the foundations of modern physics
Raczyński, A. (1986) · Reports on Mathematical Physics · doi:10.1016/0034-4877(86)90059-5 · Cited by 334
Consequences and Limits of Nonlocal Strategies
Cleve, R., Høyer, P., Toner, B., & Watrous, J. (2004) · Cited by 321
Self-citationBarrett, J. (2002) · Physical Review A · doi:10.1103/physreva.65.042302 · Cited by 320
Testing the Dimension of Hilbert Spaces
Brunner, N., Pironio, S., Acin, A., Gisin, N., Méthot, A. A., & Scarani, V. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.210503 · Cited by 304
What's Wrong with these Elements of Reality?
Mermin, N. D. (1990) · Physics Today · doi:10.1063/1.2810588 · Cited by 293
Most Quantum States Are Too Entangled To Be Useful As Computational Resources
Gross, D., Flammia, S. T., & Eisert, J. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.190501 · Cited by 284
Optimal lower bounds for quantum automata and random access codes
Nayak, A. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814608 · Cited by 275
Bell’s Inequalities and Quantum Communication Complexity
Brukner, Č., Żukowski, M., Pan, J.-W., & Zeilinger, A. (2004) · Physical Review Letters · doi:10.1103/physrevlett.92.127901 · Cited by 265
Cost of Exactly Simulating Quantum Entanglement with Classical Communication
Brassard, G., Cleve, R., & Tapp, A. (1999) · Physical Review Letters · doi:10.1103/physrevlett.83.1874 · Cited by 245
Self-citationImplausible consequences of superstrong nonlocality
van Dam, W. (2013) · Natural Computing · doi:10.1007/s11047-012-9353-6 · Cited by 232
Exponential separation of quantum and classical communication complexity
Raz, R. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301343 · Cited by 224
Quantum Communication Complexity
Brassard, G. (2003) · Foundations of Physics · doi:10.1023/a:1026009100467 · Cited by 220
Bell-Type Test of Energy-Time Entangled Qutrits
Thew, R. T., Acín, A., Zbinden, H., & Gisin, N. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.010503 · Cited by 219
Experimental Violation of Local Realism by Four-Photon Greenberger-Horne-Zeilinger Entanglement
Zhao, Z., Yang, T., Chen, Y.-A., Zhang, A.-N., Żukowski, M., & Pan, J.-W. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.180401 · Cited by 215
Bell inequalities and entanglement
Werner, R. F., & Wolf, M. M. (2001) · doi:10.5555/2011339.2011340 · Cited by 212
A local hidden variable model of quantum correlation exploiting the detection loophole
Gisin, N., & Gisin, B. (1999) · Physics Letters A · doi:10.1016/s0375-9601(99)00519-8 · Cited by 212
Quantum Entanglement and Communication Complexity
Buhrman, H., Cleve, R., & van Dam, W. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539797324886 · Cited by 206
Self-citationQuantum search of spatial regions
Aaronson, S., & Ambainis, A. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2003.1238194 · Cited by 206
Grothendieck’s constant and local models for noisy entangled quantum states
Acín, A., Gisin, N., & Toner, B. (2006) · Physical Review A · doi:10.1103/physreva.73.062105 · Cited by 201
The Quantum Moment Problem and Bounds on Entangled Multi-prover Games
Doherty, A. C., Liang, Y.-C., Toner, B., & Wehner, S. (2008) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2008.26 · Cited by 193
“All versus Nothing” Inseparability for Two Observers
Cabello, A. (2001) · Physical Review Letters · doi:10.1103/physrevlett.87.010403 · Cited by 186
Entanglement and non-locality are different resources
Brunner, N., Gisin, N., & Scarani, V. (2005) · New Journal of Physics · doi:10.1088/1367-2630/7/1/088 · Cited by 182
Quantum communication complexity of symmetric predicates
Razborov, A. A. (2003) · Izvestiya: Mathematics · doi:10.1070/im2003v067n01abeh000422 · Cited by 181
Simulating Maximal Quantum Entanglement without Communication
Cerf, N. J., Gisin, N., Massar, S., & Popescu, S. (2005) · Physical Review Letters · doi:10.1103/physrevlett.94.220403 · Cited by 174
Self-citationOn the degree of polynomials that approximate symmetric Boolean functions (preliminary version)
Paturi, R. (1992) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/129712.129758 · Cited by 172
Bell's Theorem without Inequalities and without Probabilities for Two Observers
Cabello, A. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.1911 · Cited by 169
Brassard, G., Broadbent, A., & Tapp, A. (2005) · Foundations of Physics · doi:10.1007/s10701-005-7353-4 · Cited by 165
Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R., & de Wolf, R. (2007) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1250790.1250866 · Cited by 160
Frankl, P., & Rödl, V. (1987) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1987-0871675-6 · Cited by 159
Unbounded Violation of Tripartite Bell Inequalities
Pérez-García, D., Wolf, M. M., Palazuelos, C., Villanueva, I., & Junge, M. (2008) · Communications in Mathematical Physics · doi:10.1007/s00220-008-0418-4 · Cited by 158
Lower bound on the dimension of a quantum system given measured data
Wehner, S., Christandl, M., & Doherty, A. C. (2008) · Physical Review A · doi:10.1103/physreva.78.062112 · Cited by 153
Detection Loophole in Asymmetric Bell Experiments
Brunner, N., Gisin, N., Scarani, V., & Simon, C. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.220403 · Cited by 137
Schwankung von Polynomen zwischen Gitterpunkten
Ehlich, H., & Zeller, K. (1964) · Mathematische Zeitschrift · doi:10.1007/bf01111276 · Cited by 136
Experimental Bell Inequality Violation with an Atom and a Photon
Moehring, D. L., Madsen, M. J., Blinov, B. B., & Monroe, C. R. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.090410 · Cited by 134
Quantum Entanglement and the Communication Complexity of the Inner Product Function
Cleve, R., van Dam, W., Nielsen, M., & Tapp, A. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49208-9_4 · Cited by 133
Self-citationBrassard, G., Broadbent, A., & Tapp, A. (2004) · CERN Document Server (European Organization for Nuclear Research) · Cited by 125
Nonlocality Distillation and Postquantum Theories with Trivial Communication Complexity
Brunner, N., & Skrzypczyk, P. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.160403 · Cited by 124
Multiparty quantum communication complexity
Buhrman, H., van Dam, W., Høyer, P., & Tapp, A. (1999) · Physical Review A · doi:10.1103/physreva.60.2737 · Cited by 121
Self-citationExperimental test of local hidden-variable theories
Shimony, A. (1993) · Cambridge University Press eBooks · doi:10.1017/cbo9781139172196.007 · Cited by 115
Exponential separation of quantum and classical one-way communication complexity
Bar-Yossef, Z., Jayram, T. S., & Kerenidis, I. (2004) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1007352.1007379 · Cited by 111
Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
Klauck, H., Špalek, R., & de Wolf, R. (2007) · SIAM Journal on Computing · doi:10.1137/05063235x · Cited by 108
Entanglement and non-locality are different resources
Brunner, N., Gisin, N., & Scarani, V. (2005) · Archive ouverte UNIGE (University of Geneva) · Cited by 103
A local hidden variable model of quantum correlation exploiting the detection loophole
Gisin, N., & Gisin, B. V. (1999) · CERN Document Server (European Organization for Nuclear Research) · Cited by 103
Minimum Detection Efficiency for a Loophole-Free Atom-Photon Bell Experiment
Cabello, A., & Larsson, J.-Å. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.220402 · Cited by 101
Quantum entanglement and the communication complexity of the inner product function
Cleve, R., van Dam, W., Nielsen, M. A., & Tapp, A. (2012) · Theoretical Computer Science · doi:10.1016/j.tcs.2012.12.012 · Cited by 101
Self-citationNonlocality, closing the detection loophole, and communication complexity
Massar, S. (2002) · Physical Review A · doi:10.1103/physreva.65.032121 · Cited by 98
Self-citationSimulating quantum correlations as a distributed sampling problem
Degorre, J., Laplante, S., & Roland, J. (2005) · Physical Review A · doi:10.1103/physreva.72.062314 · Cited by 97
Towards quantifying non-local information transfer: finite-bit non-locality
Steiner, M. (2000) · Physics Letters A · doi:10.1016/s0375-9601(00)00315-7 · Cited by 90
Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R., & de Wolf, R. (2008) · SIAM Journal on Computing · doi:10.1137/070706550 · Cited by 90
Förster, M., Winkler, S., & Wolf, S. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.120401 · Cited by 87
Classical simulation of quantum entanglement without local hidden variables
Massar, S., Bacon, D., Cerf, N. J., & Cleve, R. (2001) · Physical Review A · doi:10.1103/physreva.63.052305 · Cited by 78
Self-citationThe pattern matrix method for lower bounds on quantum communication
Sherstov, A. A. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374392 · Cited by 75
Public vs. private coin flips in one round communication games (extended abstract)
Newman, I., & Szegedy, M. (1996) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/237814.238004 · Cited by 72
Quantum mysteries revisited again
Aravind, P. K. (2004) · American Journal of Physics · doi:10.1119/1.1773173 · Cited by 72
Bounding the dimension of bipartite quantum systems
Vértesi, T., & Pál, K. F. (2009) · Physical Review A · doi:10.1103/physreva.79.042106 · Cited by 71
Towards Quantifying Non-Local Information Transfer: Finite-Bit Non-Locality
Steiner, M. (2000) · CERN Document Server (European Organization for Nuclear Research) · Cited by 69
Bell inequalities resistant to detector inefficiency
Massar, S., Pironio, S., Roland, J., & Gisin, B. (2002) · Physical Review A · doi:10.1103/physreva.66.052112 · Cited by 63
Self-citationA Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof
Rivlin, T. J., & Cheney, E. W. (1966) · SIAM Journal on Numerical Analysis · doi:10.1137/0703024 · Cited by 60
Communication Complexity in a 3-Computer Model
Ambainis, A. (1996) · Algorithmica · doi:10.1007/bf01955678 · Cited by 59
Single-Qubit Optical Quantum Fingerprinting
Horn, R. T., Бабичев, С. А., Marzlin, K.-P., Lvovsky, A. I., & Sanders, B. C. (2005) · Physical Review Letters · doi:10.1103/physrevlett.95.150502 · Cited by 58
Lower bounds in communication complexity based on factorization norms
Linial, N., & Shraibman, A. (2008) · Random Structures and Algorithms · doi:10.1002/rsa.20232 · Cited by 53
Experimental quantum communication complexity
Trojek, P., Schmid, C., Bourennane, M., Brukner, Č., Żukowski, M., & Weinfurter, H. (2005) · Physical Review A · doi:10.1103/physreva.72.050305 · Cited by 52
On the power of quantum fingerprinting
Yao, A. C.-C. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780554 · Cited by 52
Nonlocal correlations as an information-theoretic resource (11 pages)
Roberts, D. A., Massar, S., Pironio, S., et al. (2005) · Physical Review A · Cited by 47
Self-citationStronger Two-Observer All-Versus-Nothing Violation of Local Realism
Cabello, A. (2005) · Physical Review Letters · doi:10.1103/physrevlett.95.210401 · Cited by 39
Combinatorics and Quantum Nonlocality
Buhrman, H., Høyer, P., Massar, S., & Röhrig, H. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.047903 · Cited by 39
Self-citationFeasible quantum communication complexity protocol
Galvão, E. F. (2001) · Physical Review A · doi:10.1103/physreva.65.012318 · Cited by 34
Bounded-error quantum state identification and exponential separations in communication complexity
Gavinsky, D., Kempe, J., Regev, O., & de Wolf, R. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132602 · Cited by 33
Simulation of partial entanglement with nonsignaling resources
Brunner, N., Gisin, N., Popescu, S., & Scarani, V. (2008) · Physical Review A · doi:10.1103/physreva.78.052111 · Cited by 30
One-qubit fingerprinting schemes
de Beaudrap, N. (2004) · Physical Review A · doi:10.1103/physreva.69.022307 · Cited by 30
Experimental quantum multimeter and one-qubit fingerprinting
Du, J., Zou, P., Peng, X., Oi, D. K. L., Kwek, L. C., Oh, C. H., & EKERT, A. K. (2006) · Physical Review A · doi:10.1103/physreva.74.042319 · Cited by 29
Quantum fingerprinting with a single particle
Massar, S. (2005) · Physical Review A · doi:10.1103/physreva.71.012310 · Cited by 29
Self-citationOn communication over an entanglement-assisted quantum channel
Nayak, A., & Salzman, J. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.510007 · Cited by 28
Classical interaction cannot replace a quantum message
Gavinsky, D. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374393 · Cited by 24
Simulating Quantum Correlations with Finite Communication
Regev, O., & Toner, B. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.31 · Cited by 24
Strengths and Weaknesses of Quantum Fingerprinting
Gavinsky, D., Kempe, J., & de Wolf, R. (2006) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2006.39 · Cited by 22
A generalized Grothendieck inequality and entanglement in XOR gamesPreprint
Briët, J., Buhrman, H., & Toner, B. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0901.2009 · Cited by 19
Self-citationClassical Interaction Cannot Replace Quantum NonlocalityPreprint
Gavinsky, D. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0901.0956 · Cited by 18
Quantum Communication ComplexityPreprint
Klauck, H. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0005032 · Cited by 18
Strengths and Weaknesses of Quantum FingerprintingPreprint
Gavinsky, D., Kempe, J., & de Wolf, R. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0603173 · Cited by 18
Single-qubit optical quantum fingerprinting
Horn, R. T., Marzlin, K.-P., & Sanders, B. C. (2004) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.562449 · Cited by 12
Experimental quantum “Guess my Number” protocol using multiphoton entanglement
Zhang, J., Bao, X., Chen, T., Yang, T., Cabello, A., & Pan, J.-W. (2007) · Physical Review A · doi:10.1103/physreva.75.022302 · Cited by 11
On communication over an entanglement-assisted quantum channel
Nayak, A., & Salzman, J. (2003) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2002.1004331 · Cited by 11
Multipartite nonlocal quantum correlations resistant to imperfections
Buhrman, H., Høyer, P., Röhrig, H., & Massar, S. (2006) · Physical Review A · doi:10.1103/physreva.73.012321 · Cited by 7
Self-citationProposed experiment for the quantum “Guess My Number” protocol
Cabello, A., & López-Tarrida, A. J. (2005) · Physical Review A · doi:10.1103/physreva.71.020301 · Cited by 6
On the power of quantum fingerprinting
Yao, A. C.-C. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780551.780554 · Cited by 5
Cited by
Brunner, N., Cavalcanti, D., Pironio, S., Scarani, V., & Wehner, S. (2014) · Reviews of Modern Physics · doi:10.1103/revmodphys.86.419 · Cited by 2,688
Quantum internet: a vision for the road ahead
Wehner, S., Elkouss, D., & Hanson, R. (2018) · Science · doi:10.1126/science.aam9288 · Cited by 2,467
Chitambar, E., & Gour, G. (2019) · Reviews of Modern Physics · doi:10.1103/revmodphys.91.025001 · Cited by 1,276
Quantum algorithms: an overview
Montanaro, A. (2016) · npj Quantum Information · doi:10.1038/npjqi.2015.23 · Cited by 1,071
“We will also not cover the important topics of how to actually build a quantum computer [59] (in theory or in practice) and quantum error-correction [42], nor quantum communication complexity [23] or quantum Shannon theory [98].”
Information causality as a physical principle
Pawłowski, M., Paterek, T., Kaszlikowski, D., Scarani, V., Winter, A., & Żukowski, M. (2009) · Nature · doi:10.1038/nature08400 · Cited by 775
Metadata
- Authors
- Buhrman, H., Cleve, R., Massar, S., & de Wolf, R.
- Venue
- Reviews of Modern Physics
- Publisher
- American Physical Society (APS)
- Published
- 2010-03-11
- Volume
- 82
- Issue
- 1
- Pages
- 665-698
- ISSN
- 0034-6861 (ISSN-L)
- 1539-0756
- OpenAlex
- W1980575345
- Cited by
- 622
- References
- 155
- FWCI
- 33.67
- Type
- journal article
- Language
- en
- Open access
- green
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.