Hacker News Reader

Comment by saycheese | Hacker News Reader

Putting aside speed, what is possible in quantum computing that's not possible in classical computing?

It's not a question of possibility, but rather speedup. The three "flagship" algos are for unstructured search[1] (not clear if really useful), factoring[2] (useful to crack public key crypto), and more recently there is a result that shows that random instances of general linear problems can be solved faster[3].

Another class of algorithms use quantum computers as simulators (e.g. for chemical simulations). You can also encode certain optimization problems as "constraints" in a quantum system and hope that quantum dynamics will find good solutions to the optim. problem faster.

[1] https://en.wikipedia.org/wiki/Grover%27s_algorithm

[2] https://en.wikipedia.org/wiki/Shor%27s_algorithm

[3] https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_s...

Grover's algorithm is also (theoretically) used for breaking symmetric crypto, by halving the exponent needed in brute force search. It's the main reason to move from 128-bit ciphers to 256 bit.

> It's not a question of possibility

Yeah it really is. Quantum states just do not even fit in classical memory. Like, exponentially so. The parent was specifically asking about "possibility" not speedup.

That's just a matter of speed no? It's not an impossibility result like Turing's; classical computers can compute whatever quantum computers can. That's the Church-Turing hypothesis.

It's just a matter of speed, but there's no need to invoke the Church-Turing hypothesis.

One of the first things proven[1] about BQP is that it's contained in P^#P, which is contained in PSPACE. That means a Turing machine can simulate any quantum computer with only polynomial space (but possibly very slowly).

[1] http://epubs.siam.org/doi/abs/10.1137/S0097539796300921

I think I was using the argument that Quantum computation is Turing complete, which is why they can only compute what classical computers can.

Apart from speed the only other thing is memory. And yes, for example simulating a quantum system takes exponentially much classical memory (just to store the state of the system). This is one of the proposed killer apps for quantum computing.

I am not involved in quantum computing at all, and only have read a few articles, but my understanding is:

Calling it a speed up is kinda correct but seems slightly wrong to me. It is a completely different computing model which tends to use different algorithms that make solutions to certain problems feasible on a quantum computer that aren't on an equally powered classical computer. That is why it's so powerful, but at the same time, classical computing could stay "faster" than quantum computing for a long time, or even forever.

IANAPhysicist, but the analogy I use for my relatives is that electronic->quantum is similar to the jump from clock-work->electronic.

Most concepts carry over, but some just don't make sense anymore, and a lot of effort must be invested into fundamentally new click-clack (or zip-zap) arrangements to get things done. A large part of the "intelligence" in the final system is actually latent in its structure.

The way I understand it, quantum speedup simply means that the set of candidate solutions for a problem contained in BQP are more accurate over time.

Some problems can be solved immediately, in a single clock cycle, that are intractable for a traditional CPU. For example, cracking RSA encryption.

This is not even remotely close to being true. Shor's algorithm runs in polynomial time.

> single clock cycle

What does this even mean in this context?

My understanding (which is limited!) is that there are some apparently NP-complete problems that are P for a quantum process.

Now, it may be that these problems were never actually NP-complete, but are a superset of P for quantum computers.

Or it may be that quantum computers can really solve some NP-complete problems in P time.

Either way though, it isn't a consequence of CPU-cycles per se, but the underlying mathematical distinction (ie, what a silicon vs quantum computer does, not what it can do in a "cycle").

If quantum computers could solve NP-complete problems efficiently, the entire community would astounded.

As it stands, quantum computers can solve some problems faster than classical computers currently can; factorisation, discrete log and other problems with a particular kind of repeated structure are some such problems. However, we do not know for certain that these problems are not efficiently solvable using classical computers (I'd bet that factorisation will be put in P within my lifetime).

A big goal of the QC community is to demonstrate quantum supremacy: to unconditionally show that quantum computers can solve a problem with fewer resources than classical computers. We've made progress on this (check out Scott Aaronson's blog for more info), but still haven't achieved it.

Lastly, a small nitpick. "P time" is not a meaningful phrase; P is a complexity class consisting of problems solvable efficiently (i.e., in polynomial time) on classical computers.

The class of efficiently solvable problems on quantum computers is BQP: Bounded-error Quantum Polynomial-time, which means that BQP is the class of problems that are efficiently solved by a quantum computer, but only with some probability bounded away from 1/2. This means the QC can return incorrect answers, but there are techniques to reduce the error probability to extremely small values.

The classical analogue of this class is BPP, which is Bounded-error probabilistic poly-time. There's a conjecture that BPP=P, and if we have any sort of crypto then the conjecture is true.

Limited indeed. If nothing else, I'd suggest reading <http://www.scottaaronson.com/democritus/>. In short:

> there are some apparently NP-complete problems that are P for a quantum process

The definition of P refers to deterministic machines; no quantum. 'P for a quantum process' is a meaningless phrase. Problems solvable in polynomial time by quantum computers are contained in the classes EQP (if the answers are to be always correct) and BQP (if the answers are to be correct with a probability which may be made as high as desired).

> it may be that these problems were never actually NP-complete, but are a superset of P for quantum computers.

'NP-complete' is not an exact synonym of informal concepts like 'hard' or 'intractable'. It has a precise definition: NP-complete problems are those for which are simultaneously NP (the solution can be verified in polynomial time) and NP-hard (every instance of any NP problem can be reduced in polynomial time to it). There are problems that have been proved NP-complete. For others there are no known polynomial time algorithms, but they are suspected not to be NP-complete either. If P = NP, the notion of NP-completeness becomes trivial and equivalent to simply being in P. There's no way a problem now known to be NP-complete will later be shown not to be.

> Or it may be that quantum computers can really solve some NP-complete problems in P time.

This has not been proved false, but generally considered unlikely. (Also, 'some NP-complete problems' would imply 'all of them', by the definition of NP-completeness.)

Awesome - you have upgraded me today.

Reply on news.ycombinator.com