4 ms·

This is a great talk. Like, I am going to be linking people to this for years. It mentions the basics, goes over an example use, and just generally has the perf

This is a great talk. Like, I am going to be linking people to this for years. It mentions the basics, goes over an example use, and just generally has the perfect amount of "this could be cool". 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. 1: http://stationq.github.io/Liquid/ http://stationq.github.io/Liquid/ 2: http://algorithmicassertions.com/quirk http://algorithmicassertions.com/quirk

krastanov 10y ago
You probably already know that, but to clarify for other readers: 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.
- matt42 10y ago
  I do not know anything in quantum computing but I read that D-Wave already reached 1000 qubits. Does it mean that their computer is already more powerful that any classical super computer ? http://www.dwavesys.com/press-releases/d-wave-systems-breaks-1000-qubit-quantum-computing-barrier http://www.dwavesys.com/press-releases/d-wave-systems-breaks...
  - Strilanc 10y ago
    It's not the same kind of quantum computer. D-Wave makes an annealer. They also have a history of making grandiose claims. 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.
    - matt42 10y ago
      There is a very good visual explanation of the difference bettween quantum annealer and univeral quantum computer: https://www.youtube.com/watch?v=zvfkXjzzYOo https://www.youtube.com/watch?v=zvfkXjzzYOo
  - nabla9 10y ago
    D-Wave is doing adiabatic quantum computation. It's quantum analog computer. Comparable classical electric analog computers were last used in 50s or 60s. 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 http://science.sciencemag.org/content/345/6195/420 doi:10.1126/science.1252319
    - krastanov 10y ago
      Slight correction: D-Wave are most definitely not doing "adiabatic quantum computation". They occasionally have claimed that in the past, but not anymore. 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.
- IanCal 10y ago
  Is there an expectation of how hard it'll be to scale up the number of qubits? As in, do we think it'll be 10 times as hard each time we add another qubit, or that once we've got the stability sorted going from 5 to 10 to 50 to 100 is more a case of just building a bigger version? 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?
  - krastanov 10y ago
    Depends on what exactly you are asking: 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.
machinelevel 10y ago
Hi there! This thread makes me so happy. I posted the Quantum Supersampling video and then went on vacation for a week, and while I was out a colleague sent me this link. Thanks for your kind words; they made my day. The thoughtful smart discussion going on here is exactly what I was hoping would happen. I'll post answers (as well as I can) to the items here as time permits. 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 http://qcengine.com 2: http://machinelevel.com/qc/bristol/liquid_samples.html http://machinelevel.com/qc/bristol/liquid_samples.html

krastanov 10y ago

You probably already know that, but to clarify for other readers: 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.

matt42 10y ago
I do not know anything in quantum computing but I read that D-Wave already reached 1000 qubits. Does it mean that their computer is already more powerful that any classical super computer ? http://www.dwavesys.com/press-releases/d-wave-systems-breaks-1000-qubit-quantum-computing-barrier http://www.dwavesys.com/press-releases/d-wave-systems-breaks...
- Strilanc 10y ago
  It's not the same kind of quantum computer. D-Wave makes an annealer. They also have a history of making grandiose claims. 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.
  - matt42 10y ago
    There is a very good visual explanation of the difference bettween quantum annealer and univeral quantum computer: https://www.youtube.com/watch?v=zvfkXjzzYOo https://www.youtube.com/watch?v=zvfkXjzzYOo
- nabla9 10y ago
  D-Wave is doing adiabatic quantum computation. It's quantum analog computer. Comparable classical electric analog computers were last used in 50s or 60s. 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 http://science.sciencemag.org/content/345/6195/420 doi:10.1126/science.1252319
  - krastanov 10y ago
    Slight correction: D-Wave are most definitely not doing "adiabatic quantum computation". They occasionally have claimed that in the past, but not anymore. 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.
IanCal 10y ago
Is there an expectation of how hard it'll be to scale up the number of qubits? As in, do we think it'll be 10 times as hard each time we add another qubit, or that once we've got the stability sorted going from 5 to 10 to 50 to 100 is more a case of just building a bigger version? 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?
- krastanov 10y ago
  Depends on what exactly you are asking: 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.

machinelevel 10y ago

Hi there! This thread makes me so happy. I posted the Quantum Supersampling video and then went on vacation for a week, and while I was out a colleague sent me this link. Thanks for your kind words; they made my day. The thoughtful smart discussion going on here is exactly what I was hoping would happen. I'll post answers (as well as I can) to the items here as time permits. 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 http://qcengine.com 2: http://machinelevel.com/qc/bristol/liquid_samples.html http://machinelevel.com/qc/bristol/liquid_samples.html