4 ms·
No, that's years in the future at least. Factoring 21 without any compilation tricks requires doing a modular exponentiation under superposition. The best known
by Strilanc 4y ago
No, that's years in the future at least. Factoring 21 without any compilation tricks requires doing a modular exponentiation under superposition. The best known way to do that requires two registers of workspace (10 qubits), plus a teensy bit of breathing room (2 qubits), so call it a dozen logical qubits. If all compilation tricks are banned, even the ones that are reasonable for huge numbers but work a bit too well for small numbers such as using small lookup tables to fuse some of the multiplications together, the overall computation takes on the order of 10000 gates. If you require it to work in one or two shots (otherwise even random coin flipping will work), then those gates need to have error rates below one in a hundred thousand and your storage needs error rates per round below one in ten million.
The experiment being announced here is testing different ways storing 1 error corrected qubit, to show that making it bigger can make it better. On an absolute scale, that logical qubit is still not good enough. It needs to be made even bigger. And there needs to be a dozen of them instead of one. And it's barely breaking even; you want strong gains in quality from adding quantity not just minor gains. This means the underlying physical qubits still need more improvement. There's a lot to do!
Disclaimer: am on google quantum team, opinions are my own.
- sebzim4500 4y agoSounds like you are just talking about Shor's algorithm. Presumably if you wanted to factorise 21 naively you could do it with fewer qbits, you just wouldn't demonstrate any kind of quantum speedup.
- Strilanc 4y agoIf I wanted to factorize 21 without demonstrating any kind of quantum speedup, I'd use pen and paper.