111–120 of 149 posts
I don't trust anything IBM says. They have a long history of lying and misleading that continues to this day. It's about as trustworthy as Facebook saying you shouldn't be concerned about privacy on Facebook.
Earlier quoted context omitted.
Crucial question - is the calibration a one time effort where the same calibration can be used to calculate any number of results within the calibrated space? In other words, can you amortize the calibration cost across 1,000 runs and come out an order of magnitude ahead?
"John Martinis explicitly confirmed for me that once the qubits are calibrated, you can run any circuit on them that you want." https://www.scottaaronson.com/blog/?p=4372
A source of this confusion is that we need to discuss space and time complexity simultaneously. In the algorithms for quantum simulation (and many other algorithms), there is a trade off between space complexity and time complexity. ELI5: You don't have to store intermediate results if you can recompute them when you need them, but you may end up recomputing them a huge number of times.
For the quantum circuit, the standard method of computation gives exponential memory complexity in number of qubits (store 2^N amplitudes for a N qubit wavefunction) and time complexity D2^N, i.e. linear in circuit depth and exponential in number of qubits. For example, under the IBM calculation, 53 qubits at depth 30 use 64 PB of storage and a few days of calculation time, while 54 qubits use 128 PB and a week in calculation time. Adding a qubit doubles the storage requirements AND the time requirements.
Under google's estimation of the run time, they were using a space time memory tradeoff. There is a continuous range of space-time memory tradeoffs - USE MAX MEMORY as IBM does, MAX RECOMPUTATION (store almost no intermediate results, just add each contribution to the final answer and recompute everything) and a range of in-between strategies. While I don't know the precise complexities, the time-heavy strategies will have time complexity exponential in both N and D ( 2^(ND) ) and space complexity constant.That's why googles estimate for time complexity is so drastically different than IBMs.
Side note: IBM also uses a non-standard evaluation order for the quantum circulation, which utilizes a trade-off between depth and number of qubits. In the regime of a large number of qubits, but a relatively small depth, you can again classically simulate using an algorithm that scales N*2^D rather than D2^N, using a method that turns the quantum circuit on its side and contracts the tensors that way. In the regime of N comparable to D, the optimal tensor contraction corresponds to neither running the circuit the usual way or sideways but something in between. None of these tricks fundamentally change the ultimate exponential scaling, however.
As an extra step, you could also run compression techniques on the tensors (i.e. SVD, throwing away small singular values), to make the space-time complexity tradeoff into a three-way space-time-accuracy tradeoff. You wouldn't expect too much gain by compression, and your accuracy would quickly go to zero if you tried to do more and more qubits or longer depth circuits with constant space and time requirements. However, the _real_ quantum computer (as Google has it now, with no error correction) also has accuracy that goes to zero with larger depth and number of qubits. Thus, one can imagine that the next steps in this battle are as following: If we say that Google's computer has not at this moment beaten classical computers with 128PB of memory to work with, then google will respond with a bigger and more accurate machine that will again claim to beat all classical computers. Then IBM will add in compression for the accuracy tradeoff and perhaps again will still beat the quantum machine.
So this back and forth can continue for a while - but the classical computers are ultimately fighting a losing battle, and the quantum machine will triumph in the end, as exponentials are a bitch.
Earlier quoted context omitted.
Isn't quantum factoring proven to be exponentially faster than the best known classical one? The only question is we don't know if there is a better classical factoring algorithm. Wikipedia: > On a quantum computer, to factor an integer N, Shor's algorithm runs in polynomial time. This is almost exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which wor…
Yes, for factoring integers the best known quantum algorithm is better than the best known classical algorithm. The catch is that we don't know if a better classical algorithm exists but just wasn't discovered yet. Compare this for example to sorting. We have proven that any sorting algorithm working with comparisons can at best be O(n*log(n)) fast, it's impossible for a faster classical algorithm to exist.
If a worst case to simulate on a classical computer is 2.5 days (per IBM's blog) then they should either: 1. Actually preform the experiment per their approach, compare the results, and provide tangible proof in the coming days. or 2. Retract their claims. In either case, exciting times ahead. [Edit: Yes, I read their published paper[1] which only claims it is possible to achieve and does not perform the same experim…
Earlier quoted context omitted.
They didn't say 2.5 days on a laptop. They probably mean on a bunch of datacenters together. That is expensive. Google implied their supremacy over all of the world computers combined together.
These calculations of 2.5 day and 1000 years, they're calculations based on specific parameters, right? Could they just prove it on a smaller version of the problem instead? Can they do a version of the problem which takes maybe 1m on with IBMs algorithm and 1 year with Google's?
There's also an alternative algorithm that requires less space, but it takes longer.
Also of note is Gil Kalai's updated take on the experiment [1]. The heart of the complaint is that the quantum computer's solution to this problem relies on a calibration process, which is done on a classical computer and requires resources orders of magnitudes higher than the quantum portion of the computation: > The Google experiment actually showed that a quantum computer running for 100 seconds PLUS a classic com…
We should probably amend the link to point to IBM's actual blog post, https://www.ibm.com/blogs/research/2019/10/on-quantum-suprem...
Earlier quoted context omitted.
Yes, for factoring integers the best known quantum algorithm is better than the best known classical algorithm. The catch is that we don't know if a better classical algorithm exists but just wasn't discovered yet. Compare this for example to sorting. We have proven that any sorting algorithm working with comparisons can at best be O(n*log(n)) fast, it's impossible for a faster classical algorithm to exist.
>We have proven that any sorting algorithm working with comparisons can at best be O(n*log(n)) fast, it's impossible for a faster classical algorithm to exist. You can have a faster classical algorithm if it's distributed across n threads for a size n array. For each index i in an array arr, spawn a thread that counts the number of values in arr that are less than arr[i] (an O(n) linear scan), call this x, then do ou…
"Total Work" is the important part to minimize in practice. If "total work" scales at O(n^2), then in practice, the job scales at O(n^2). Its infeasible to build O(n^2) CPUs running O(n^2) threads as n-grows.
Scott Aaronson now has a detailed analysis and covers the IBM claims as well: https://www.scottaaronson.com/blog/?p=4372 The high order bit is that the IBM claims do not cast much of a shadow over the claims of quantum supremacy and still show the same exponential difference.