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

61–67 of 67 posts

Re: An Argument Against Quantum Computers

#61

Post by codekilla »

smallnamespace wrote: post #53
codekilla wrote: post #44

Earlier quoted context omitted.

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? Wou…

> 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

Can you provide a reference for this? My understanding is that you can efficiently setup qubits using a hadamard transform

Re: An Argument Against Quantum Computers

#62

Post by smallnamespace »

codekilla wrote: post #61
smallnamespace wrote: post #53

Earlier quoted context omitted.

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? Wou…

> 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 Can you provide a reference for this? My understanding is that you can efficiently setup qubits using a hadamard transform

Yes, but the Hadamard transform is essentially a linear operation.

The span of qubit states reachable in a polynomial number of Hadamard transform operations from the starting state is much less than all possible qubit states.

This follows immediately from information-theoretic principles. There are 2^(2^N-1) possible 'collections' of 'classical bits' representable by N qubits. Therefore it takes 2^N-1 bits of information to represent, but since the Hadamard transform is basically linear, we can see (in a very handwavy way) that only a polynomial number of possible states is reachable from a polynomial number of quantum gate operations.

Re: An Argument Against Quantum Computers

#63

Post by codekilla »

smallnamespace wrote: post #62
codekilla wrote: post #61

Earlier quoted context omitted.

> 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 Can you provide a reference for this? My understanding is that you can efficiently setup qubits using a hadamard transform

Yes, but the Hadamard transform is essentially a linear operation. The span of qubit states reachable in a polynomial number of Hadamard transform operations from the starting state is much less than all possible qubit states. This follows immediately from information-theoretic principles. There are 2^(2^N-1) possible 'collections' of 'classical bits' representable by N qubits. Therefore it takes 2^N-1 bits of inform…

This is verbatim from 'Explorations in Quantum Computing' by Colin P. Williams: "The utility of the Hadamard gate derives from that fact that by applying, in parallel, a separate Hadamard gate to each of n qubits, each initially in the state |0⟩, 1 H|0⟩⊗H|0⟩⊗···⊗H|0⟩= √ |j⟩ (2.20)

we can create an n-qubit superposition containing 2n component eigenstates. These eigenstates represent all the possible bit strings one can write using n bits. The importance of this capability is often overlooked. But, in reality, it is one of the most important tricks of quantum computing as it gives is the ability to load exponentially many indices into a quantum computer using only polynomially many operations. Had Nature been unkind, and had we had to enter the different bit-strings individually, as we do in classical computing, then quantum computing would have had far less potential for breakthroughs in computational complexity."

I'm just talking about loading a quantum register, there are other issues with gate times and decoherence.

Re: An Argument Against Quantum Computers

#64

Post by kirrent »

smaddox wrote: post #54
kirrent wrote: post #41

Earlier quoted context omitted.

'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] pr…

Shor's original paper discusses the fundamental need for several runs and gives the time complexity.

https://arxiv.org/pdf/quant-ph/9508027.pdf

The paper you linked to is just saying that the need for several runs and 2006 readout error rates together led to awful scaling (though still better than classical factorisation). That isn't surprising. Error rates in all parts of even modern quantum computers are still too high to scale well. Especially when repetition is called for.

Ultimately, complexity is calculated using logical qbits. Kalai doesn't think that even with error correction codes we can get close enough. Most other people think we can. That paper you linked to is just making the point that we're definitely not there yet. When we do, algorithms in BQP will still need several runs on many algorithms (the exact same way as algorithms in BPP do) but that should already be incorporated into those algorithm's complexity.

Re: An Argument Against Quantum Computers

#65

Post by kirrent »

kirrent wrote: post #64
smaddox wrote: post #54

Earlier quoted context omitted.

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] pr…

Shor's original paper discusses the fundamental need for several runs and gives the time complexity. https://arxiv.org/pdf/quant-ph/9508027.pdf The paper you linked to is just saying that the need for several runs and 2006 readout error rates together led to awful scaling (though still better than classical factorisation). That isn't surprising. Error rates in all parts of even modern quantum computers are still too…

*Kalai doesn't think that even with error correction codes we can get sufficiently close to a logical qbit.

Re: An Argument Against Quantum Computers

#66

Post by [deleted] »

codekilla wrote: post #63
smallnamespace wrote: post #62

Earlier quoted context omitted.

Yes, but the Hadamard transform is essentially a linear operation. The span of qubit states reachable in a polynomial number of Hadamard transform operations from the starting state is much less than all possible qubit states. This follows immediately from information-theoretic principles. There are 2^(2^N-1) possible 'collections' of 'classical bits' representable by N qubits. Therefore it takes 2^N-1 bits of inform…

This is verbatim from 'Explorations in Quantum Computing' by Colin P. Williams: "The utility of the Hadamard gate derives from that fact that by applying, in parallel, a separate Hadamard gate to each of n qubits, each initially in the state |0⟩, 1 H|0⟩⊗H|0⟩⊗···⊗H|0⟩= √ |j⟩ (2.20) we can create an n-qubit superposition containing 2n component eigenstates. These eigenstates represent all the possible bit strings one c…

[deleted]

Re: An Argument Against Quantum Computers

#67

Post by tagrun »

stickfigure wrote: post #55
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.

You're probably around the same age as me then.

I wouldn't expect you to be familiar with it unless you've actually worked in the academia doing research quantum information. This isn't stuff we teach in class at all, even to PhD students, it's a part of research.

It'll also probably read like "from a markov-chain-based paper generator" to you too, but if you're interested about how actual noise behaves, you can read this for example: https://www.nature.com/articles/nphys1994 (arxiv link if you don't have access: https://arxiv.org/abs/1101.4707)

While it's about flux qubits, the 1/f behavior is almost universal in all current promising candidates, and DD virtually works in all quantum computers.

Post reply on HN