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)
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.
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.
I disagree. Through Scott Aaronson's writings, I gather we still don't have conclusive evidence [1] that anyone's built an actual quantum computer capable of more sophisticated computations than a human 10-year-old can do with pen and paper, and furthermore that it's not clear we'll be able to build such a machine in our lifetimes. I'm not saying it's impossible, but we know it's going to be really hard.
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 not dispute the claim about the existence of a quantum computer which surpasses its classical brethren. Scott is correct.
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.
Again, I do not dispute this claim and also do not see it as a problem. Folks working on it, including myself, would like to see it as a viable replacement for any computational device. And it's not, right now.
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.
They do not all need to interact directly with one another. You can create full entanglement even if they linearly interact. It just means you pay a penalty in the compilation of your program.
Architectures with higher two-qubit connectivity is merely an optimization.
> 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].
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.
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.
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.
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.
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.
> 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.
I am in agreement with your sentiment here. Adding a qubit does not mean that every single thing you do on a quantum computer doubles in speed, which is a possible way to interpret some of my statements.
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".
> As I said before, the size of a classical state space of a probability distribution is also exponentially large...
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".
> 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.
> 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!
> 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
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.
It is true that I am not being mathematically precise in my statements. The precise way to say what I said is: In order to represent completely an arbitrary state in the space of one billion qubits, you will need a number of bytes exponential in that number of qubits. If we have, as mathematical entities, one billion additional qubits, this will be equivalent to increasing the dimension of our existing system by 2^(1 billion) times.
Of course, I am saying "mathematical entities", and almost all practitioners of quantum computing are aware of the challenge to actually build them.
There are lots of "checkpoints" one can imagine with the commercialization of a technology. Right now, large industry players, whose survival depends on their tech strategy, are investing in quantum computer R&D. I don't mean that these companies are themselves trying to build quantum computers, but they are interested in applying them to their hardest technical problems.
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?
That's my goal! It is desirable, and I think it is feasible.
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.
Just to give you an idea, I've spent about 30-45 minutes reading over various materials (the Github links). I think my level of knowledge would be equivalent of understanding how dup, drop, and rot work in FORTH (or car and cdr in Lisp)... Basic element manipulation (bit/qubit, stack, and list).
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 admit it is an unusually larger leap to get to anything useful. We have been blessed to have such a fantastic and intuitive understanding of classical computing. We can pick up most new programming languages gradually and efficiently. When the fundamental object of manipulation is this wacky thing called a "state vector in 2^n dimensional Hilbert space" as opposed to "a bag of bits", and operations must be reversible, and ... and ... and ..., things are just harder.
I hope we (both Rigetti and the quantum computing community at large) can continue to refine and simplify the concepts at hand.
Unlike adding RAM, adding each extra qubit is also exponentially harder, since maintaining coherence of all the qubits becomes more and more difficult. That's why scaling from the tiny quantum computers we have today (which are not useful) to a useful quantum computer remains a decades long research agenda.
