6 ms·

> Now. "Exponential" is faster than most people, including myself, can believe. When one unit of resource doubles your computational capacity, it doesn't take m

> Now. "Exponential" is faster than most people, including myself, can believe. When one unit of resource doubles your computational capacity, it doesn't take many units. Please don't make bullshit claims about exponential speedups. I don't know exactly what technology you are claiming to have, but statements like this cause me to believe less in your technology, not more. We've been through the cycle of unfounded hype many times (with D-WAVE and others). Scott Aaronson has an entire category on his blog filled with depressingly many posts debunking the same bullshit over and over [0]. [0] http://www.scottaaronson.com/blog/?cat=17 http://www.scottaaronson.com/blog/?cat=17

reikonomusha 9y ago
The size of the state space in which the qubits live is exponential in the number of qubits. This is because the qubits live in an n-fold tensor product of two-dimensional Hilbert spaces. Performing an operation on a single qubit is the same as performing a 2^n-dimensional unitary transformation on the state of the system. This is not disagreed by experts in the field of quantum computing, including Scott.
- petters 9y ago
  But you said "When one unit of resource doubles your computational capacity" which I believe is what your parent comment rightly called bullshit.
- algorias 9y ago
  I know what a Hilbert space is, and I also know that this 2^n-dimensional space cannot be accessed except through a destructive measurement operation. An exponential state space does not imply that there is exponential computing power to be harnessed there. As an analogy, when you execute a randomized classical algorithm, the size of the state space in which the bits live is also exponential (and at the end you observe the result, and your uncertainty collapses from a probability distribution to one of its possible outcomes). Yet you would look at me like I'm crazy (or a fraud) if I claimed that randomized algorithms have exponentially more computing power than deterministic ones. The only way in which the quantum case differs from the classical picture above, is that amplitudes have a phase and can thus interfere (constructively or destructively). The art of creating quantum algorithm lies entirely in orchestrating favorable interference patterns.
  - goldenkey 9y ago
    The way I like to explain it simply to people is that right now, you can use frameworks to manipulate probability distributions. Quantum logic gates are basically a restriction on the operations you can use to combine pdf functions. Ultimately, unless you can find a clever way to convert an algorithm into one that uses pdfs and then achieves a pdf where one single value has 99% of the EV, QM aint gonna help ya.
  - dangirsh 9y ago
    It seems like we should be more careful when saying "exponential" increase in computational performance. For many quantum algorithms, the speedup is actually superpolynomial [1] [2]. In some sense, this is due to the fact that the state space grows exponentially but, as you correctly pointed out, it can only be accessed in a destructive manner. For many algorithms (e.g. Shor's), the net result is a superpolynomial improvement in the resources required for solving a practically important problem (factoring). Unfortunately, the nuance of superpolynomial vs exponential is lost in many high-level discussions about quantum computing. Maybe we should just say "much, much faster" ;) To make matters worse, quantum computing textbooks often present Simon's Problem [3] as a showcase for truly exponential speedup. It turns out this is misleading, as I've never heard of a practically relevant algorithm with truly exponential speedup. [1]: http://math.nist.gov/quantum/zoo/ http://math.nist.gov/quantum/zoo/ [2]: https://en.wikipedia.org/wiki/Time_complexity#Superpolynomial_time https://en.wikipedia.org/wiki/Time_complexity#Superpolynomia... [3]: https://en.wikipedia.org/wiki/Simon%27s_problem https://en.wikipedia.org/wiki/Simon%27s_problem
    - algorias 9y ago
      > In some sense, this is due to the fact that the state space grows exponentially What I take issue with is precisely the conflation of the size of the state space with the quantum speedup. Shor's algorithm is fast because QFT (quantum fourier transform) creates an interference pattern that can reveal the period of certain functions, and QFT can be implemented efficiently because of its specific structure. As I said before, the size of a classical state space of a probability distribution is also exponentially large, so no, the root cause is emphatically not the size of the state space, but the way in which that space can be manipulated and the fact that amplitudes add up in a way that's not linear (when looking at the resulting probabilities). Note that Grover's algorithm achieves only a quadratic speedup with the same size of state space as Shor's. Your explanation doesn't add up, it just adds to the confusion. I just think that it's very important to stay far away from the (wrong, but pervasive in pop science) idea that quantum computers are fast because they "try exponentially many solutions in parallel". Excessively highlighting the size of the state space is already a step too far in that direction for my taste. My words are a bit harsh, but I do appreciate the fact that you are engaging honestly, and please don't take my skepticism personally. I would like to hear what your technology brings to the table, how it differs from competing approaches, etc.
codekilla 9y ago
The simplest quantum algorithm shows an exponential speedup over the best classical solution, this, of course, is the toy example often used in QC texts of determining whether or not a function is constant or balanced(Deutsch). But, as John Preskill points out...this is not even the really interesting thing here. Quantum simulation actually lies outside the class of NP, because there is no efficient way to verify the solution of such a simulation. This area is where quantum computers, in my opinion, are the most interesting, we will be able to do things we simply cannot on a classical computer....and for the record..most people commenting should know that D-WAVE operates using the Adiabatic model, and is not a universal quantum computer.

reikonomusha 9y ago

The size of the state space in which the qubits live is exponential in the number of qubits. This is because the qubits live in an n-fold tensor product of two-dimensional Hilbert spaces. Performing an operation on a single qubit is the same as performing a 2^n-dimensional unitary transformation on the state of the system. This is not disagreed by experts in the field of quantum computing, including Scott.

petters 9y ago
But you said "When one unit of resource doubles your computational capacity" which I believe is what your parent comment rightly called bullshit.
algorias 9y ago
I know what a Hilbert space is, and I also know that this 2^n-dimensional space cannot be accessed except through a destructive measurement operation. An exponential state space does not imply that there is exponential computing power to be harnessed there. As an analogy, when you execute a randomized classical algorithm, the size of the state space in which the bits live is also exponential (and at the end you observe the result, and your uncertainty collapses from a probability distribution to one of its possible outcomes). Yet you would look at me like I'm crazy (or a fraud) if I claimed that randomized algorithms have exponentially more computing power than deterministic ones. The only way in which the quantum case differs from the classical picture above, is that amplitudes have a phase and can thus interfere (constructively or destructively). The art of creating quantum algorithm lies entirely in orchestrating favorable interference patterns.
- goldenkey 9y ago
  The way I like to explain it simply to people is that right now, you can use frameworks to manipulate probability distributions. Quantum logic gates are basically a restriction on the operations you can use to combine pdf functions. Ultimately, unless you can find a clever way to convert an algorithm into one that uses pdfs and then achieves a pdf where one single value has 99% of the EV, QM aint gonna help ya.
- dangirsh 9y ago
  It seems like we should be more careful when saying "exponential" increase in computational performance. For many quantum algorithms, the speedup is actually superpolynomial [1] [2]. In some sense, this is due to the fact that the state space grows exponentially but, as you correctly pointed out, it can only be accessed in a destructive manner. For many algorithms (e.g. Shor's), the net result is a superpolynomial improvement in the resources required for solving a practically important problem (factoring). Unfortunately, the nuance of superpolynomial vs exponential is lost in many high-level discussions about quantum computing. Maybe we should just say "much, much faster" ;) To make matters worse, quantum computing textbooks often present Simon's Problem [3] as a showcase for truly exponential speedup. It turns out this is misleading, as I've never heard of a practically relevant algorithm with truly exponential speedup. [1]: http://math.nist.gov/quantum/zoo/ http://math.nist.gov/quantum/zoo/ [2]: https://en.wikipedia.org/wiki/Time_complexity#Superpolynomial_time https://en.wikipedia.org/wiki/Time_complexity#Superpolynomia... [3]: https://en.wikipedia.org/wiki/Simon%27s_problem https://en.wikipedia.org/wiki/Simon%27s_problem
  - algorias 9y ago
    > In some sense, this is due to the fact that the state space grows exponentially What I take issue with is precisely the conflation of the size of the state space with the quantum speedup. Shor's algorithm is fast because QFT (quantum fourier transform) creates an interference pattern that can reveal the period of certain functions, and QFT can be implemented efficiently because of its specific structure. As I said before, the size of a classical state space of a probability distribution is also exponentially large, so no, the root cause is emphatically not the size of the state space, but the way in which that space can be manipulated and the fact that amplitudes add up in a way that's not linear (when looking at the resulting probabilities). Note that Grover's algorithm achieves only a quadratic speedup with the same size of state space as Shor's. Your explanation doesn't add up, it just adds to the confusion. I just think that it's very important to stay far away from the (wrong, but pervasive in pop science) idea that quantum computers are fast because they "try exponentially many solutions in parallel". Excessively highlighting the size of the state space is already a step too far in that direction for my taste. My words are a bit harsh, but I do appreciate the fact that you are engaging honestly, and please don't take my skepticism personally. I would like to hear what your technology brings to the table, how it differs from competing approaches, etc.

codekilla 9y ago

The simplest quantum algorithm shows an exponential speedup over the best classical solution, this, of course, is the toy example often used in QC texts of determining whether or not a function is constant or balanced(Deutsch). But, as John Preskill points out...this is not even the really interesting thing here. Quantum simulation actually lies outside the class of NP, because there is no efficient way to verify the solution of such a simulation. This area is where quantum computers, in my opinion, are the most interesting, we will be able to do things we simply cannot on a classical computer....and for the record..most people commenting should know that D-WAVE operates using the Adiabatic model, and is not a universal quantum computer.