The DOI matches its Crossref record; 33 of the 33 references it cites were found in a registry or an index.
Quantum Computing since Democritus
Abstract
Written by noted quantum computing theorist Scott Aaronson, this book takes readers on a tour through some of the deepest ideas of maths, computer science and physics. Full of insights, arguments and philosophical perspectives, the book covers an amazing array of topics. Beginning in antiquity with Democritus, it progresses through logic and set theory, computability and complexity theory, quantum computing, cryptography, the information content of quantum states and the interpretation of quantum mechanics. There are also extended discussions about time travel, Newcomb's Paradox, the anthropic principle and the views of Roger Penrose. Aaronson's informal style makes this fascinating book accessible to readers with scientific backgrounds, as well as students and researchers working in physics, computer science, mathematics and philosophy.
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
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
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2009) · Journal of the ACM · doi:10.1145/1568318.1568324 · Cited by 2,315
How to construct random functions
Goldreich, O., Goldwasser, S., & Micali, S. (1986) · Journal of the ACM · doi:10.1145/6490.6503 · Cited by 2,115
Unconscious determinants of free decisions in the human brain
Soon, C. S., Brass, M., Heinze, H.-J., & Haynes, J.-D. (2008) · Nature Neuroscience · doi:10.1038/nn.2112 · Cited by 1,741
A Pseudorandom Generator from any One-way Function
HÅstad, J., Impagliazzo, R., Levin, L. A., & Luby, M. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539793244708 · Cited by 1,653
Random numbers certified by Bell’s theorem
Pironio, S., Acín, A., Massar, S., de la Giroday, A. B., Matsukevich, D. N., Maunz, P., Olmschenk, S., Hayes, D., Luo, L., Manning, T. A., et al. (2010) · Nature · doi:10.1038/nature09008 · Cited by 1,420
Parity, circuits, and the polynomial-time hierarchy
Furst, M., Saxe, J. B., & Sipser, M. (1984) · Mathematical Systems Theory · doi:10.1007/bf01744431 · Cited by 938
Algebraic methods in the theory of lower bounds for Boolean circuit complexity
Smolensky, R. (1987) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/28395.28404 · Cited by 845
Public-key cryptosystems from the worst-case shortest vector problem: extended abstract
Peikert, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536461 · Cited by 813
Algebraic methods for interactive proof systems
Lund, C., Fortnow, L., Karloff, H., & Nisan, N. (1992) · Journal of the ACM · doi:10.1145/146585.146605 · Cited by 711
Shamir, A. (1992) · Journal of the ACM · doi:10.1145/146585.146609 · Cited by 662
A public-key cryptosystem with worst-case/average-case equivalence
Ajtai, M., & Dwork, C. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258604 · Cited by 642
Informational derivation of quantum theory
Chiribella, G., D’Ariano, G. M., & Perinotti, P. (2011) · Physical Review A · doi:10.1103/physreva.84.012311 · Cited by 619
∑11-Formulae on finite structures
Ajtai, M. (1983) · Annals of Pure and Applied Logic · doi:10.1016/0168-0072(83)90038-6 · Cited by 585
The fuzzball proposal for black holes: an elementary review
Mathur, S. D. (2005) · CERN Document Server (European Organization for Nuclear Research) · Cited by 564
Razborov, A. A., & Rudich, S. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1494 · Cited by 479
Number-theoretic constructions of efficient pseudo-random functions
Naor, M., & Reingold, O. (2004) · Journal of the ACM · doi:10.1145/972639.972643 · Cited by 368
Quantum computing, postselection, and probabilistic polynomial-time
Aaronson, S. (2005) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2005.1546 · Cited by 311
Self-citationLibet, B. (2005) · The Oxford Handbook of Free Will · doi:10.1093/oxfordhb/9780195178548.003.0025 · Cited by 299
Implications of the Copernican principle for our future prospects
Gott, J. R. (1993) · Nature · doi:10.1038/363315a0 · Cited by 290
Adleman, L. M., DeMarrais, J., & Huang, M.-D. A. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293639 · Cited by 262
Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
Kitaev, A., & Watrous, J. (2000) · Proceedings of the thirty-second annual ACM symposium on Theory of computing · doi:10.1145/335305.335387 · Cited by 218
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
The fabric of reality: the science of parallel universes--and its implications
(1998) · Choice Reviews Online · doi:10.5860/choice.35-3931 · Cited by 200
Algebrization: A New Barrier in Complexity Theory
Aaronson, S., & Wigderson, A. (2009) · ACM Transactions on Computation Theory · doi:10.1145/1490270.1490272 · Cited by 190
Self-citationPP is closed under intersection
Beigel, R., Reingold, N., & Spielman, D. A. (1991) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/103418.103426 · Cited by 159
Quantum mechanics of time travel through post-selected teleportation
Lloyd, S., Maccone, L., García−Patrón, R., Giovannetti, V., & Shikano, Y. (2011) · Physical review. D. Particles, fields, gravitation, and cosmology/Physical review. D. Particles and fields · doi:10.1103/physrevd.84.025007 · Cited by 143
Non-uniform ACC Circuit Lower Bounds
Williams, R. (2011) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2011.36 · Cited by 124
Jain, R., Ji, Z., Upadhyay, S., & Watrous, J. (2011) · Journal of the ACM · doi:10.1145/2049697.2049704 · Cited by 117
Bennett, C. H., Leung, D., Smith, G., & Smolin, J. A. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.170502 · Cited by 88
Are there interactive protocols for co-NP languages?
Fortnow, L., & Sipser, M. (1988) · Information Processing Letters · doi:10.1016/0020-0190(88)90199-8 · Cited by 81
The GCT program toward the P vs. NP problem
Mulmuley, K. (2012) · Communications of the ACM · doi:10.1145/2184319.2184341 · Cited by 49
Circuit Lower Bounds for Merlin–Arthur Classes
Santhanam, R. (2009) · SIAM Journal on Computing · doi:10.1137/070702680 · Cited by 48
Cited by
Quantum machine learning: a classical perspective
Ciliberto, C., Herbster, M., Ialongo, A. D., Pontil, M., Rocchetto, A., Severini, S., & Wossnig, L. (2018) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2017.0551 · Cited by 518
Quantum Computing for Finance: State-of-the-Art and Future Prospects
Egger, D. J., Gambella, C., Marecek, J., McFaddin, S., Mevissen, M., Raymond, R., Simonetto, A., Woerner, S., & Yndurain, E. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3030314 · Cited by 366
Quantum Low-Density Parity-Check Codes
Breuckmann, N. P., & Eberhardt, J. N. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.040101 · Cited by 328
Stringent and Efficient Assessment of Boson-Sampling Devices
Tichy, M. C., Mayer, K., Buchleitner, A., & Mølmer, K. (2014) · Physical Review Letters · doi:10.1103/physrevlett.113.020502 · Cited by 127
Contracting projected entangled pair states is average-case hard
Haferkamp, J., Hangleiter, D., Eisert, J., & Gluza, M. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.013010 · Cited by 62
Metadata
- Authors
- Aaronson, S.
- Venue
- Cambridge University Press eBooks
- Publisher
- Cambridge University Press
- Published
- 2013-03-14
- OpenAlex
- W574734723
- Cited by
- 352
- References
- 33
- FWCI
- 7.69
- Type
- book
- Language
- en
- Open access
- closed
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.