5 ms·

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

by 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.
  - sanxiyn 7y ago
    Exact quote from the paper: "algorithm becomes exponentially more computationally expensive with increasing circuit depth". See also figure 4b, where circuit depth scaling is graphed.
    - tagrun 7y ago
      That sentence actually reads "Schrödinger–Feynman algorithm becomes exponentially more computationally expensive with increasing circuit depth" which is true (because the paths in a path integral in a discrete setting would grow combinatorically, but don't have to sort to path integrals to approximate the unitary in a "quick" and dirt way, which clearly doesn't scale well --in fact, if you avoid such "clever" tricks [which is only beneficial in some limited regime] and do it in the naive way, it will scale linearly). It's not the only game you can play on a classical computer, as IBM points out (for which the upfront cost is much higher). Figure 4b is about error estimation, They use XEB which is exponentially faster than, say doing full quantum process tomography, which is also true. That's the whole reasoning behind XEB, which gives far less information about the error channels, but you still have a fair estimate on the overall fidelity. None of these have anything to do with the complexity of the actual computation done on the quantum computer though.
      - sanxiyn 7y ago
        Indeed these don't have anything to do with quantum computers, but it does have something to do with quantum supremacy, because quantum supremacy is a claim about both quantum computers and classical computers. Google chose an algorithm exponential in circuit depth as the best classical algorithm in order to establish quantum supremacy. IBM demonstrated (as you agree) it is in fact not the best classical algorithm. IBM is entirely correct to point this out.
        tagrun 7y ago
        Again, no. It is a trivial fact that on a classical computer, you can simulate a quantum computer in time that grows linearly in circuit depth, in principle (as in the case of the "naive" way I mentioned above). No one in doing quantum algrothims ever claimed this was the case, and claiming otherwise is just a silly mistake. Preskill coined the word "quantum supremacy", not Martinis. Even if someone from Martinis' lab misspoke, you can't pin it on Preskill. Take Shor's algorithm, which has been the poster boy of quantum computing for decades. It gives exponential speed up in the number of qubits, not circuit depth. See other examples here: https://quantumalgorithmzoo.org/ https://quantumalgorithmzoo.org/ The complexity is in the number of qubits, "cirucit depth" is a non-concept in quantum algorithms. No one cares about the circuit depth in quantum algorithms, because in principle, you can always reduce the circuit depth to 1 on a quantum computer: quantum computers aren't necessarily made of basic logic gates, you can implement any unitary in by for example smoothly pulsing the fields in a correct way in a single go. "Depth" is a concept which usually comes into play when you try to measure the quality of the implementation of some given gate U. You repeat U many many times say M, and see how some measured quantity decays as a function of M, which gives a measure of the fidelity. But this has nothing to do with the quantum algorithm's complexity, it's just for "benchmarking" a physical implementation of the gate.
afthonos 7y ago
Thanks for the detailed response; I am not a physicist, so I didn’t catch the sleight of hand in the linear scaling claim. The timing of the “rebuttal” is almost certainly intentional, and possible because of the accidental pre-publication last month. I hope the rebuttal is indeed specious, because it’s an exciting advance; I’m sure time will tell.
- tagrun 7y ago
  It's pretty easy and requires no physics, actually. Here's a simple, extended version. A quantum gate is, mathematically speaking, a matrix. For a given physical system, of fixed number of qubits, obtaining that matrix on a classical computer takes (on average) a fixed amount of time, let's say T seconds. A quantum "circuit" is a sequence of quantum gates, applied consecutively in time, and you simply multiply them all to get their overall effect. So if your circuit is made of 10 gates, the total CPU time is 10T, plus the time for 10-1 matrix multiplications. If it is 20 gates, then it is 20T plus time for 20-1 matrix multiplications. Since multiplying two matrices of the same dimension also takes a fixed amount, on average, the simulation time grows linearly with circuit depth. The quantum supremacy is related to how T grows as you increase the number of qubits, n (which is exponential, it's a 2^n by 2^n matrix).

by tagrun 7y ago

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.
- sanxiyn 7y ago
  Exact quote from the paper: "algorithm becomes exponentially more computationally expensive with increasing circuit depth". See also figure 4b, where circuit depth scaling is graphed.
  - tagrun 7y ago
    That sentence actually reads "Schrödinger–Feynman algorithm becomes exponentially more computationally expensive with increasing circuit depth" which is true (because the paths in a path integral in a discrete setting would grow combinatorically, but don't have to sort to path integrals to approximate the unitary in a "quick" and dirt way, which clearly doesn't scale well --in fact, if you avoid such "clever" tricks [which is only beneficial in some limited regime] and do it in the naive way, it will scale linearly). It's not the only game you can play on a classical computer, as IBM points out (for which the upfront cost is much higher). Figure 4b is about error estimation, They use XEB which is exponentially faster than, say doing full quantum process tomography, which is also true. That's the whole reasoning behind XEB, which gives far less information about the error channels, but you still have a fair estimate on the overall fidelity. None of these have anything to do with the complexity of the actual computation done on the quantum computer though.
    - sanxiyn 7y ago
      Indeed these don't have anything to do with quantum computers, but it does have something to do with quantum supremacy, because quantum supremacy is a claim about both quantum computers and classical computers. Google chose an algorithm exponential in circuit depth as the best classical algorithm in order to establish quantum supremacy. IBM demonstrated (as you agree) it is in fact not the best classical algorithm. IBM is entirely correct to point this out.
      - tagrun 7y ago
        Again, no. It is a trivial fact that on a classical computer, you can simulate a quantum computer in time that grows linearly in circuit depth, in principle (as in the case of the "naive" way I mentioned above). No one in doing quantum algrothims ever claimed this was the case, and claiming otherwise is just a silly mistake. Preskill coined the word "quantum supremacy", not Martinis. Even if someone from Martinis' lab misspoke, you can't pin it on Preskill. Take Shor's algorithm, which has been the poster boy of quantum computing for decades. It gives exponential speed up in the number of qubits, not circuit depth. See other examples here: https://quantumalgorithmzoo.org/ https://quantumalgorithmzoo.org/ The complexity is in the number of qubits, "cirucit depth" is a non-concept in quantum algorithms. No one cares about the circuit depth in quantum algorithms, because in principle, you can always reduce the circuit depth to 1 on a quantum computer: quantum computers aren't necessarily made of basic logic gates, you can implement any unitary in by for example smoothly pulsing the fields in a correct way in a single go. "Depth" is a concept which usually comes into play when you try to measure the quality of the implementation of some given gate U. You repeat U many many times say M, and see how some measured quantity decays as a function of M, which gives a measure of the fidelity. But this has nothing to do with the quantum algorithm's complexity, it's just for "benchmarking" a physical implementation of the gate.

afthonos 7y ago

Thanks for the detailed response; I am not a physicist, so I didn’t catch the sleight of hand in the linear scaling claim. The timing of the “rebuttal” is almost certainly intentional, and possible because of the accidental pre-publication last month. I hope the rebuttal is indeed specious, because it’s an exciting advance; I’m sure time will tell.

tagrun 7y ago
It's pretty easy and requires no physics, actually. Here's a simple, extended version. A quantum gate is, mathematically speaking, a matrix. For a given physical system, of fixed number of qubits, obtaining that matrix on a classical computer takes (on average) a fixed amount of time, let's say T seconds. A quantum "circuit" is a sequence of quantum gates, applied consecutively in time, and you simply multiply them all to get their overall effect. So if your circuit is made of 10 gates, the total CPU time is 10T, plus the time for 10-1 matrix multiplications. If it is 20 gates, then it is 20T plus time for 20-1 matrix multiplications. Since multiplying two matrices of the same dimension also takes a fixed amount, on average, the simulation time grows linearly with circuit depth. The quantum supremacy is related to how T grows as you increase the number of qubits, n (which is exponential, it's a 2^n by 2^n matrix).