Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cambridge University Press eBooks

Randomness

Scott Aaronson

Published Mar 14, 2013• 0 citations
Publisher

Abstract

In the last two chapters, we talked about computational complexity up till the early 1970s. Here, we'll add a new ingredient to our already simmering stew – something that was thrown in around the mid-1970s, and that now pervades complexity to such an extent that it's hard to imagine doing anything without it. This new ingredient is randomness . Certainly, if you want to study quantum computing, then you first have to understand randomized computing. I mean, quantum amplitudes only become interesting when they exhibit some behavior that classical probabilities don't : contextuality, interference, entanglement (as opposed to correlation), etc. So we can't even begin to discuss quantum mechanics without first knowing what it is that we're comparing against. Alright, so what is randomness? Well, that’s a profound philosophical question, but I’m a simpleminded person. So, you’ve got some probability p , which is a real number in the unit interval [0, 1]. That’s randomness. But wasn’t it a big achievement when Kolmogorov put probability on an axiomatic basis in the 1930s? Yes, it was! But in this chapter, we’ll only care about probability distributions over finitely many events, so all the subtle questions of integrability, measurability, and so on won’t arise. In my view, probability theory is yet another example where mathematicians immediately go to infinite-dimensional spaces, in order to solve the problem of having a nontrivial problem to solve! And that’s fine – whatever floats your boat. I’m not criticizing that. But in theoretical computer science, we’ve already got our hands full with 2n choices. We need 2ℵ0 choices like we need a hole in the head.

DOI
10.1017/cbo9780511979309.008

Related papers

Quantum computing

Scott Aaronson

Alright, so now we've got this beautiful theory of quantum mechanics, and the possibly-even-more-beautiful theory of computational complexity. Clearly, with two theories this beautiful, you can't just let them stay single – you have to set them up, see if they hit it off, etc. And that brings us to the class BQP : Bounded-Error Quantum Polynomial-Time. We talked in Chapter 7 about BPP , or Bounded-Error Probabilistic Polynomial-Time. Informally, BPP is the class of computational problems that are efficiently solvable in the physical world if classical physics is true. Now we ask, what problems are efficiently solvable in the physical world if (as seems more likely) quantum physics is true? To me it’s sort of astounding that it took until the 1990s for anyone to really seriously ask this question, given that all the tools for asking it were in place by the 1960s or even earlier. It makes you wonder, what similarly obvious questions are there today that no one’s asking?

Cambridge University Press eBooks•Mar 14, 2013•1 citation

Skepticism of quantum computing

Scott Aaronson

Last chapter, we talked about whether quantum states should be thought of as exponentially long vectors, and I brought up class BQP/qpoly and concepts like quantum advice. Actually, I’d say that the main reason why I care is something I didn't mention last time, which is that it relates to whether we should expect quantum computing to be fundamentally possible or not. There are people, like Leonid Levin and Oded Goldreich, who just take it as obvious that quantum computing must be impossible. Part of their argument is that it's extravagant to imagine a world where describing the state of 200 particles takes more bits then there are particles in the universe. To them, this is a clear indication something is going to break down. So part of the reason that I like to study the power of quantum proofs and quantum advice is that it helps us answer the question of whether we really should think of a quantum state as encoding an exponential amount of information. So, on to the Eleven Objections. Works on paper, not in practice. Violates Extended Church–Turing Thesis. Not enough “real physics.” Small amplitudes are unphysical. Exponentially large states are unphysical. Quantum computers are just souped-up analog computers. Quantum computers aren't like anything we've ever seen before. Quantum mechanics is just an approximation to some deeper theory. Decoherence will always be worse than the fault-tolerance threshold. We don't need fault-tolerance for classical computers. Errors aren't independent. What I did is to write out every skeptical argument against the possibility of quantum computing that I could think of. We'll just go through them, and make commentary along the way. Let me just start by saying that my point of view has always been rather simple: it's entirely conceivable that quantum computing is impossible for some fundamental reason. If so, then that's by far the most exciting thing that could happen for us. That would be much more interesting than if quantum computing were possible, because it changes our understanding of physics. To have a quantum computer capable of factoring 10000-digit integers is the relatively boring outcome – the outcome that we'd expect based on the theories we already have.

Cambridge University Press eBooks•Mar 14, 2013•1 citation

Quantum Computation

David Tong

The universe we live in is both strange and interesting. This strangeness comes about because, at the most fundamental level, the universe is governed by the laws of quantum mechanics. This is the most spectacularly accurate and powerful theory ever devised, one that has given us insights into many aspects of the world, from the structure of matter to the meaning of information. This textbook provides a comprehensive account of all things quantum. It starts by introducing the wavefunction and its interpretation as an ephemeral wave of complex probability, before delving into the mathematical formalism of quantum mechanics and exploring its diverse applications, from atomic physics and scattering, to quantum computing. Designed to be accessible, this volume is suitable for both students and researchers, beginning with the basics before progressing to more advanced topics.

Cambridge University Press eBooks•Jun 19, 2025•0 citations

Ask me anything

Scott Aaronson

To remind you, this book is based on a course I taught in 2006. On the last day of class, I followed the great tradition pioneered by Richard Feynman, in which the last class should be one where you can ask the teacher anything. Feynman's rule was that you could ask about anything except politics, religion, or the final exam. In my case, there was no final exam, and I didn't even make politics or religion off-limits. This chapter collects some of the questions people asked me, together with my responses. Student: Do you often think about using computer science to limit or give us a hint about physical theories? Do you think that we'll be able to discover physical theories which give more powerful models than quantum computation? Scott: Is BQP the end of the road, or is there more to be found? That's a fantastic question, and I wish more people would think about it. I’m being a bit of a politician here and not answering directly, because obviously the answer is “I don't know.” I guess the whole idea with science is that if we don't know the answer, we don't try to sprout one out of our butt or something. We try to base our answers on something. So, everything we know is consistent with the idea that quantum computing is the end of the road. Greg Kuperberg had an analogy I really liked. He said that there are people who keep saying that we've gone from classical to quantum mechanics so what other surprises are in store? But maybe that's like first assuming the Earth is flat, and then on discovering that it's round, saying who knows, maybe it has the topology of a Klein bottle. There's a surprise in a given direction, but once you've assimilated it, there may not be any further surprise in that same direction.

Cambridge University Press eBooks•Mar 14, 2013•5 citations

Introduction to Quantum Computation

Tudor D. Stanescu

Quantum computation is not an imminent achievement . We will not wake up tomorrow and find quantum computers on our desks. At the time of this writing, IBM has just unveiled the Condor – a chip containing 1,121 superconducting qubits. This number will likely increase (perhaps spectacularly) in the near future. However, the qubits have a relatively large error rate and, in the absence of a breakthrough advance that significantly lowers this rate, one would need hundreds of physical qubits to realize an error-corrected logical qubit. Predicting how long it will take to achieve the controlled manipulation of thousands of (logical) qubits (i.e., a number of qubits consistent with the “useful” implementation of known quantum algorithms) is probably not a rational undertaking, at least for a scientist. The most pessimistic experts regard the lively research activity in quantum computation as a waste of time and resources. But the pervading mood in this field is one of cautious optimism, particularly considering the possibility of achieving useful tasks (e.g., simulating quantum systems) with a sufficiently large number of “imperfect” qubits. Expediency may be responsible for some of this optimism; a good feeling about the prospects for quantum computation certainly helps when it comes to publishing papers and getting funded. Ultimately, however, the responsibility for the wise distribution of resources rests with the funding agencies; scientists, on the other hand, are called to explore every aspect of real and possible worlds that looks fascinating and worthy of their curiosity. From this perspective, quantum computation (defined broadly) offers plenty of opportunities for producing “good science.” The problems brought to the fore by the development of this field range from basic questions regarding the foundations of quantum mechanics and unsolved problems in computational complexity, to the investigation of new phases of matter (e.g., topological quantum phases), the quest for “complete” control over quantum systems, and the critical need for significant advances in materials science and device fabrication (e.g., engineering nanoscale heterostructures with atomic precision). Progress in these areas will naturally open new possibilities for interesting applications. Precisely identifying these applications is premature, but building a (general purpose) quantum computer will not necessarily be among the first of them.

CRC Press eBooks•May 3, 2024•2 citations

Generating Randomness from a Computable, Non-Random Sequence of Qubits

Tejas Bhojraj

•Jan 1, 2022•0 citations
In the last two chapters, we talked about computational complexity up till the early 1970s. Here, we'll add a new ingredient to our already simmering stew – something that was thrown in around the mid-1970s, and that now pervades complexity to such an extent that it's hard to imagine doing anything without it. This new ingredient is randomness . Certainly, if you want to study quantum computing, then you first have to understand randomized computing. I mean, quantum amplitudes only become interesting when they exhibit some behavior that classical probabilities don't : contextuality, interference, entanglement (as opposed to correlation), etc. So we can't even begin to discuss quantum mechanics without first knowing what it is that we're comparing against. Alright, so what is randomness? Well, that’s a profound philosophical question, but I’m a simpleminded person. So, you’ve got some probability p , which is a real number in the unit interval [0, 1]. That’s randomness. But wasn’t it a big achievement when Kolmogorov put probability on an axiomatic basis in the 1930s? Yes, it was! But in this chapter, we’ll only care about probability distributions over finitely many events, so all the subtle questions of integrability, measurability, and so on won’t arise. In my view, probability theory is yet another example where mathematicians immediately go to infinite-dimensional spaces, in order to solve the problem of having a nontrivial problem to solve! And that’s fine – whatever floats your boat. I’m not criticizing that. But in theoretical computer science, we’ve already got our hands full with 2n choices. We need 2ℵ0 choices like we need a hole in the head.
Alright, so now we've got this beautiful theory of quantum mechanics, and the possibly-even-more-beautiful theory of computational complexity. Clearly, with two theories this beautiful, you can't just let them stay single – you have to set them up, see if they hit it off, etc. And that brings us to the class BQP : Bounded-Error Quantum Polynomial-Time. We talked in Chapter 7 about BPP , or Bounded-Error Probabilistic Polynomial-Time. Informally, BPP is the class of computational problems that are efficiently solvable in the physical world if classical physics is true. Now we ask, what problems are efficiently solvable in the physical world if (as seems more likely) quantum physics is true? To me it’s sort of astounding that it took until the 1990s for anyone to really seriously ask this question, given that all the tools for asking it were in place by the 1960s or even earlier. It makes you wonder, what similarly obvious questions are there today that no one’s asking?
Last chapter, we talked about whether quantum states should be thought of as exponentially long vectors, and I brought up class BQP/qpoly and concepts like quantum advice. Actually, I’d say that the main reason why I care is something I didn't mention last time, which is that it relates to whether we should expect quantum computing to be fundamentally possible or not. There are people, like Leonid Levin and Oded Goldreich, who just take it as obvious that quantum computing must be impossible. Part of their argument is that it's extravagant to imagine a world where describing the state of 200 particles takes more bits then there are particles in the universe. To them, this is a clear indication something is going to break down. So part of the reason that I like to study the power of quantum proofs and quantum advice is that it helps us answer the question of whether we really should think of a quantum state as encoding an exponential amount of information. So, on to the Eleven Objections. Works on paper, not in practice. Violates Extended Church–Turing Thesis. Not enough “real physics.” Small amplitudes are unphysical. Exponentially large states are unphysical. Quantum computers are just souped-up analog computers. Quantum computers aren't like anything we've ever seen before. Quantum mechanics is just an approximation to some deeper theory. Decoherence will always be worse than the fault-tolerance threshold. We don't need fault-tolerance for classical computers. Errors aren't independent. What I did is to write out every skeptical argument against the possibility of quantum computing that I could think of. We'll just go through them, and make commentary along the way. Let me just start by saying that my point of view has always been rather simple: it's entirely conceivable that quantum computing is impossible for some fundamental reason. If so, then that's by far the most exciting thing that could happen for us. That would be much more interesting than if quantum computing were possible, because it changes our understanding of physics. To have a quantum computer capable of factoring 10000-digit integers is the relatively boring outcome – the outcome that we'd expect based on the theories we already have.
The universe we live in is both strange and interesting. This strangeness comes about because, at the most fundamental level, the universe is governed by the laws of quantum mechanics. This is the most spectacularly accurate and powerful theory ever devised, one that has given us insights into many aspects of the world, from the structure of matter to the meaning of information. This textbook provides a comprehensive account of all things quantum. It starts by introducing the wavefunction and its interpretation as an ephemeral wave of complex probability, before delving into the mathematical formalism of quantum mechanics and exploring its diverse applications, from atomic physics and scattering, to quantum computing. Designed to be accessible, this volume is suitable for both students and researchers, beginning with the basics before progressing to more advanced topics.
To remind you, this book is based on a course I taught in 2006. On the last day of class, I followed the great tradition pioneered by Richard Feynman, in which the last class should be one where you can ask the teacher anything. Feynman's rule was that you could ask about anything except politics, religion, or the final exam. In my case, there was no final exam, and I didn't even make politics or religion off-limits. This chapter collects some of the questions people asked me, together with my responses. Student: Do you often think about using computer science to limit or give us a hint about physical theories? Do you think that we'll be able to discover physical theories which give more powerful models than quantum computation? Scott: Is BQP the end of the road, or is there more to be found? That's a fantastic question, and I wish more people would think about it. I’m being a bit of a politician here and not answering directly, because obviously the answer is “I don't know.” I guess the whole idea with science is that if we don't know the answer, we don't try to sprout one out of our butt or something. We try to base our answers on something. So, everything we know is consistent with the idea that quantum computing is the end of the road. Greg Kuperberg had an analogy I really liked. He said that there are people who keep saying that we've gone from classical to quantum mechanics so what other surprises are in store? But maybe that's like first assuming the Earth is flat, and then on discovering that it's round, saying who knows, maybe it has the topology of a Klein bottle. There's a surprise in a given direction, but once you've assimilated it, there may not be any further surprise in that same direction.
Quantum computation is not an imminent achievement . We will not wake up tomorrow and find quantum computers on our desks. At the time of this writing, IBM has just unveiled the Condor – a chip containing 1,121 superconducting qubits. This number will likely increase (perhaps spectacularly) in the near future. However, the qubits have a relatively large error rate and, in the absence of a breakthrough advance that significantly lowers this rate, one would need hundreds of physical qubits to realize an error-corrected logical qubit. Predicting how long it will take to achieve the controlled manipulation of thousands of (logical) qubits (i.e., a number of qubits consistent with the “useful” implementation of known quantum algorithms) is probably not a rational undertaking, at least for a scientist. The most pessimistic experts regard the lively research activity in quantum computation as a waste of time and resources. But the pervading mood in this field is one of cautious optimism, particularly considering the possibility of achieving useful tasks (e.g., simulating quantum systems) with a sufficiently large number of “imperfect” qubits. Expediency may be responsible for some of this optimism; a good feeling about the prospects for quantum computation certainly helps when it comes to publishing papers and getting funded. Ultimately, however, the responsibility for the wise distribution of resources rests with the funding agencies; scientists, on the other hand, are called to explore every aspect of real and possible worlds that looks fascinating and worthy of their curiosity. From this perspective, quantum computation (defined broadly) offers plenty of opportunities for producing “good science.” The problems brought to the fore by the development of this field range from basic questions regarding the foundations of quantum mechanics and unsolved problems in computational complexity, to the investigation of new phases of matter (e.g., topological quantum phases), the quest for “complete” control over quantum systems, and the critical need for significant advances in materials science and device fabrication (e.g., engineering nanoscale heterostructures with atomic precision). Progress in these areas will naturally open new possibilities for interesting applications. Precisely identifying these applications is premature, but building a (general purpose) quantum computer will not necessarily be among the first of them.