8 ms·

"Quantum Supremacy" is a technical term, not a colloquial one. It refers to showing that there exists a problem that a real, physical quantum computer can solve

"Quantum Supremacy" is a technical term, not a colloquial one. It refers to showing that there exists a problem that a real, physical quantum computer can solve quickly that a classical computer cannot. Reading the IBM article, they are fully aware of what "quantum supremacy" means in a technical sense, and they are urging the media not to use that term, since it will be misunderstood by the public. Their claim that Google has failed to achieve supremacy rests solely on their claim that they can simulate the circuit far faster (and scale the simulation linearly) using better classical algorithms. That's a strong claim, and I'm interested in seeing what Google responds with. Disclosure: I work at Google, but hahaha, no, I'm not cool enough to work on this.

sanxiyn 7y ago
Thank you. I am not sure why people are talking about 2.5 days, since the key claim is "linearly scaling". If simulation is linearly scaling in this regime, the entire proof is indeed questionable.
- mazesc 7y ago
  IBMs response seems strong regarding "linear scaling", but could they give a complexity-theoretic argument rather than an empirical one?
  - sanxiyn 7y ago
    I think IBM didn't elaborate because it is kind of obvious if you are into this, and if you are not, linearly scaling graph from 10 to 30 is more than good enough. But since we have niche audience here, let's elaborate. Quantum supremacy is O(n) claim. Then what is n? The answer is that there are two parameters, not one. In Google paper, n is number of qubits and m is circuit depth. n is well known to be difficult to increase. m is not easy either, because if your qubit isn't stable enough, you can't run deep circuit. What Google did is to run n=53 and m=20. Then, why do you need n=53 and m=20? After all, you could see whether it's exponential by, say, trying n and m from 10 to 15, it doesn't need to take days and years. The answer is that there is time-space tradeoff available and if your n is constant, exp(n) space (but still constant space, since n is constant) poly(m) time algorithm is available, and if your m is constant, exp(m) space (but still constant space, since m is constant) poly(n) time algorithm is available. So if you want to show exponential speedup, you need to be able to exclude these algorithms by increasing n or m enough such that exp(n) or exp(m) space is not realizable. Google chose n=53 such that exp(n) is not realizable, and ran scaling experiment on m. This is what they mean whey they say in the paper "Up to 43 qubits, we use a Schrödinger algorithm, which simulates the evolution of the full quantum state... Above this size, there is not enough random access memory (RAM) to store the quantum state". Now what IBM is saying is becoming clear. There is not enough RAM, but there is enough disk, so exp(n) where n=53 is realizable, and simulation runs linear in m. It's not a new algorithm, it's exactly the same algorithm Google ran up to n=43. So 43 qubits clearly can't demonstrate quantum supremacy. For the same reason, 53 qubits can't either.
    - mazesc 7y ago
      Thanks a lot, that was insightful!
    - htfu 7y ago
      Thanks for the breakdown! But so in other words, it’s still not all that far off that (realistic amounts of) disk storage can’t contain the state and scaling reverts to how they assert it.
      - sanxiyn 7y ago
        Indeed. It's just that 2^53 bytes (about 10 petabytes) of storage is in fact available, so you need a few more qubits to exclude that.
        AlanYx 7y ago
        It's not quite that efficient... IBM's arxiv paper says "64 PiB of disk space are required for 53-qubit circuits, and 128 PiB for 54-qubit circuits". Summit has 250 PiB of total storage currently, so it would seem that a 55-qubit simulation is almost within reach by IBM's method as well.
    - mannykannot 7y ago
      Thanks for this clear explanation of the issue! This looks to me like a convincing rebuttal of the specific claim Google made about classical runtime at this particular size, but does it rule out Google claiming supremacy by using the problem constrained such that n == m? Or would Google's device have exponential runtime growth in that variant?
marktangotango 7y ago
> Disclosure: I work at Google, but hahaha, no, I'm not cool enough to work on this. I often wonder why people feel compelled to write this. There nothing in your profile or in your post history to prove unequivocally you do or don’t work anywhere in particular so why even mention it? Edit; responders are citing ethics and company policy; but does anyone really think vague hand wavey speculation on a public message board is relavant to anthing? Sure if you work in the ads group and you posted "wow, our division is in trouble, competitor Z is really killing it, and our quarter earnings are going to miss big time!" Yeah that matters, but GP? Really?
- AYBABTME 7y ago
  To disclose possible bias, in this case maybe parent feels like their opinion might be biased toward Google's claim.
- afthonos 7y ago
  Company policy. This prevents headlines like "Google had employees secretly astroturf to give traction to their quantum supremacy claims" if someone decides to truly dig. I theoretically could pretend I don't work here, but I find life is easier if I just follow reasonable rules. (I did forget to mention I didn't speak for Google, but it should be pretty obvious from context)
- otterley 7y ago
  First, it’s a professional ethics requirement. If there is the possibility of a conflict of interest in our statement, we need to disclose it to avoid misleading anyone. In addition, there are plenty of ways to figure out where an HN member is employed besides looking at their post history. It’s not necessarily found in publicly available data, but it can be found. Also, you have to account for future acts. Disclosing early can help insure against accusations about misconduct if you were to out yourself — or someone were to out you — later.
- smadurange 7y ago
  I agree. Possibly to just give a bit more weight to what they say. So far, I've mostly seen this with Google employees here. Can't remember seeing anyone else mentioning this except when promoting a product. 1. Regarding policy, I think a simple disclosure like this is my personal opinion not that of my employer would be good enough. 2. Indicate possible bias: nope, one should always understand any opinion is biased due to many different reasons. So, unless this is a rigorous analysis of something, this is quite uncalled for.
skywhopper 7y ago
But from the Google blog it sounds like the “problem” they chose boils down to “emulating a quantum computer”. Which doesn’t sound like it’s exactly in the spirit of the test, since the quantum computer can obviously emulate itself—and with zero wasted operations!
- afthonos 7y ago
  It's exactly the spirit of the test; the missing element is that the circuit they're emulating can scale in qubits. So the question is, if you add one cubit, what happens? Can classical computers keep up? The tests were run on a range of cubits with 50+ being the largest number, which is where the 10,000 year claim comes from. Anything further than that just isn't feasible to compute on classical computers, because they don't scale like that. So why is this in the spirit of the test? Because this means that there are some problems that can only be efficiently solved by quantum computers. So this establishes "supremacy" in the sense that while a quantum computer can efficiently solve any classical computing problem, a classical computer cannot solve any quantum computing problem. The distance between having this proof-of-concept and having meaningful speedups on real problems that cannot be matched by classical computers is very large; all this tells you is that it's possible, and looking more might not be a waste.
tagrun 7y ago
Physicists here. Note that they say it scales linearly in circuit depth (which is a trivial fact, and has always been true for classical simulations of quantum computers which are optimal in that regard --in fact, that is the case when doing it in the most naive way), not the number of qubits which is the quantum speed up referred in "quantum supremacy". Another thing, this is actually Martinis' decades long work. I know Google recently started raining money down on his lab a couple years back, helping with the classical aspects, design etc, and media loves reporting as Google's Quantum Computer, but the actual quantum computer, the nitty gritty physics isn't Google's work. Martinis already had a working setup with ~10 qubits when Google started supporting him ~5 years ago. This IBM "rebuttal" sounds a bit like cheating on multiple aspects, and the timing of the announcement is interesting. Note that they don't tell you how the memory requirements grow with the number of qubits either (which is exponential as well). I expect the response will be new toy computation proposals which will also be prohibitively expensive in classical memory (not just classical CPU with limited memory) in current supercomputers as well. If the experimentalists can roll out more qubits faster though (less likely), the "concern" will be addressed as well.
- sanxiyn 7y ago
  No, if you read Google paper, quantum supremacy is entirely about circuit depth scaling.
  - tagrun 7y ago
    No idea where exactly you got that idea (feel free to quote any part of the paper), but no, it isn't. Even the brute force "simulation" of a quantum computer is like UN...U2.U1 where Us are unitarity matrices. The hard part is obtaining those unitaries (whose dimensions grow exponentially with the number of qubits). For fixed number of qubits though, once you have N unitaries, you do N matrix multiplications. If you double N, it'll take twice long on a classical and roughly twice on a quantum computer (different gates take different amount of time to implement). But on an actual quantum computer, there are tricks you can do (if the Hamiltonian allows) which may allow you to do it in fewer unitaries. Circuit depth is still important because it is important 1) for modelling the noise in the device and extracting gate fidelities, that's basically how randomized benchmarking works although they're doing something else for fidelity estimates it still is a function of circuit depth 2) for doing anything meaningful when using a given set of basic building block gates.
deleted 7y ago
[deleted]
NotAnEconomist 7y ago
> "Quantum Supremacy" is a technical term, not a colloquial one. It refers to showing that there exists a problem that a real, physical quantum computer can solve quickly that a classical computer cannot. So my bath tub full of water has "quantum supremacy" over any super computer, because measuring the result in 1 minute at high fidelity would be much, much harder to do on a classical computer? IBM's claim is Google has a very expensive bath tub of water.

sanxiyn 7y ago

Thank you. I am not sure why people are talking about 2.5 days, since the key claim is "linearly scaling". If simulation is linearly scaling in this regime, the entire proof is indeed questionable.

mazesc 7y ago
IBMs response seems strong regarding "linear scaling", but could they give a complexity-theoretic argument rather than an empirical one?
- sanxiyn 7y ago
  I think IBM didn't elaborate because it is kind of obvious if you are into this, and if you are not, linearly scaling graph from 10 to 30 is more than good enough. But since we have niche audience here, let's elaborate. Quantum supremacy is O(n) claim. Then what is n? The answer is that there are two parameters, not one. In Google paper, n is number of qubits and m is circuit depth. n is well known to be difficult to increase. m is not easy either, because if your qubit isn't stable enough, you can't run deep circuit. What Google did is to run n=53 and m=20. Then, why do you need n=53 and m=20? After all, you could see whether it's exponential by, say, trying n and m from 10 to 15, it doesn't need to take days and years. The answer is that there is time-space tradeoff available and if your n is constant, exp(n) space (but still constant space, since n is constant) poly(m) time algorithm is available, and if your m is constant, exp(m) space (but still constant space, since m is constant) poly(n) time algorithm is available. So if you want to show exponential speedup, you need to be able to exclude these algorithms by increasing n or m enough such that exp(n) or exp(m) space is not realizable. Google chose n=53 such that exp(n) is not realizable, and ran scaling experiment on m. This is what they mean whey they say in the paper "Up to 43 qubits, we use a Schrödinger algorithm, which simulates the evolution of the full quantum state... Above this size, there is not enough random access memory (RAM) to store the quantum state". Now what IBM is saying is becoming clear. There is not enough RAM, but there is enough disk, so exp(n) where n=53 is realizable, and simulation runs linear in m. It's not a new algorithm, it's exactly the same algorithm Google ran up to n=43. So 43 qubits clearly can't demonstrate quantum supremacy. For the same reason, 53 qubits can't either.
  - mazesc 7y ago
    Thanks a lot, that was insightful!
  - htfu 7y ago
    Thanks for the breakdown! But so in other words, it’s still not all that far off that (realistic amounts of) disk storage can’t contain the state and scaling reverts to how they assert it.
    - sanxiyn 7y ago
      Indeed. It's just that 2^53 bytes (about 10 petabytes) of storage is in fact available, so you need a few more qubits to exclude that.
      - AlanYx 7y ago
        It's not quite that efficient... IBM's arxiv paper says "64 PiB of disk space are required for 53-qubit circuits, and 128 PiB for 54-qubit circuits". Summit has 250 PiB of total storage currently, so it would seem that a 55-qubit simulation is almost within reach by IBM's method as well.
  - mannykannot 7y ago
    Thanks for this clear explanation of the issue! This looks to me like a convincing rebuttal of the specific claim Google made about classical runtime at this particular size, but does it rule out Google claiming supremacy by using the problem constrained such that n == m? Or would Google's device have exponential runtime growth in that variant?

marktangotango 7y ago

> Disclosure: I work at Google, but hahaha, no, I'm not cool enough to work on this. I often wonder why people feel compelled to write this. There nothing in your profile or in your post history to prove unequivocally you do or don’t work anywhere in particular so why even mention it? Edit; responders are citing ethics and company policy; but does anyone really think vague hand wavey speculation on a public message board is relavant to anthing? Sure if you work in the ads group and you posted "wow, our division is in trouble, competitor Z is really killing it, and our quarter earnings are going to miss big time!" Yeah that matters, but GP? Really?

AYBABTME 7y ago
To disclose possible bias, in this case maybe parent feels like their opinion might be biased toward Google's claim.
afthonos 7y ago
Company policy. This prevents headlines like "Google had employees secretly astroturf to give traction to their quantum supremacy claims" if someone decides to truly dig. I theoretically could pretend I don't work here, but I find life is easier if I just follow reasonable rules. (I did forget to mention I didn't speak for Google, but it should be pretty obvious from context)
otterley 7y ago
First, it’s a professional ethics requirement. If there is the possibility of a conflict of interest in our statement, we need to disclose it to avoid misleading anyone. In addition, there are plenty of ways to figure out where an HN member is employed besides looking at their post history. It’s not necessarily found in publicly available data, but it can be found. Also, you have to account for future acts. Disclosing early can help insure against accusations about misconduct if you were to out yourself — or someone were to out you — later.
smadurange 7y ago
I agree. Possibly to just give a bit more weight to what they say. So far, I've mostly seen this with Google employees here. Can't remember seeing anyone else mentioning this except when promoting a product. 1. Regarding policy, I think a simple disclosure like this is my personal opinion not that of my employer would be good enough. 2. Indicate possible bias: nope, one should always understand any opinion is biased due to many different reasons. So, unless this is a rigorous analysis of something, this is quite uncalled for.

skywhopper 7y ago

But from the Google blog it sounds like the “problem” they chose boils down to “emulating a quantum computer”. Which doesn’t sound like it’s exactly in the spirit of the test, since the quantum computer can obviously emulate itself—and with zero wasted operations!

afthonos 7y ago
It's exactly the spirit of the test; the missing element is that the circuit they're emulating can scale in qubits. So the question is, if you add one cubit, what happens? Can classical computers keep up? The tests were run on a range of cubits with 50+ being the largest number, which is where the 10,000 year claim comes from. Anything further than that just isn't feasible to compute on classical computers, because they don't scale like that. So why is this in the spirit of the test? Because this means that there are some problems that can only be efficiently solved by quantum computers. So this establishes "supremacy" in the sense that while a quantum computer can efficiently solve any classical computing problem, a classical computer cannot solve any quantum computing problem. The distance between having this proof-of-concept and having meaningful speedups on real problems that cannot be matched by classical computers is very large; all this tells you is that it's possible, and looking more might not be a waste.

tagrun 7y ago

Physicists here. Note that they say it scales linearly in circuit depth (which is a trivial fact, and has always been true for classical simulations of quantum computers which are optimal in that regard --in fact, that is the case when doing it in the most naive way), not the number of qubits which is the quantum speed up referred in "quantum supremacy". Another thing, this is actually Martinis' decades long work. I know Google recently started raining money down on his lab a couple years back, helping with the classical aspects, design etc, and media loves reporting as Google's Quantum Computer, but the actual quantum computer, the nitty gritty physics isn't Google's work. Martinis already had a working setup with ~10 qubits when Google started supporting him ~5 years ago. This IBM "rebuttal" sounds a bit like cheating on multiple aspects, and the timing of the announcement is interesting. Note that they don't tell you how the memory requirements grow with the number of qubits either (which is exponential as well). I expect the response will be new toy computation proposals which will also be prohibitively expensive in classical memory (not just classical CPU with limited memory) in current supercomputers as well. If the experimentalists can roll out more qubits faster though (less likely), the "concern" will be addressed as well.

sanxiyn 7y ago
No, if you read Google paper, quantum supremacy is entirely about circuit depth scaling.
- tagrun 7y ago
  No idea where exactly you got that idea (feel free to quote any part of the paper), but no, it isn't. Even the brute force "simulation" of a quantum computer is like UN...U2.U1 where Us are unitarity matrices. The hard part is obtaining those unitaries (whose dimensions grow exponentially with the number of qubits). For fixed number of qubits though, once you have N unitaries, you do N matrix multiplications. If you double N, it'll take twice long on a classical and roughly twice on a quantum computer (different gates take different amount of time to implement). But on an actual quantum computer, there are tricks you can do (if the Hamiltonian allows) which may allow you to do it in fewer unitaries. Circuit depth is still important because it is important 1) for modelling the noise in the device and extracting gate fidelities, that's basically how randomized benchmarking works although they're doing something else for fidelity estimates it still is a function of circuit depth 2) for doing anything meaningful when using a given set of basic building block gates.

deleted 7y ago

[deleted]

NotAnEconomist 7y ago

> "Quantum Supremacy" is a technical term, not a colloquial one. It refers to showing that there exists a problem that a real, physical quantum computer can solve quickly that a classical computer cannot. So my bath tub full of water has "quantum supremacy" over any super computer, because measuring the result in 1 minute at high fidelity would be much, much harder to do on a classical computer? IBM's claim is Google has a very expensive bath tub of water.