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

Skepticism of quantum computing

Scott Aaronson

Published Mar 14, 2013• 1 citation
Publisher

Abstract

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.

DOI
10.1017/cbo9780511979309.016

Related papers

Are Quantum States Exponentially Long Vectors?

Scott Aaronson

I'm grateful to Oded Goldreich for inviting me to the 2005 Oberwolfach Meeting on Complexity Theory. In this extended abstract, which is based on a talk that I gave there, I demonstrate that gratitude by explaining why Goldreich's views about quantum computing are wrong.

arXiv:quant-ph/0507242•Jul 26, 2005•11 citations

On Quantum Computation

Mika Hirvensalo

As early as 1982 Richard P. Feynman suggested that it might be impossible to simulate quantum mechanical phenomena with a computer without an exponential slowdown the efficiency of computation. He also proposed that this problem may be avoided by allowing the computer to run according to the laws of quantum mechanics, thus implicitely suggesting that a computer based on the quantum mechanical systems, a quantum computer, might have exponentially more computational efficiency than any classical one. A quantum mechanical phenomenon that never occurs classical physics and which actually makes quantum computation interesting and powerful, is the superposition of states, which, loosely speaking, means that instead of being totally one single state, a particle can be in between many states. Compare this to the elements of classical computer, bits. A bit takes values zero or one, but never anything between. In a quantum computer, one is able to store it both values simultaneously one quantum bit, equally weighted or not. Moreover, the classical computer one can store a number from zero to $2^n-1$ a register of length $n$, whereas, quantum computation, all the values could be stored simultaneously. The computation, which is performed via unitary transformations the state vector space, then applies to all these values simultaneously. Thus the power of the quantum computation lies not the absolute speed of the hypothetetical quantum computer but the possibility to actually follow many computational path simultaneously, as a nondeterministic automaton does. Alas, the observation of the outcome will yield only one value destroying the rest irreversibly. However, using a procedure smart enough one could obtain some valuable information about the computation.

•May 14, 1997•4 citations

Long-range interactions, weak magnetic fields amplification, and end states for quantum computing

Luka Trifunovic

It was Richard Feynman who first proposed, in 1982, the far-reaching concept of \na ”quantum computer”—a device more powerful than classical computers. The idea \nof a quantum computer is to employ the fascinating and often counterintuitive \nlaws of quantum mechanics to process information. It is far from obvious that \nthe proposed concept of a quantum computer is more powerful than its classical \ncounterpart, it was only in 1994 when Peter Shor theoretically demonstrated the \nexistence of a quantum algorithm for factorizing integers into prime factors \nthat runs in polynomial time unlike its classical counterpart which works in \nsub-exponential time. The factorization of integers into prime factors is the \nbasis of asymmetric cryptography. These early theoretical results lunched an \nimmense interest of the scientific community. Already during ’90s, the first \nproposals for the physical implementation of quantum computation emerged. Ever \nsince, many experimental groups around the world pursued different physical \nimplementations of quantum bits (qubits). The first decade of the new century \nsaw a steady improvement in the control and decoherence time (the time over \nwhich the information carried by the qubit is lost) for various qubits by many \norders of magnitude. The natural next step in this context is to answer the \nquestion of how to scale the system up to include many qubits and thus build a \nquantum computer? One of the main parts of this thesis addresses exactly this \nquestion, namely the question of architecture and scalability of future quantum \ncomputer. \n \nAmong various different physical realizations of qubits, the idea of using \nelectron spins trapped in electrostatic semiconductor quantum dots as the \nbuilding blocks of a quantum computer (the so-called spin qubits), put forward \nby Daniel Loss and David DiVincenzo in 1997, triggered tremendous interest in \nscientific community. Nevertheless, the implementation of the original \nLoss-DiVincenzo proposal posed a considerable technical challenge. It used \nquantum tunneling between qubits to enable their communication with each other, \nand thus required that the qubits to be placed very close to each other. This \nrequirement not only leaves little \nspace for the placement of the vast amount of gates and wirings needed to define \nthe electrostatic quantum dots, but also makes it challenging to control the \nlocal magnetic field needed for single-qubit operations. For these reasons, no \nsystem with more than a couple of spin qubits has been \nsuccessfully implemented thus far. In the first part of this thesis, we leap \nover this long-standing problem with an entirely different strategy of using \nmetallic floating gates or ferromagnets to couple together qubits that are \nseparated over a long distance. Our scheme works for any type of \nspin qubits, including the qubits based on nitrogen-vacancy center (NV-center) \nin diamond and technologically very important silicon qubits. \n \nThe main topic of this thesis is related to quantum computer. Still, quite \nunexpectedly, some of the ideas we employed in order to tackle the problem of \nquantum computer scalability can be utilized in a completely different field of \nresearch, namely, in the field of magnetic field sensing. Qubit are not only a \nnecessary ingredient of quantum computer but they also provide a way to measure \nvery accurately magnetic fields. The magnetometer build upon the qubit based on \nNV-center, so-called NV-magnetometer, emerged in recent years as most sensitive \nmagnetic moment sensor. These magnetometers are able to detect about hundred \nnuclear spins within a minute of acquisition time. In the second part of this \nthesis, we propose an entirely novel experimental realization of \nNV-magnetometers which increases present NV-center sensitivities by four orders \nof magnitude at room temperature. This unprecedented amplification of \nsensitivity will render magnetometers capable of detecting individual nuclear \nspins. This amplification is achieved by introducing a ferromagnetic particle \nbetween the nuclear spin that needs to be detected and the NV-magnetometer. Our \nsetup, in contrast to existing schemes, is particularly advantageous because, \ndue to the large amplification of sensitivity, the nuclear spin need not lie \nwithin a few nanometers of the surface but rather can be detectable at a \ndistance of 30 nm. With these novelties, our scheme provides chemically \nsensitive spin detection under ambient conditions allowing nanoscale resolution \nof nuclear magnetic moments in biological systems—the holy grail of nuclear \nmagneticresonance. \n \nIn the last part of the thesis we focus our attention to a new direction in \nquantum computer implementation that deals with topological quantum computer \nintroduced by Alexei Kitaev in 1997; in this approach the idea is to use \nquasiparticles with ”fractional” statistics and to perform the single- and \ntwo-qubit gates by merely exchanging these quasiparticles. Additionally, \ninformation in this system is stored non-locally thus it mitigates the problem \nof decoherence caused by local noise from the environment. Majorana fermions are \none of the most well known examples of such excitations. We analyze transport \nsignatures of different topological states in one-dimensional systems, like \nMajorana fermions and fractionally charged states. We envision an Aharonov-Bohm \nsetup wherein conductance measurement provides a clear signature of presence of \nfractionally charged fermionic states, since oscillations with double period \nemerge in this case. Additionally, we propose a very simple setup that enables \nexistence of degenerate mid-gap states, so-called Tamm-Shockley states that are \ncharacterized by fractional charge and discuss possible ways of detecting these \nstates experimentally. \n

•Jan 1, 2015•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

Quantum beauty: real and ideal

Frank A. Wilczek

© Darwin College, 2013. When I was asked to talk about quantum beauty I was a little startled, because the beauty of quantum theory is something that practising physicists, in the course of their work, rarely think about or mention. But when I gave the idea a chance, it really caught my imagination. And that’s why I’m here. Quantum beauty really is a wonderful, true thing to talk about. I’m going to sneak up on quantum beauty by putting it in historical context. The right context, I think, is a broader question: Does the world embody beautiful ideas? That is a question that people have thought about for a long time. Its intellectual history deserves volumes and syllabi. Here, though, I want to keep things brief and entertaining, so I shall spin a simple tale of heroes. Pythagoras and Plato intuited that the world should embody beautiful ideas; Newton and Maxwell demonstrated how the world could embody beautiful ideas, in specific impressive cases. Finally, in the twentieth century in modern physics, and especially in quantum physics, we find a definitive answer: Yes! - the world does embody beautiful ideas.

Cambridge University Press eBooks•May 23, 2013•0 citations

Ask the hard questions

F. Sullivan

For particular classes of problems that we can state as generalizations of finding the period of a discrete function or locating an item on a discrete list, quantum computing promises a dramatic speedup over classical machines. Quantum computing has had a stimulating effect on the theory of computing, generated some excellent thinking about the foundations of quantum mechanics, and justified some elegant experimental work in applied physics. But, as was probably inevitable, it also has generated some myths. I think the myths actually affect public perception of what's possible in computing technology and, by implication, can lead to wild overestimates of what to expect from computational science.

Computing in Science & Engineering•Oct 22, 2003•0 citations
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.
As early as 1982 Richard P. Feynman suggested that it might be impossible to simulate quantum mechanical phenomena with a computer without an exponential slowdown the efficiency of computation. He also proposed that this problem may be avoided by allowing the computer to run according to the laws of quantum mechanics, thus implicitely suggesting that a computer based on the quantum mechanical systems, a quantum computer, might have exponentially more computational efficiency than any classical one. A quantum mechanical phenomenon that never occurs classical physics and which actually makes quantum computation interesting and powerful, is the superposition of states, which, loosely speaking, means that instead of being totally one single state, a particle can be in between many states. Compare this to the elements of classical computer, bits. A bit takes values zero or one, but never anything between. In a quantum computer, one is able to store it both values simultaneously one quantum bit, equally weighted or not. Moreover, the classical computer one can store a number from zero to 2n−12^n-12n−1 a register of length nnn, whereas, quantum computation, all the values could be stored simultaneously. The computation, which is performed via unitary transformations the state vector space, then applies to all these values simultaneously. Thus the power of the quantum computation lies not the absolute speed of the hypothetetical quantum computer but the possibility to actually follow many computational path simultaneously, as a nondeterministic automaton does. Alas, the observation of the outcome will yield only one value destroying the rest irreversibly. However, using a procedure smart enough one could obtain some valuable information about the computation.
It was Richard Feynman who first proposed, in 1982, the far-reaching concept of \na ”quantum computer”—a device more powerful than classical computers. The idea \nof a quantum computer is to employ the fascinating and often counterintuitive \nlaws of quantum mechanics to process information. It is far from obvious that \nthe proposed concept of a quantum computer is more powerful than its classical \ncounterpart, it was only in 1994 when Peter Shor theoretically demonstrated the \nexistence of a quantum algorithm for factorizing integers into prime factors \nthat runs in polynomial time unlike its classical counterpart which works in \nsub-exponential time. The factorization of integers into prime factors is the \nbasis of asymmetric cryptography. These early theoretical results lunched an \nimmense interest of the scientific community. Already during ’90s, the first \nproposals for the physical implementation of quantum computation emerged. Ever \nsince, many experimental groups around the world pursued different physical \nimplementations of quantum bits (qubits). The first decade of the new century \nsaw a steady improvement in the control and decoherence time (the time over \nwhich the information carried by the qubit is lost) for various qubits by many \norders of magnitude. The natural next step in this context is to answer the \nquestion of how to scale the system up to include many qubits and thus build a \nquantum computer? One of the main parts of this thesis addresses exactly this \nquestion, namely the question of architecture and scalability of future quantum \ncomputer. \n \nAmong various different physical realizations of qubits, the idea of using \nelectron spins trapped in electrostatic semiconductor quantum dots as the \nbuilding blocks of a quantum computer (the so-called spin qubits), put forward \nby Daniel Loss and David DiVincenzo in 1997, triggered tremendous interest in \nscientific community. Nevertheless, the implementation of the original \nLoss-DiVincenzo proposal posed a considerable technical challenge. It used \nquantum tunneling between qubits to enable their communication with each other, \nand thus required that the qubits to be placed very close to each other. This \nrequirement not only leaves little \nspace for the placement of the vast amount of gates and wirings needed to define \nthe electrostatic quantum dots, but also makes it challenging to control the \nlocal magnetic field needed for single-qubit operations. For these reasons, no \nsystem with more than a couple of spin qubits has been \nsuccessfully implemented thus far. In the first part of this thesis, we leap \nover this long-standing problem with an entirely different strategy of using \nmetallic floating gates or ferromagnets to couple together qubits that are \nseparated over a long distance. Our scheme works for any type of \nspin qubits, including the qubits based on nitrogen-vacancy center (NV-center) \nin diamond and technologically very important silicon qubits. \n \nThe main topic of this thesis is related to quantum computer. Still, quite \nunexpectedly, some of the ideas we employed in order to tackle the problem of \nquantum computer scalability can be utilized in a completely different field of \nresearch, namely, in the field of magnetic field sensing. Qubit are not only a \nnecessary ingredient of quantum computer but they also provide a way to measure \nvery accurately magnetic fields. The magnetometer build upon the qubit based on \nNV-center, so-called NV-magnetometer, emerged in recent years as most sensitive \nmagnetic moment sensor. These magnetometers are able to detect about hundred \nnuclear spins within a minute of acquisition time. In the second part of this \nthesis, we propose an entirely novel experimental realization of \nNV-magnetometers which increases present NV-center sensitivities by four orders \nof magnitude at room temperature. This unprecedented amplification of \nsensitivity will render magnetometers capable of detecting individual nuclear \nspins. This amplification is achieved by introducing a ferromagnetic particle \nbetween the nuclear spin that needs to be detected and the NV-magnetometer. Our \nsetup, in contrast to existing schemes, is particularly advantageous because, \ndue to the large amplification of sensitivity, the nuclear spin need not lie \nwithin a few nanometers of the surface but rather can be detectable at a \ndistance of 30 nm. With these novelties, our scheme provides chemically \nsensitive spin detection under ambient conditions allowing nanoscale resolution \nof nuclear magnetic moments in biological systems—the holy grail of nuclear \nmagneticresonance. \n \nIn the last part of the thesis we focus our attention to a new direction in \nquantum computer implementation that deals with topological quantum computer \nintroduced by Alexei Kitaev in 1997; in this approach the idea is to use \nquasiparticles with ”fractional” statistics and to perform the single- and \ntwo-qubit gates by merely exchanging these quasiparticles. Additionally, \ninformation in this system is stored non-locally thus it mitigates the problem \nof decoherence caused by local noise from the environment. Majorana fermions are \none of the most well known examples of such excitations. We analyze transport \nsignatures of different topological states in one-dimensional systems, like \nMajorana fermions and fractionally charged states. We envision an Aharonov-Bohm \nsetup wherein conductance measurement provides a clear signature of presence of \nfractionally charged fermionic states, since oscillations with double period \nemerge in this case. Additionally, we propose a very simple setup that enables \nexistence of degenerate mid-gap states, so-called Tamm-Shockley states that are \ncharacterized by fractional charge and discuss possible ways of detecting these \nstates experimentally. \n
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.
© Darwin College, 2013. When I was asked to talk about quantum beauty I was a little startled, because the beauty of quantum theory is something that practising physicists, in the course of their work, rarely think about or mention. But when I gave the idea a chance, it really caught my imagination. And that’s why I’m here. Quantum beauty really is a wonderful, true thing to talk about. I’m going to sneak up on quantum beauty by putting it in historical context. The right context, I think, is a broader question: Does the world embody beautiful ideas? That is a question that people have thought about for a long time. Its intellectual history deserves volumes and syllabi. Here, though, I want to keep things brief and entertaining, so I shall spin a simple tale of heroes. Pythagoras and Plato intuited that the world should embody beautiful ideas; Newton and Maxwell demonstrated how the world could embody beautiful ideas, in specific impressive cases. Finally, in the twentieth century in modern physics, and especially in quantum physics, we find a definitive answer: Yes! - the world does embody beautiful ideas.
For particular classes of problems that we can state as generalizations of finding the period of a discrete function or locating an item on a discrete list, quantum computing promises a dramatic speedup over classical machines. Quantum computing has had a stimulating effect on the theory of computing, generated some excellent thinking about the foundations of quantum mechanics, and justified some elegant experimental work in applied physics. But, as was probably inevitable, it also has generated some myths. I think the myths actually affect public perception of what's possible in computing technology and, by implication, can lead to wild overestimates of what to expect from computational science.