3 ms·

What is a "first actually working quantum computer" if not this Sycamore device that Google used to demonstrate quantum supremacy?

by rrss 7y ago

Laakeri 7y ago
Maybe something that solves a natural problem instead of an artificial one.
SAI_Peregrinus 7y ago
One with fault-tolerance.
317070 7y ago
I reckon one that has quantum error correction on qubits which present Boolean values. I.e. one which could also run a classical program. That is the quantum computer which is actually a quantum Turing machine and which can do speedups of e.g. factorization. Unfortunately, it is hypothesized that such a quantum Turing machine will require about ~1000 qubits of this machine per qubit with error correction, maybe more.
- kulahan 7y ago
  For what it's worth, the FAQ on his blog dances around this topic: "Running Shor’s algorithm to break the RSA cryptosystem would require several thousand logical qubits. With known error-correction methods, that could easily translate into millions of physical qubits, and those probably of a higher quality than any that exist today."
  - grubles 7y ago
    "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" https://arxiv.org/abs/1905.09749 https://arxiv.org/abs/1905.09749
ThePhysicist 7y ago
You could of course argue that it's already a quantum computer that they've built. It's not a general purpose quantum computer though, as it doesn't allow you to run arbitrary gate sequences on it due to limited coherence time and limited inter-qubit connectivity. So while you surely can do some quantum computations on it you can't yet run arbitrary quantum programs.
- yvdriess 7y ago
  In terms of limited connectivity: mesh connectivity is theoretically sufficient. Putting all qubits in superposition in a preparation phase then allows you to do any arbitrary quantum computation by a sequence of measurements and one-qubit operations. You would be doing one-way measurement quantum computing, and not quantum circuits, but it's just as universal.
dekhn 7y ago
I'd love to see one that can compute energy levels for molecules that are larger than we can currently simulate on supercomputers. quantum chemistry simulations typically scale O(n7) where n = # of basis functions (usually larger than the number of atoms in the molecule).
- comicjk 7y ago
  I agree with you, but with a couple of corrections. The cheaper algorithm called Density Functional Theory is probably the most popular kind of quantum calculation on molecules, and scales as ~N^2.5 in practice. On the other hand, the number of basis functions is a more than the number of valence electrons in the molecule (if the calculation is at all sane), much larger than the number of atoms. So the exponent is often smaller than you said, but the N is also much bigger. So in the end you're absolutely right about the need for quantum computing for molecules.

What is a "first actually working quantum computer" if not this Sycamore device that Google used to demonstrate quantum supremacy?

by rrss 7y ago

What is a "first actually working quantum computer" if not this Sycamore device that Google used to demonstrate quantum supremacy?

Laakeri 7y ago

Maybe something that solves a natural problem instead of an artificial one.

SAI_Peregrinus 7y ago

One with fault-tolerance.

317070 7y ago

I reckon one that has quantum error correction on qubits which present Boolean values. I.e. one which could also run a classical program. That is the quantum computer which is actually a quantum Turing machine and which can do speedups of e.g. factorization. Unfortunately, it is hypothesized that such a quantum Turing machine will require about ~1000 qubits of this machine per qubit with error correction, maybe more.

kulahan 7y ago
For what it's worth, the FAQ on his blog dances around this topic: "Running Shor’s algorithm to break the RSA cryptosystem would require several thousand logical qubits. With known error-correction methods, that could easily translate into millions of physical qubits, and those probably of a higher quality than any that exist today."
- grubles 7y ago
  "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" https://arxiv.org/abs/1905.09749 https://arxiv.org/abs/1905.09749

ThePhysicist 7y ago

You could of course argue that it's already a quantum computer that they've built. It's not a general purpose quantum computer though, as it doesn't allow you to run arbitrary gate sequences on it due to limited coherence time and limited inter-qubit connectivity. So while you surely can do some quantum computations on it you can't yet run arbitrary quantum programs.

yvdriess 7y ago
In terms of limited connectivity: mesh connectivity is theoretically sufficient. Putting all qubits in superposition in a preparation phase then allows you to do any arbitrary quantum computation by a sequence of measurements and one-qubit operations. You would be doing one-way measurement quantum computing, and not quantum circuits, but it's just as universal.

dekhn 7y ago

I'd love to see one that can compute energy levels for molecules that are larger than we can currently simulate on supercomputers. quantum chemistry simulations typically scale O(n7) where n = # of basis functions (usually larger than the number of atoms in the molecule).

comicjk 7y ago
I agree with you, but with a couple of corrections. The cheaper algorithm called Density Functional Theory is probably the most popular kind of quantum calculation on molecules, and scales as ~N^2.5 in practice. On the other hand, the number of basis functions is a more than the number of valence electrons in the molecule (if the calculation is at all sane), much larger than the number of atoms. So the exponent is often smaller than you said, but the N is also much bigger. So in the end you're absolutely right about the need for quantum computing for molecules.