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

51–60 of 67 posts

Re: An Argument Against Quantum Computers

#51

Post by gji »

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.

Your first statement isn't quite true. See, for example, https://www.scottaaronson.com/blog/?p=473

In short, it's hard to classically model pretty simple quantum mechanical systems and sample the probability distribution of outcomes. Using a quantum computer to simulate the system and sample the probability distribution is easy.

Re: An Argument Against Quantum Computers

#52

Post by jcranmer »

wyager wrote: post #48
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?

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 st…

The essential problem with a quantum computer, as I understand is it, is that you can't actually read out the state you've created. Sure I can create a state which is an equal admixture of all 2^64 basis vectors, but if I try to look at it, I'm going to randomly end up with only one of the basis vectors.

Re: An Argument Against Quantum Computers

#53

Post by smallnamespace »

codekilla wrote: post #44
smallnamespace wrote: post #42

Earlier quoted context omitted.

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.

Let's say you have N qubits in a superposition.

A superposition is (a bit of an oversimplification since there are also complex numbers involved and a linear constraint) is in some sense a probabilistic distribution over the possible (classical) values that you get when you measure those N qubits.

E.g. if you measured this N-qubit state many times, which of the 2^(N-1) possible superposition values would you get? Would it be the uniform distribution? Biased towards particular classical bit patterns?

Note that there are 2^(N-1) possible classical bit patterns, so an arbitrary collection of these patterns would take O(2^N) operations to define.

> I'm definitely not saying you get the answer to every problem in a single evaluation step

Yes, but my point is that if your input is an arbitrary collection of classical N-bits, then in general you will require an exponential number of quantum operations to set stuff it into an N-qubit initial state, which means you get zero speedup.

Quantum computers only see speedup on inputs that require a relatively small number of quantum operations to set up. 'Small' could mean polynomial. But it's true that the space of 'easy to set up' initial N-qubit states is much smaller than the space of all possible N-qubit states, which is why a quantum computer cannot simply considered 'a magical computer that computes on 2^N bits at once' without considering how you get those bits in or out of the damn thing.

Re: An Argument Against Quantum Computers

#54

Post by smaddox »

kirrent wrote: post #41
smaddox wrote: post #31

Earlier quoted context omitted.

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. Als…

Perhaps I don't, but your description doesn't seem to contradict my point that scalability is distinct from competitive with classical computing. Perhaps people also implicitly mean "scales faster than a classical computer", in which case I did indeed misunderstand.

On the topic of whether or not the need for averaging is already accounted for in algorithmic complexity, my understanding is that it is not. This [1] preprint from 2006 seems to support my understanding. If you have evidence to the contrary, I would greatly appreciate a link.

[1] https://arxiv.org/pdf/quant-ph/0612077

Re: An Argument Against Quantum Computers

#55

Post by stickfigure »

tagrun wrote: post #38

This illustrates the disconnect of mathematicians trying to do physics. Not only his error model is unrealistic (you essentially need a frequency dependent power spectral density function to represent fluctuations in control which decays according to a power law at high frequencies, sometimes called 1/f noise but the power doesn't have to be 1; also you don't get that kind of strong spatial correlations in real syste…

Geezus. I have a degree in CSC from an engineering college. I did well in both math and physics; hell, I even enjoyed them. I've been working professionally for 25 years (with considerable success!).

I'm not sure if I could distinguish what you just said from a markov-chain-based paper generator.

I feel old.

Re: An Argument Against Quantum Computers

#56

Post by deepnotderp »

btilly wrote: post #27
goatlover wrote: post #18

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. 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 requi…

Okay, first of all, we are no where near Landauer's Limit right now, and will likely never reach that point because we'll run into thermal noise "danger zones" far before then.

Second of all, there are plenty of (and probably the primary ) forms of non-quantum reversible logic.

In the slightly less exotic category there is also adiabatic computing which can actually be done in standard CMOS in most flavors.

Re: An Argument Against Quantum Computers

#58

Post by lmm »

jcranmer wrote: post #52
wyager wrote: post #48

Earlier quoted context omitted.

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 st…

The essential problem with a quantum computer, as I understand is it, is that you can't actually read out the state you've created. Sure I can create a state which is an equal admixture of all 2^64 basis vectors, but if I try to look at it, I'm going to randomly end up with only one of the basis vectors.

Sure, but you might be able to perform some computation that involves those 2^64 possible states that ends up with some determined state that you can reliably measure. So while you can't store 2^64 classical values in one quantum bit, nor can you necessarily simulate that quantum bit exactly with even 2^64 classical values.

Re: An Argument Against Quantum Computers

#59

Post by wyager »

jcranmer wrote: post #52
wyager wrote: post #48

Earlier quoted context omitted.

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 st…

The essential problem with a quantum computer, as I understand is it, is that you can't actually read out the state you've created. Sure I can create a state which is an equal admixture of all 2^64 basis vectors, but if I try to look at it, I'm going to randomly end up with only one of the basis vectors.

That’s why quantum algorithms try to bring the final result down to (mostly) a combination of only a few standard basis states.

Re: An Argument Against Quantum Computers

#60

Post by pankajdoharey »

I dont buy this argument, for one reason and one reason alone. When we started integrating silicons we had similar problems of noise and distortion due to circuits packed so close. There was always scope for corruption of signals and then the problem got amplified when these circuits started working at higher frequencies. A high end processor these days could be 4Ghz, such a high frequency data transaction already creates distortion, so we employed many schemes to circumvent these things most notably using different wire interconnects, going smaller and using various chemical shielding. His key argument revolves around noise/distortion which is not a good argument. If the math doesn't work then its a real problem. Also massiveness argument is also not correct because it was given for computers aswell that we will never be able to build smaller computers and yet we did.
Post reply on HN