Quantum Supersampling [video]
machinelevel.com
machinelevel.com
The one thing that bothered me, in the whole talk, is when he said that a 10-qubit circuit was beyond anything we could run right now. Simulators like Liquid [1] or even my browser-drag-and-drop toy Quirk [2] would easily run that circuit. In hindsight it's obvious that he meant on an actual quantum computer.
Sure, 10 qubits happen to be doable on an classical computer, but the classical resource requirements for simulating quantum bits grow exponentially, so 40 qubits is about where even super computing clusters stop being useful and 100 qubits is beyond the capabilities of any classical computer you can fit on Earth.
http://www.dwavesys.com/press-releases/d-wave-systems-breaks...
I think getting to fifty proper qubits will be a much bigger deal than D-Wave getting to even ten thousand "qubits". But I suppose time will tell.
There is no consensus whether D-Wave actually provides clear quantum speedup or not.
Rønnow TF, Troyer M, Wang Z, Job J, Boixo S, Isakov SJ, Wecker D, Martinis JM: Defining and detecting quantum speedup, Science, 19 June 2014, http://science.sciencemag.org/content/345/6195/420 doi:10.1126/science.1252319
Adiabatic quantum computation is equivalent to other models of quantum computing (e.g. the circuit model). It has all the power expected from a quantum computer.
D-Wave do some form of annealing that can be simulated classically in a fairly efficient manner.
Other random questions, is there a feeling for when they'd be useful? A 5 qubit processor isn't really useful for much, but is a 10? Do they suddenly go from not-useful to "wow" very quickly as we scale up?
Is there something everyone is waiting to hit, like a "once we reach about X qubits we'll be able to do Y which was totally infeasible before", or is it a bit early for that?
How difficult it is to scale the simulation of N qubits? Naively you need a list of 2^N complex numbers to represent the state of N qubits. So, naively, adding one qubit to the simulation makes it a factor of 2 more difficult. This is not exact but it is a good enough intuition. (However, it is only a conjecture that quantum computers are more powerful than classical ones, even if it conjecture as strongly believed as NP!=P).
How difficult it is to make a quantum computer of N+1 qubits when you have already built a computer of N qubits? Today my biased opinion would be to say that it takes a few years to create something reliable with one more qubit than the current state of the art (which is about 5). People are actively working on methods that would scale better (until then it is just scientists playing with cool hardware, but nothing practical).
As to how many qubits we need to do something practical. To factor a thousand bit number in its prime factors you will need a few thousand qubits. But you will need to implement error correcting codes (qubits are unreliable so you encode one "logical" qubit redundantly in multiple "physical" qubits). If you count the physical qubits, you will need a few million. Currently we do not have machines that reliably work on more than 10ish.
But another active field of research is "shallow depth circuits". Those are simple non-universal quantum circuits that require just a few qubits but do things that can not be done on classical computers efficiently. An example might be the Quantum Approximate Optimization Algorithm which for a few months was the most efficient way to find approximate solutions to NP-complete problems of certain type (until we found a better classical approach). But I would like to stress that those are not universal quantum computers.
Regarding this one: You're exactly right that simulators can handle pretty complex circuits; my sim used in the video, QCEngine [1] will handle up to 28 qubits in a browser for full simulation, or many thousands for the subset of operations known as the "Clifford Group".
When I started scaling down things to run them, it was on actual hardware. Most hardware requires several 'physical' qubits to implement each 'logical' qubit. For example, the photonic chip I showed generated 4 entangled qubits, but the program I ran with it just has 2. It's using something called 'Measurement-based QC', whic destroys the working qubits as the program goes on. Anyway, the hardware's getting much better, and I expect to see photonic devices with many qubits in the near future.
Strilanc, your Quirk sim is amazing. It's fun and easy to use, and the tooltips on the instructions are awesome. The circle notation made me smile, as that's the way I visualize this stuff, even on graph paper.
A while ago I made some side-by-side notes on QCEngine and Liquid, as each is the right tool for a different job. You can see that here [2].
1: http://qcengine.com 2: http://machinelevel.com/qc/bristol/liquid_samples.html
is there a good introductory material for writing code for quantum computers and how quantum computers work?
also is there a way to evaluate the performance boost with the simulator?
But I guess you were specifically interested in how to write those black box library routines that work on the (currently imaginary) quantum hardware you attached to your classical computer.
There are two sides to this question:
1) You are interested in the physical system (compared to having interest in electronics in the case of classical computers). Then you have to learn the physics - what wavelength of laser you shine at your ion trap; what microwave signal you send to your superconducting cavity; how to focus your laser on the NV center in your diamond crystal, etc. Regrettably, I do not have better resource for this beyond just looking at review articles in Science and Nature (it is a very young and very active research area). You will need to learn the basic physics before doing that. This book [1] is the canonical resource for that field.
2) You are interested in the computer science (compared to studying Turing Machines and designing algorithms in the case of classical computers). For this I would point to Scott Aaronson's blog, his MIT lecture notes, and his books (and papers that he has aimed at the general public).
[1]: http://www.cambridge.org/us/academic/subjects/physics/quantu...
P.S. My points is, quantum computers are special purpose add-ons that solve very specific problems more efficiently than classical computers. For all classically easy problems (all problems in P) solving them on a classical computer will be faster, simply because building a classical computer is so much easier.
i think referring to it as a lookup table is self confounding
the whole thing still regretfully relies on the random
periodicity is the way to go but periodicity in place of the look up table
i was stunned to see the graph at 19:53
to come by that graph through such a probabilistic method is validating
those etched silicon photonic quantum gates shown following 23:14 are awesome
the variable temperature controlled index of refraction phase operation reminded me of a previous link using optics to solve np-complete problems(o) and someone compared it to a sleep sort
when he put up the results at 22:14 comparing with monte carlo i wondered what the time difference was for each calculated result
i understand that energy requirements for the kind of state control necessary, like the low temperatures, the 2 degree kelvin quoted at 26:53, for single infared photon detection, make these physical quantum computers impractical when compared to classical computations like the monte carlo example.. he also talks a bit about decoherence issues as an unfortunate race saying 'so long to finish the program' how long is so long?
though the clear consistency between the classical and physical quantum computer results is definitely more than 'almost interesting' i do wonder about what time was spent to get each result.. the goal is to optimise for speed, right?
the simulator(i) is really cool
What is supposed to be interesting about the result at 15:15? As far as I can tell, the shader contains all the information that is presented as the output here, so it doesn't seem impressive. But he says "our calculation produced the complete answer perfectly with zero noise" as if this is a serious accomplishment? I don't get it.
and yes, you are right, in terms of relying solely on the simulation, this is hardly a 'serious accomplishment' because it relies on many classical computations to simulate
but rather it is the shaders and their use that are the accomplishment
the simulation is only a test bed to investigate the practicality of these shaders before placing them into a real quantum computer
since working directly with quantum computers currently is both difficult and limiting you are better off with a computation heavy simulation to try out ideas to determine which ones have the greatest potential for successful results
imagine prototyping on a device that needs to remain at 17millikelvin
for instance, the author states it took some time before realising an inverted fourier transform was necessary to achieve these results, even noting almost giving up on the whole thing as a result of the constant failings while using the original idea of a forward fourier transform
could such a revelation had been made using the actual quantum hardware? sure.. maybe, but the probability, ;p, is much much lower
with the quantum computer you can think of the parallel computations in terms of a single classical computation
so the computation heavy simulation shows that "our calculation produced the complete answer perfectly with zero noise" which is encouraging that if placed into a real quantum computer, as is shown later in the video, we can get zero noise results with essentially a single computation
when placed into the real quantum computer the results still retain some noise due the limitations of current real quantum computers because they had to detrimentally limit their qubit use.. further exemplifying the importance of the simulator
but given a quantum computer that can perform using the same number of qubits as the simulation these shaders should give zero noise results which would be a serious accomplishment
.. is there a word for 'theoretically based on simulation'? simulationally theoretic? ;p