Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An Argument Against Quantum Computers

quantamagazine.org

Post reply on HN
Print view View original

41–50 of 67 posts

Re: An Argument Against Quantum Computers

#41

Post by kirrent »

smaddox wrote: post #31
kirrent wrote: post #11

Scott Aaronson still has his $100 000 wager available for an actual refutation of scalable QC. The impetus for the bet was actually from arguing with Gil Kalai in the comments on a blog. https://www.scottaaronson.com/blog/?p=902

Whether or not you can make a scalable quantum computer is beside the point, though. The question is, can you make a quantum computer that is competitive with a classical computer, speed and/or cost wise. I suspect that any speedup imparted by clever uses of entanglement will be counteracted by the fundamental need for error correction and averaging over several runs. I look forward to being proven either right or wr…

'I suspect that any speedup imparted by clever uses of entanglement will be counteracted by the fundamental need for error correction and averaging over several runs.'

Perhaps you don't understand what people mean when they say scalable quantum computing? They mean that it scales with the error correction included. Needing to average over several runs is already factored into the complexity of quantum algorithms.

Also, whether you can make a scalable quantum computer isn't beside the point. It's the entire point Kalai's trying to make. If you can make a scalable quantum computer we already know that there are applications it will outperform a classical computer on performance and cost.

Re: An Argument Against Quantum Computers

#42

Post by smallnamespace »

codekilla wrote: post #32
jcranmer wrote: post #30

Earlier quoted context omitted.

That argument is patently wrong: it's the quantum bullshit fallacy. The point of the space argument I was making was that, if you need N bits of space to represent the input/output in classical computers, you should still need (I'm not sure if it's the case, but I don't see why it's not) Ω(N) qubits to do the same representation in a quantum computer. The quantum bullshit fallacy is that, since an entangled N-qubit i…

Honestly, I don't understand the point you are making. If you can explain to me how the Deutsch-Joza algorithm works without making reference to the fact that a function evaluation happens on a qubit in superposition(and thus an expanded state-space, as the simplest example), sure. I sincerely don't understand your points about classical simulation, or input/output in classical computers.

As you say, N qubits can be thought of as a distribution over its possible 2^N values, but you can't ignore the starting distribution, which may be very far from the set of classical bits that you want to operate over (and therefore may take an exponential number of quantum operations to realize).

So one very simplified model to think of what quantum computation is that you can do parallel operations to a distribution over your 2^N vector of classical bits, but you don't get to specify an arbitrary starting distribution, you can only start with relatively 'simple' distributions.

This restriction is what makes the claim 'you can compute over 2^N values simultaneously' at best very incomplete — yes, you can do that, as long as you're fine not being able to start from arbitrary starting values. But this is a big restriction!

Re: An Argument Against Quantum Computers

#43

Post by stcredzero »

vtomole wrote: post #40
cbHXBY1D wrote: post #29

Earlier quoted context omitted.

Why are topological quantum computers more resilient? Do they handle the problem of decoherence better?

Yes, they do handle decoherence better. Here is a video explaining the theory behind the particles that are used to perform topological quantum computation [0]. I emphasize that unlike superconducting, quantum dots, ion traps, photonic e.t.c; topological quantum computers have not been physically realized because non-abelian anyons have not been detected. [0]: https://www.youtube.com/watch?v=hKFecm9NKbM

"Non-Abelian Anyons" would be a great band name. "Have Not Been Detected" would be a great 1st album name.

Re: An Argument Against Quantum Computers

#44

Post by codekilla »

smallnamespace wrote: post #42
codekilla wrote: post #32

Earlier quoted context omitted.

Honestly, I don't understand the point you are making. If you can explain to me how the Deutsch-Joza algorithm works without making reference to the fact that a function evaluation happens on a qubit in superposition(and thus an expanded state-space, as the simplest example), sure. I sincerely don't understand your points about classical simulation, or input/output in classical computers.

As you say, N qubits can be thought of as a distribution over its possible 2^N values, but you can't ignore the starting distribution , which may be very far from the set of classical bits that you want to operate over (and therefore may take an exponential number of quantum operations to realize). So one very simplified model to think of what quantum computation is that you can do parallel operations to a distributi…

What do you mean exactly by starting distribution? I'm definitely not saying you get the answer to every problem in a single evaluation step, no one ever said that.

Re: An Argument Against Quantum Computers

#45

Post by davidgay »

zitterbewegung wrote: post #12

Gil Kalai can have his contrarian opinion on quantum computers. But we can have a much simpler argument against quantum computers. That they will remain infeasible for a long enough time for traditional computers to catch up to it. What I mean by traditional computers catching up with it is that we will see innovations in traditional algorithms that either make quantum computers extremely pricey for a very long time…

> Gil Kalai can have his contrarian opinion on quantum computers. But we can have a much simpler argument against quantum computers. That they will remain infeasible for a long enough time for traditional computers to catch up to it.

IIUC and IIRC (both somewhat doubtful admittedly), Feynman argued - https://people.eecs.berkeley.edu/~christos/classics/Feynman.... - that only a quantum computer can perform a scalable simulation of quantum physics. Assuming that is correct, there is no option for "traditional computers" to catch up for all problems at least.

Re: An Argument Against Quantum Computers

#46

Post by Robotbeat »

vtomole wrote: post #40
cbHXBY1D wrote: post #29

Earlier quoted context omitted.

Why are topological quantum computers more resilient? Do they handle the problem of decoherence better?

Yes, they do handle decoherence better. Here is a video explaining the theory behind the particles that are used to perform topological quantum computation [0]. I emphasize that unlike superconducting, quantum dots, ion traps, photonic e.t.c; topological quantum computers have not been physically realized because non-abelian anyons have not been detected. [0]: https://www.youtube.com/watch?v=hKFecm9NKbM

...they have, if you believe this (fairly convincing!) set of evidence showing perfect Andreev Reflection (robust to changes in gate potential), which should only be possible (in a way robust to changes in gate potential) in the presence of Majorana states (i.e. a type of non-abelian anyon): https://quantumfrontiers.com/2017/11/21/majorana-update/

Re: An Argument Against Quantum Computers

#47

Post by Robotbeat »

codekilla wrote: post #39
cbHXBY1D wrote: post #29

Earlier quoted context omitted.

Why are topological quantum computers more resilient? Do they handle the problem of decoherence better?

Yes, they are the theoretically the most elegant way to deal with decoherence. They rely on an exotic state of matter, non-abelian anyons(many still working on verifying their existence), and winding discrete non-abelian anyons into a topological braid, which disperses the quantum state spatially, making it much more resilient against decoherence(obvious simplifications made). This is the specific type of quantum com…

What's interesting about topological quantum computing is that these Majorana pairs are resistant to disturbances for the same reason that Cooper pairs are in superconductors.

Re: An Argument Against Quantum Computers

#48

Post by wyager »

jcranmer wrote: post #25
wyager wrote: post #14

Earlier quoted context omitted.

Your answer doesn’t actually explain what we can do on a quantum computer that we can’t on a traditional computer. The answer: we don’t know. We don’t even know if BQP is actually any bigger than P. However, we’ve figured out how to do some things quickly on quantum computers that we haven’t ever figured out how to do quickly on classical computers, like certain mathematically useful operations on abelian groups. One…

> If your vector space is too big to even represent in classical memory, you might still be able to work with it on a quantum computer. Quantum computers don't have any space advantage, I thought?

Your question is too simple to have a correct answer.

You can represent any unit vector in a vector space with 2^n basis elements using only n qubits.

Constructing an arbitrary vector might not be more efficient than doing it on a classical computer, but constructing certain vectors that would probably be very large and/or unwieldy on a classical computer is possible. For example, it’s easy to represent any single standard basis vector in a vector space with size 2^64 on a classical computer; just use a list of (64-bit word to describe which basis vector you’re talking about and a weight). Now go ahead and try to use that same representation for a Fourier transform, and you’re out of luck. But this is no problem on a quantum computer. You just end up with a 64-qubit system that has a non-zero value for all of those 2^64 basis states (using only 64 qubits). You can also construct the circuit required to do the Fourier transform with ~64log(64) gates.

So for this problem, there’s definitely a space advantage. The trouble is that most of these advantages don’t generalize in any obvious way. Maybe there’s even a representation on classical computers that’s equally efficient and we just haven’t found it yet.

And as you mention below, this isn’t useful for arbitrary linear operations (many of them seem to be just as expensive on a quantum computer as on a classical computer) but there are certain known-to-be-useful linear operations that are extremely cheap to represent compared to what we know how to do on a classical computer.

Re: An Argument Against Quantum Computers

#49

Post by jcranmer »

codekilla wrote: post #32
jcranmer wrote: post #30

Earlier quoted context omitted.

That argument is patently wrong: it's the quantum bullshit fallacy. The point of the space argument I was making was that, if you need N bits of space to represent the input/output in classical computers, you should still need (I'm not sure if it's the case, but I don't see why it's not) Ω(N) qubits to do the same representation in a quantum computer. The quantum bullshit fallacy is that, since an entangled N-qubit i…

Honestly, I don't understand the point you are making. If you can explain to me how the Deutsch-Joza algorithm works without making reference to the fact that a function evaluation happens on a qubit in superposition(and thus an expanded state-space, as the simplest example), sure. I sincerely don't understand your points about classical simulation, or input/output in classical computers.

If you have an N-bit classical computer in a black box, you get at most 2^N possible outputs. If you have an N-qubit quantum computer in a black box, you can get at most 2^N possible outputs, not 2^2^N. We write the N-qubit registers as a vector of 2^2^N elements to make the math work, but measurement means we still can only distinguish between 2^N possible values.

Re: An Argument Against Quantum Computers

#50

Post by monktastic1 »

codekilla wrote: post #28
jcranmer wrote: post #25

Earlier quoted context omitted.

> If your vector space is too big to even represent in classical memory, you might still be able to work with it on a quantum computer. Quantum computers don't have any space advantage, I thought?

Imagine you have a classical bit string 0101, there are 2^4 possible different configurations of this string, and the classical computer will always exist in ONE of them. A quantum computer, with a qubit register 0101, can be put into a superposition state between all 4 qubits, where the state of the qubit register is ALL 2^4 different configurations simultaneously....now scale that up to 50-100-1000 qubits and you g…

Well, only in the same sense that the vector (1, 1) is "both (1, 0) and (0, 1) simultaneously." It's still a single vector in a 2^N dimensional space. It just happens to be expressed in terms of a basis that makes it look complicated.
Post reply on HN