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

21–30 of 67 posts

Re: An Argument Against Quantum Computers

#21

Post by Robotbeat »

frostburg wrote: post #17
Robotbeat wrote: post #15

Earlier quoted context omitted.

> That they will remain infeasible for a long enough time for traditional computers to catch up to it. Doesn't work for things we know are exponentially faster on quantum computers. Eventually, with enough (but not an absurd number) of bits, a decent quantum computer can solve problems that wouldn't be possible on a classical computer the size of the universe operating for billions of years. Improvements in algorithm…

We don't know of any such thing. There is nothing proven to be NP-hard that can be done in polynomial time with a quantum algorithm. Factorization isn't proven to be NP-hard.

/Proven/, sure. Hence the parenthetical "(etc)". As far as we know, however, factorization is not in P.

Re: An Argument Against Quantum Computers

#23

Post by ohazi »

stcredzero wrote: post #13

A note for the savvy: A quantum computer is not a magic bit-string that mysteriously flips to the correct answer. A n-qubit quantum computer is not like 2^n phantom computers running at the same time in some quantum superposition phantom-zone. That's the popular misconception, but it's effectively ignorant techno-woo. Here's what really happens. If you have a string of n-qubits, when you measure them, they might end…

https://www.smbc-comics.com/comic/the-talk-3

Re: An Argument Against Quantum Computers

#24

Post by pdpi »

goatlover wrote: post #18
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…

> Your answer doesn’t actually explain what we can do on a quantum computer that we can’t on a traditional computer. Why would there be anything you could compute on a quantum computer that you can't compute on a classical one (provided the classical one is powerful enough or given enough time for certain algorithms quantum computers are more efficient at). Is there speculation that a quantum computer could be used f…

"Solve problem x in polynomial time". AIUI, BQP is thought to be a superset of P and to include some stuff from outside NP. Specific problems that are part of BQP but that we expect are not in P is the interesting response here.

An example of such a problem is integer factorisation (see: Shor's Algorithm), which means that RSA and similar schemes might become vulnerable once suitably large quantum computers are available.

Re: An Argument Against Quantum Computers

#25

Post by jcranmer »

wyager wrote: post #14
stcredzero wrote: post #13

A note for the savvy: A quantum computer is not a magic bit-string that mysteriously flips to the correct answer. A n-qubit quantum computer is not like 2^n phantom computers running at the same time in some quantum superposition phantom-zone. That's the popular misconception, but it's effectively ignorant techno-woo. Here's what really happens. If you have a string of n-qubits, when you measure them, they might end…

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?

Re: An Argument Against Quantum Computers

#26

Post by codekilla »

stcredzero wrote: post #13

A note for the savvy: A quantum computer is not a magic bit-string that mysteriously flips to the correct answer. A n-qubit quantum computer is not like 2^n phantom computers running at the same time in some quantum superposition phantom-zone. That's the popular misconception, but it's effectively ignorant techno-woo. Here's what really happens. If you have a string of n-qubits, when you measure them, they might end…

I'm not sure it's useful anymore to point to quantum computers and say: 'Hey! You're not getting all your function evaluations back....so they're weak'. I feel this leads to misconceptions about quantum computing as well. You have to remember, the tensor product of N qubits is an exponentially expanding space...and the functions DO get evaluated in that space, the trick being you have to extract a JOINT property of the function evaluations, rather than the result of each one individually. Let's be clear, even with this caveat, the potential of quantum computing is enormous. I've personally read Kalai's papers and in my opinion, his objections boil down to 'it's just too good to be true'....but hey...we'll see :)

Re: An Argument Against Quantum Computers

#27

Post by btilly »

goatlover wrote: post #18
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…

> Your answer doesn’t actually explain what we can do on a quantum computer that we can’t on a traditional computer. Why would there be anything you could compute on a quantum computer that you can't compute on a classical one (provided the classical one is powerful enough or given enough time for certain algorithms quantum computers are more efficient at). Is there speculation that a quantum computer could be used f…

The fundamental observation behind quantum computing is that an irreversible bit flip releases a minimum amount of heat, while a reversible one releases none. See https://en.wikipedia.org/wiki/Landauer%27s_principle for the theoretical limits to classical computing based on this. But there are, to the best of our current knowledge, no theoretical limits to how much computation can happen reversibly.

However the requirement that the operations all be completely reversible is very strict. For example logic operations like "and" and "or" are off the table. BUT when physicists like Richard Feynman looked into, what DOES happen is that your computation can progress in a quantum superposition of states. And there is no upper limit to how many states are in the quantum superposition.

So in essence what you get should be a very hard to program but unbelievably parallel computer with no upper limit on computational speed.

The first demonstration that this could be useful for problems that people care about was https://en.wikipedia.org/wiki/Shor%27s_algorithm for factoring integers. The fact that we do not know how to factor integers quickly is an underpinning of public key cryptography algorithms like RSA. However we know how to solve that if we had a quantum computer. And this is just engineering, right?

Everyone recognizes that it is a very hard engineering problem. But the minority opinion laid out in this article is that the engineering problem is not just a practical problem, but the physics makes it intrinsically hard in a way that cannot ever be worked around. No matter how well a quantum computer works in theory, it is physically impossible for us to build and operate one that does better than the classical computers that we already know how to build.

Re: An Argument Against Quantum Computers

#28

Post by codekilla »

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?

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 get the idea. The quantum computer has a ridiculous advantage in terms of holding state spaces.

Re: An Argument Against Quantum Computers

#29

Post by cbHXBY1D »

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…

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

Re: An Argument Against Quantum Computers

#30

Post by jcranmer »

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…

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 is represented as a 2^N-dimension vector with complex arguments, it's really a computation on 2^N elements in O(1) time. The first sign that this is fallacious is that the basis here isn't of size 2^N but of size 2^N - 1. We're still only capable of reading N bits of information out of an N-qubit register; the fact that classical simulation requires a much larger state space to compute the probability doesn't mean that there's an inherent ability to freely vary through all of those states to represent the entire state space.

Post reply on HN