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

How big are quantum states?

Scott Aaronson

Published Mar 14, 2013• 0 citations
Publisher

Abstract

I'm going to talk about the title question, but first, a little digression. In science, there's this traditional hierarchy where you have biology on top, and chemistry underlies it, and then physics underlies chemistry. If the physicists are in a generous mood, they'll say that math underlies physics. Then, computer science is over somewhere with soil engineering or some other nonscience. Now, my point of view is a bit different: computer science is what mediates between the physical world and the Platonic world. With that in mind, “computer science” is a bit of a misnomer; maybe it should be called “quantitative epistemology.” It's sort of the study of the capacity of finite beings such as us to learn mathematical truths. I hope I’ve been showing you some of that. How do we reconcile this with the notion that any actual implementation of a computer must be based on physics? Wouldn’t the order of physics and CS be reversed? Well, by similar logic one could say that any mathematical proof has to be written on paper, and therefore physics should go below math in the hierarchy. Or one could say that math is basically a field that studies whether particular kinds of Turing machine will halt or not, and so CS is the ground that everything else sits on. Math is then just the special case where the Turing machines enumerate topological spaces or do something else that mathematicians care about. But then, the strange thing is that physics, especially in the form of quantum probability, has lately been seeping down the intellectual hierarchy, contaminating the “lower” levels of math and CS. This is how I’ve always thought about quantum computing: as a case of physics not staying where it’s supposed to in the intellectual hierarchy! If you like, I’m professionally interested in physics precisely to the extent that it seeps down into the “lower” levels, which are supposed to be the least arbitrary ones, and forces me to rethink what I thought I understood about those levels.

DOI
10.1017/cbo9780511979309.015

Related papers

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

A Quantum-Digital Universe

Giacomo Mauro D’Ariano

Can Reality be simulated by a huge Quantum Computer? Do we believe that Reality is made of something more than interacting quantum systems? The idea that the whole Physics is ultimately a quantum computation—a strong quantum version of the Church-Turing hypothesis well synthesized by the Wheeler’s coinage It from bit—is very appealing. It is theoretically very parsimonious: an Occam razor’s quality-guaranteed description of the world. But, if this is the case, then we need to understand the entire Physics as emergent from the quantum computation. Here I will make a short exploration on how this may come about. Ask a physicist what does he thinks the world is made of. Very likely the first impetuous answer will be: it is made of particles! But, at a second thought the answer will be: it is a Quantum Field. Particles are just states or the Field: they can be created and annihilated. We have indeed a beautiful Grand Unified Field Theory, and we are looking forward to see the Higg’s boson at the LHC. But what is the Quantum Field made of? Ultimately, it is made of quantum systems that are interacting, each system located at a different position in space. Things may be indeed more complicated than that, because the field is a continuum. But is Reality actually continuous? We don ’ t know: but it looks easier to think to Reality as a continuum. Now, suppose that this is not the case, namely Reality is ultimately discrete, and the continuum is only a mathematical fiction. Then, what else is out there more than interacting quantum

Advanced Science Letters•Oct 1, 2012•13 citations

Philosophy of Quantum Information Science

Kervalishvili P.J.

Nowadays quantum information science is in a state of theoretic completeness; much is invested to research quality physical solution for quantum computer and applications, so the field is led by physicists and information science and technology professionals. This field proved its potential and many (including us) believe it is in the right direction to go. In this paper we'll try to present and analyze the philosophy and nature of quantum information science and discuss hot topics around them. Although there is plenty of space for discussion around this field, we will concentrate on some important issues, such as quantum communication, algorithms and cryptography. Communication promises to be one of the directions where huge breakthroughs will be observed (entanglement as communication), algorithms have already shown exponential advantage (Shor's factoring) over classical counterparts and different paradigm of information processing. Cryptography seems to utilize general achievements in quantum information science and make encryption protocols very secure. Quantum computation can be understood as a generalization of classical computation: The possible states of a quantum computer are superpositions of bit strings, where the tensor factor is called a quantum bit or qubit. To evaluate the computational complexity of an algorithm, either classical or quantum, it is necessary to specify a set of elementary operations, the number of which used during the computation quantities the complexity. If we allow arbitrary permutations classically, or arbitrary unitary transformations quantum mechanically, any state can be reached from any other state in a single step. The general kind of quantum computer should be programmed to perform distinctively quantum operations such as generating two bits in a superposition state. An appropriate measurement on the final superposed state of the computer produces a probabilistic behavior of the output, and because of this quantum parallelization does not reduce the average time required for parallelizable computation completion. The development of quantum computing science and technology as well as quantum computers as thinking machines is very dependent on different achievements of modern research in fundamental and applied physics as well as novel mathematical methods and tools.

NATO science for peace and security series. Sub-series E, Human and societal dynamics•Jan 1, 2012•2 citations

Mutually Unbiased Bases in Composite Dimensions What I've Already Done in a More "Proper" Tone Pff Whatever...You Go Ahead And Close An Open Problem of 28+ Years With Not One Single Collaborator And Catch Every Stupid Typo That Some Stooge Will Try to Harp On Don't Make Me Laugh. Objections to Tone Are Not Real Objections. The Literature to Date on This Matter Is Pathetic and Inexcusable. It is a Black Dot On Math History. I Can Write Volumes of Fury On This.

Christopher Pompetzki

Mutually Unbiased Bases in Composite DimensionsChris PompetzkiDecember 2025Fine. Here is the original with the ”proper” tone. Lame. Where’s the fun in that.Whatever. Oh how I much prefer people cite my version with the insufferable tone complete with Moby Dick, Shrek, and Drake references. What else would one expect when one man has done what others haven’t done for what 28+ years now in profound isolation. Though sure, I suppose I’ll do the ”right thing” and post my clean(er) version. Imagine my excitement at the notion of some stooges trying to steal my proof and act like they solved the problem when I actually did. Imagine even claiming it without citing me. Hehe. Oh I hope some do. I do not consent to any posting of this on the pathetic, outdated, obselete arXiv that apparently requires some kind of code to publish. We prove that the maximum number of mutually unbiased bases in dimension d is at most p + 1, where p is the smallest prime factor of d. The proof is three steps: (1) mutual unbiasedness forces bi-unimodularity of overlap functions, (2) bi-unimodularity factors through the Chinese Remainder Theorem to prime factors, (3) the Zp factor admits at most p 1 pairwise compatible bi-unimodular families. For d = 6, this gives M (6) = 3. Oh and by the way, yes I do declare that M (6) = 3 ought to be called the Pompetzki-Ahab-Shrek Theorem or something to that effect. Imagine the audacity of all the people who threw in the towel on M (6) = 3 trying to claim credit for what I, the absolute madman have done. Ha. Only a true psycho would stick with this problem for more than a day tops. Oh I know I ought to have ”proper” toned papers and go get a PhD in pure math apparently. Though then I’d have to do some BS that someone else wants me to do instead of doing what I want to do: brutally advancing mankind’s closure of open problems with all the ”Furor Teutonicus” of zee David Hilbert at least cubed hehe. Ja. Gut. You know vat. I zhought about giving zee Verldt zee fully clean und zee neutered und zee ”proper tone” und zhen I zaid NEIN! Ja. Gut. Vhy. Becauseit makes me smirks. Schadenfreude. That’s why.You know what. I just don't care enough to give it to the world fully clean. I must insist that I coat it with zee Scheisse ja. Zat iz vat is required after all zee Scheisse zat zee stupid have talked about the great German Mathematician, David Hilbert, who is sadly no longer with us. Imagine the extent of his fury at how much of the math world has thumbed their noses at him as they say to Hell with the notion that existence matters in math carry a moral imperative for mathematicians to resolve. I'm too furious. I'm too disgusted. The world didn't deserve David Hilbert. Nor Gauss. Nor Euler. Herr Hilbert said: Wir mussen wissen. Wir werden wissen.Many agreed when he was alive. Then he passed. Then people lost their fear of that Germanic fury. Then M(6) went unclosed for what 28+ years GTFO. There's no excuse for it. I'm furious.

•Dec 27, 2025•0 citations

Quantum computers: where physics meets computer science

SOFIA MAVROGIORGOU

Quantum Physics is defined as “the study of matter and energy at the most fundamental level”. It has entirely transformed our perspective of the physical world and is also the foundation of numerous technological advancements. More specifically, quantum mechanics has been applied in sectors such as medicine and biology, with quantum computing emerging as the most prominent among them. [5] The primary objective of this study is to analyse the concepts of quantum computing, focusing on what quantum computers are, how they function, as well as outline and explain the differences between them and standard computational models (classic computers). Furthermore, their relation to the laws of physics will be discussed. Secondarily, this article aims to provide recent achievements, such as existing quantum computers and plans concerning the future so as to underline the role quantum physics will play, shaping the frontier of computation.

Open Schools Journal for Open Science•Jan 12, 2026•0 citations

Using Quantum Computers to Learn Physics

Nathan Wiebe

Since its inception at the beginning of the twentieth century, quantum mechanics has challenged our conceptions of how the universe ought to work; however, the equations of quantum mechanics can be too computationally difficult to solve using existing computers for even modestly large systems. Here I will show that quantum computers can sometimes be used to address such problems and that quantum computer science can assign formal complexities to learning facts about nature. Hence, computer science should not only be regarded as an applied science; it is also of central importance to the foundations of science.

arXiv:1401.4507•Jan 18, 2014•1 citation
I'm going to talk about the title question, but first, a little digression. In science, there's this traditional hierarchy where you have biology on top, and chemistry underlies it, and then physics underlies chemistry. If the physicists are in a generous mood, they'll say that math underlies physics. Then, computer science is over somewhere with soil engineering or some other nonscience. Now, my point of view is a bit different: computer science is what mediates between the physical world and the Platonic world. With that in mind, “computer science” is a bit of a misnomer; maybe it should be called “quantitative epistemology.” It's sort of the study of the capacity of finite beings such as us to learn mathematical truths. I hope I’ve been showing you some of that. How do we reconcile this with the notion that any actual implementation of a computer must be based on physics? Wouldn’t the order of physics and CS be reversed? Well, by similar logic one could say that any mathematical proof has to be written on paper, and therefore physics should go below math in the hierarchy. Or one could say that math is basically a field that studies whether particular kinds of Turing machine will halt or not, and so CS is the ground that everything else sits on. Math is then just the special case where the Turing machines enumerate topological spaces or do something else that mathematicians care about. But then, the strange thing is that physics, especially in the form of quantum probability, has lately been seeping down the intellectual hierarchy, contaminating the “lower” levels of math and CS. This is how I’ve always thought about quantum computing: as a case of physics not staying where it’s supposed to in the intellectual hierarchy! If you like, I’m professionally interested in physics precisely to the extent that it seeps down into the “lower” levels, which are supposed to be the least arbitrary ones, and forces me to rethink what I thought I understood about those levels.
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.
Can Reality be simulated by a huge Quantum Computer? Do we believe that Reality is made of something more than interacting quantum systems? The idea that the whole Physics is ultimately a quantum computation—a strong quantum version of the Church-Turing hypothesis well synthesized by the Wheeler’s coinage It from bit—is very appealing. It is theoretically very parsimonious: an Occam razor’s quality-guaranteed description of the world. But, if this is the case, then we need to understand the entire Physics as emergent from the quantum computation. Here I will make a short exploration on how this may come about. Ask a physicist what does he thinks the world is made of. Very likely the first impetuous answer will be: it is made of particles! But, at a second thought the answer will be: it is a Quantum Field. Particles are just states or the Field: they can be created and annihilated. We have indeed a beautiful Grand Unified Field Theory, and we are looking forward to see the Higg’s boson at the LHC. But what is the Quantum Field made of? Ultimately, it is made of quantum systems that are interacting, each system located at a different position in space. Things may be indeed more complicated than that, because the field is a continuum. But is Reality actually continuous? We don ’ t know: but it looks easier to think to Reality as a continuum. Now, suppose that this is not the case, namely Reality is ultimately discrete, and the continuum is only a mathematical fiction. Then, what else is out there more than interacting quantum
Nowadays quantum information science is in a state of theoretic completeness; much is invested to research quality physical solution for quantum computer and applications, so the field is led by physicists and information science and technology professionals. This field proved its potential and many (including us) believe it is in the right direction to go. In this paper we'll try to present and analyze the philosophy and nature of quantum information science and discuss hot topics around them. Although there is plenty of space for discussion around this field, we will concentrate on some important issues, such as quantum communication, algorithms and cryptography. Communication promises to be one of the directions where huge breakthroughs will be observed (entanglement as communication), algorithms have already shown exponential advantage (Shor's factoring) over classical counterparts and different paradigm of information processing. Cryptography seems to utilize general achievements in quantum information science and make encryption protocols very secure. Quantum computation can be understood as a generalization of classical computation: The possible states of a quantum computer are superpositions of bit strings, where the tensor factor is called a quantum bit or qubit. To evaluate the computational complexity of an algorithm, either classical or quantum, it is necessary to specify a set of elementary operations, the number of which used during the computation quantities the complexity. If we allow arbitrary permutations classically, or arbitrary unitary transformations quantum mechanically, any state can be reached from any other state in a single step. The general kind of quantum computer should be programmed to perform distinctively quantum operations such as generating two bits in a superposition state. An appropriate measurement on the final superposed state of the computer produces a probabilistic behavior of the output, and because of this quantum parallelization does not reduce the average time required for parallelizable computation completion. The development of quantum computing science and technology as well as quantum computers as thinking machines is very dependent on different achievements of modern research in fundamental and applied physics as well as novel mathematical methods and tools.
Mutually Unbiased Bases in Composite DimensionsChris PompetzkiDecember 2025Fine. Here is the original with the ”proper” tone. Lame. Where’s the fun in that.Whatever. Oh how I much prefer people cite my version with the insufferable tone complete with Moby Dick, Shrek, and Drake references. What else would one expect when one man has done what others haven’t done for what 28+ years now in profound isolation. Though sure, I suppose I’ll do the ”right thing” and post my clean(er) version. Imagine my excitement at the notion of some stooges trying to steal my proof and act like they solved the problem when I actually did. Imagine even claiming it without citing me. Hehe. Oh I hope some do. I do not consent to any posting of this on the pathetic, outdated, obselete arXiv that apparently requires some kind of code to publish. We prove that the maximum number of mutually unbiased bases in dimension d is at most p + 1, where p is the smallest prime factor of d. The proof is three steps: (1) mutual unbiasedness forces bi-unimodularity of overlap functions, (2) bi-unimodularity factors through the Chinese Remainder Theorem to prime factors, (3) the Zp factor admits at most p 1 pairwise compatible bi-unimodular families. For d = 6, this gives M (6) = 3. Oh and by the way, yes I do declare that M (6) = 3 ought to be called the Pompetzki-Ahab-Shrek Theorem or something to that effect. Imagine the audacity of all the people who threw in the towel on M (6) = 3 trying to claim credit for what I, the absolute madman have done. Ha. Only a true psycho would stick with this problem for more than a day tops. Oh I know I ought to have ”proper” toned papers and go get a PhD in pure math apparently. Though then I’d have to do some BS that someone else wants me to do instead of doing what I want to do: brutally advancing mankind’s closure of open problems with all the ”Furor Teutonicus” of zee David Hilbert at least cubed hehe. Ja. Gut. You know vat. I zhought about giving zee Verldt zee fully clean und zee neutered und zee ”proper tone” und zhen I zaid NEIN! Ja. Gut. Vhy. Becauseit makes me smirks. Schadenfreude. That’s why.You know what. I just don't care enough to give it to the world fully clean. I must insist that I coat it with zee Scheisse ja. Zat iz vat is required after all zee Scheisse zat zee stupid have talked about the great German Mathematician, David Hilbert, who is sadly no longer with us. Imagine the extent of his fury at how much of the math world has thumbed their noses at him as they say to Hell with the notion that existence matters in math carry a moral imperative for mathematicians to resolve. I'm too furious. I'm too disgusted. The world didn't deserve David Hilbert. Nor Gauss. Nor Euler. Herr Hilbert said: Wir mussen wissen. Wir werden wissen.Many agreed when he was alive. Then he passed. Then people lost their fear of that Germanic fury. Then M(6) went unclosed for what 28+ years GTFO. There's no excuse for it. I'm furious.
Quantum Physics is defined as “the study of matter and energy at the most fundamental level”. It has entirely transformed our perspective of the physical world and is also the foundation of numerous technological advancements. More specifically, quantum mechanics has been applied in sectors such as medicine and biology, with quantum computing emerging as the most prominent among them. [5] The primary objective of this study is to analyse the concepts of quantum computing, focusing on what quantum computers are, how they function, as well as outline and explain the differences between them and standard computational models (classic computers). Furthermore, their relation to the laws of physics will be discussed. Secondarily, this article aims to provide recent achievements, such as existing quantum computers and plans concerning the future so as to underline the role quantum physics will play, shaping the frontier of computation.
Since its inception at the beginning of the twentieth century, quantum mechanics has challenged our conceptions of how the universe ought to work; however, the equations of quantum mechanics can be too computationally difficult to solve using existing computers for even modestly large systems. Here I will show that quantum computers can sometimes be used to address such problems and that quantum computer science can assign formal complexities to learning facts about nature. Hence, computer science should not only be regarded as an applied science; it is also of central importance to the foundations of science.