As a software engineer looking for a highly marketable and differentiated skill set, given your projections for quantum computing roadmap, when should I start exploring this area? (or: when should I start writing code and doing side projects)
I like to use the analogy. Adding 1 GB of RAM these days isn't that big of a deal. You can maybe open two more tabs in Chrome. :) Adding 1 giga-qubit to your computer would make it 4.6 x 10^301029995 times better. That's unimaginably more powerful than anything any human can think of.
We don't have quantum software engineering figured out. And it's not going to be figured out by a few academics, although they may lay some good foundations. It's going to be figured out by the same folks who figured out traditional computing: people who try stuff, break stuff, and experiment.
Quantum computation is such a new and different computing paradigm, that whoever is prepared will be able to reap the benefits much earlier. And, if the promises of scaling are true (they are from a fundamental physics standpoint), such companies will propel themselves far ahead of the competition.
I would say that, in the current stage of development of quantum software and hardware, even a seasoned software professional will not—on short order—be able to apply the tools directly to their problems. As a programming language enthusiast, it's like taking a long-time K&R C programmer, and asking them to be productive in Agda. It's not that they can't, but they probably won't be able to do it by tomorrow. It'll take time, energy, and investment to think in new ways.
I personally believe that commercialization will become more and more apparent when services are accelerated by quantum computation. But how many people are going to share that secret sauce?
Is that feasible? Is it desirable?
I said in another comment that I think the best thing we can do is get quantum devices in the hands of people and let them play. Unfortunately, for a long time, quantum computers and their programming have been so utterly out-of-reach and opaque that that has been difficult. Now I think we are taking good steps to opening the possibility of experimentation up.
The difference though, is that I only needed to understand there was a container of multiple items in FORTH and Lisp. For basic element manipulation, I needed to understand matrices.
At this rate, it would take hours before I understand how to write a basic program. And my trailblazer sense is already tingling (that I should let others be pioneers).
Normally I'd just resume lurker mode at this point, but my interest in combinatorics is driving my curiosity towards understanding what might be possible.
I hope we (both Rigetti and the quantum computing community at large) can continue to refine and simplify the concepts at hand.
What you're ignoring with your exponential growth argument is that it is also exponentially harder to add one qubit while maintaining usefulness (i.e. long decoherence times).
I'd say, anyone who doesn't want to work either in academia or on "vanity projects" like D-Wave's much-hyped collabs with Lockheed, Google etc. should wait half a decade and see.
[1] Arguably the D-Wave machines are faster than a human, but we don't have evidence (yet) that it's not just a fancy annealing ASIC.
I do disagree that it is exponentially more difficult to add a qubit. Coherence times are something to optimize, and densely packing qubits is also difficult with coherence times, but the notion of adding a qubit to a system doesn't come with an inherent exponential difficulty.
Regarding whether it is useful or not to learn quantum computing for your profession, if it's true that systems can be built that grow with exponential power, then they'll be relevant faster than one might think.
Or is that an oversimplified view?
Architectures with higher two-qubit connectivity is merely an optimization.
It's less "please beat a $20000 server stuffed with GPU accelerators" and more "please beat a 6502, or to start with at least an abacus".
The problem is that everything is so toy-level so far that it's not even in the category of "computation tool".
There's a reason we work on it, though, and that's because of two reasons: (1) our current and insofar accurate understanding of physics says with certainty that a quantum computing device is superior to its classical counterpart, and (2) while the problem is not easy, there seems to be just the right number of engineering problems (signal integrity, signal routing, superconducting non-magnetic fab, etc.) in our way that we feel we can tackle them in a timely manner. Rigetti in particular is a company that believes that having a full stack team will allow these interdisciplinary problems to be solved faster.
No one, on our team at least, is disillusioned about where we are. As the article says, 8 qubit chips are in the final phases of validation. As I say, 8 qubit chips are simulatable faster on your shiny Intel chip. Does that mean the entire enterprise is useless? No. It is a stepping stone for a company that has raised less money than many CoolNewLikeUberButForX apps you see pop up here. I find that unimaginably remarkable.
When I answer questions about quantum computing, however, I want to share my and others' visions about it based off of what we know, in a relatively accurate fashion, that is understandable by a general audience.
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].
This is not disagreed by experts in the field of quantum computing, including Scott.
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.
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/
[2]: https://en.wikipedia.org/wiki/Time_complexity#Superpolynomia...
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.
From a purely personal perspective, I do think that it is very interesting that we can affect the entirety of a state with an otherwise linear number of physical operations. Whether that is useful in providing lots of exponential or even polynomial speedups in the arena of practical algorithms is yet to be determined. I suspect that with a robust enough computer, the answer will be a resounding "yes".
This is true, but a single state in a classical probability distribution is not exponentially large. Because of superposition, a single quantum state can be associated with an exponentially large number of amplitudes. As you mentioned, quantum algorithms rely on the interference of these amplitudes. However, if you could somehow assign a complex amplitude to each state in a classical probability distribution, you would still be limited to manipulating only one amplitude at a time. It is in this sense that the exponential scaling is important.
> 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 didn't mean to imply that all quantum algorithms have superpolynomial speedups. But (especially) for the ones that do, I about the exponentially large set of amplitudes being manipulated in parallel.
> 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".
100% agreed.
> However, if you could somehow assign a complex amplitude to each state in a classical probability distribution, you would still be limited to manipulating only one amplitude at a time.
This is probably just more confusing. What I should say is that classical probabilities have no physical manifestation that you can directly manipulate - they just denote our lack of information about a system. Amplitudes in quantum systems can be related to probabilities, but they don't represent lack of information. The probabilistic nature of quantum systems is deeper than that: measurements project superposition states onto classical states in a probabilistic way. This is
For exponentially large superposition states, there are an exponential number of amplitudes. When we act on the state in certain ways, we update all of the amplitudes in parallel. There is no counterpart to this when acting on classical states, even when you have incomplete information about the state (and thus an exponentially large probability distribution).
> But (especially) for the ones that do, I about the exponentially large set of amplitudes being manipulated in parallel.
Let's try again.
> However, if you could somehow assign a complex amplitude to each state in a classical probability distribution, you would still be limited to manipulating only one amplitude at a time.
This is probably just more confusing. What I should say is that classical probabilities have no physical manifestation that you can directly manipulate - they just denote our lack of information about a system. Amplitudes in quantum systems can be related to probabilities, but they don't represent lack of information. The probabilistic nature of quantum systems is deeper than that: measurements project superposition states onto classical states in a probabilistic way. But before this projection, we're forced to say that the physical state of the system is in superposition. Even more, the amplitudes accociated with each part of the superposition state are part of the physical definition of the state. In this sense, they are more "real" than classical probabilities.
For exponentially large superposition states, there are an exponential number of amplitudes. When we act on the state in certain ways, we update all of the amplitudes in parallel. There is no counterpart to this when acting on classical states, including when you have incomplete information about the state (and thus an exponentially large probability distribution).
> But (especially) for the ones that do, I about the exponentially large set of amplitudes being manipulated in parallel.
Let me try again. The built-in exponential in the physical state (as I described above) helps me see how quantum speedups (especially super-polynomial ones) could even be possible. You're right that there's more to the story than just having an exponentially large number of amplitudes, but it's an important part of the story!
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.
That's not true and you should know better. For example, there are very few problem for which quantum computers are known to perform better than standard computers.
Of course, I am saying "mathematical entities", and almost all practitioners of quantum computing are aware of the challenge to actually build them.