A Problem That Only Quantum Computers Will Ever Be Able to Solve | Hacker News Reader

A Problem That Only Quantum Computers Will Ever Be Able to Solve

quantamagazine.org

84 pointsjonbaer32 comments

This is basically the TCS version of a clickbait headline. It's a separation of BQP and PH by an oracle. Certainly a nice result, but to put it into context, we also have a separation of P and NP by an oracle. Yet, we are very far away from actually proving that P and NP are distinct.

We need to do something about clickbait.

We need to stop upvoting it.

Any time I hear something sensational about quantum computing, I check Scott Aaronson's blog for the real story. Here's his blog post on this topic: https://www.scottaaronson.com/blog/?p=3827.

Good suggestion; TLDR:

> Since (despite my journalist moratorium) a journalist already emailed to ask me about the practical implications of the BQP vs. PH breakthrough—for example, for the ~70-qubit quantum computers that Google and others hope to build in the near future—let me take the opportunity to say that, as far as I can see, there aren’t any.

That webpage is the hardest thing to read on a phone screen. Dark grey on black, why would he ever think that's a good choice??

I think the white box behind the text must not have loaded on your phone. Looks fine to me.

I really like Scott Aaronson's writing, but I find that blog post pretty impenetrable.

Thank you a lot!

My first thought was "Oh, I have forgotten the address of that nice blog of that Prof. with all kind of interesting CS stuff that shows 'NP' and 'BQP' and 'P' connected with lines in the right upper corner. That blog will likely have more useful insights. How to find that blog again? I have so many bookmarks and not all tagged correctly, hmm".

But after reading the article and coming back here there is the right link near the top! :-)

People on HN are so great, love that! (Especially when they think in the same direction as me^^).

In fact, we have an oracle that separates P from NP and another through which P=NP. This is why tackling P vs NP via oracles is an abandoned strategy.

True. This makes me wonder if there's an oracle relative to which BQP = PH?

This article makes it seem like the problem that separates BQP and PH is one the classical computers literally cannot solve, given any amount of time. I don't believe that is actually what's going on. If it were the case, this result would have falsified the Church Turing Thesis, and there would be a lot more hype around this.

Please correct me if I'm wrong.

P != quickly solvable by a classical computer.

P means solvable in polynomial time relative to the size of the problem, which could still take longer than the universe has existed

Given that computer scientists use the word "efficiently" to mean "in polynomial time", I'm not too upset at using "quickly" to mean the same.

Idk, I majored in CS and I don't use the term efficient or quick to imply relative asymptotic time complexity.

Consider for example a randomized quicksort (O(n^2) worst case) is often faster than say mergesort (O(nlog(n)) worst case)) for small lists due to reduced overhead. I know these are both polynomial, but relatively speaking, randomized quicksort can be more efficient & quick.

In the real world we can make certain assumptions about our problem domain, where the most 'efficient' solution for your business problem may not have the smallest asymptotic time complexity.

Maybe it's fair to assume everyone reading this article knows what the auther means & i'm just being that guy, but I still don't like ambiguity lol

It's used when talking about the extended Church-Turing thesis [1]:

> "A probabilistic Turing machine can efficiently simulate any realistic model of computation." The word 'efficiently' here means up to polynomial-time reductions.

Real-world efficiency doesn't necessarily factor into what theoretical computer scientists are interested in.

[1] https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

>The actual best way to distinguish between complexity classes like BQP and PH is to measure the computational time required to solve a problem in each. But computer scientists “don’t have a very sophisticated understanding of, or ability to measure, actual computation time,” said Henry Yuen, a computer scientist at the University of Toronto.

>So instead, computer scientists measure something else that they hope will provide insight into the computation times they can’t measure: They work out the number of times a computer needs to consult an “oracle” in order to come back with an answer. An oracle is like a hint-giver. You don’t know how it comes up with its hints, but you do know they’re reliable.

This is not how it works, at all.

Oh?

1. You don't measure the number of steps, you prove that it's bounded by some function of input length.

2. You don't work off number of oracle calls, but number of total steps with an oracle call counting as one step.

Thanks for expounding.

Can't quantum computers be simulated on classical computers? Doesn't that mean that any problem solvable by a quantum computer can be solved by a classical computer, given enough resources? If so, isn't the headline that "Only Quantum Computers Will Ever Be Able to Solve" misleading?

I don't know much about this subject, so I'm assuming one of my assumptions is wrong.

> Can't quantum computers be simulated on classical computers?

The simulation gets exponentially slow, to the point that the fastest classical computers we have are not practical for simulating even modestly sized quantum systems.

Regarding (a), the approximation can be made as good as you want. However you are right on (b) it gets exponentially slow.

They can be simulated on classical computers, but in exponential time. In general, you need 2^n bits to represent n qubits.

You can see this in the case of a basic quantum gate, the hadamard gate:

H(a) produces a qubit with equal probably of being 1 or 0 if observed; H(H(a)) will always return the original value of A. Doing this to an entangled vector of qubits, performing another transform, then hadamard again produces a quantum circuit that takes an impractical number of classical bits to simulate.

Yes; the title should probably include the word "efficiently."

  Imagine you have two random number generators, each 
  producing a sequence of digits. The question for your 
  computer is this: Are the two sequences completely 
  independent from each other, or are they related in a 
  hidden way?

That, right there, should tell absolutely everyone, by intuition alone, that, despite assurances from industry experts that flaws leading to breaks (plain-text discovery faster than brute force) are universally impractical, even with all the energy of a dyson sphere, that there are classified equations for back doors baked into all modern, commercially used civilian/consumer-grade cryptographic algorithms.

I'm not 100% sure which side you are taking, but I think you are saying all common crypto is backdoored. That seems like a giant logical leap with absolutely no hints as to why you landed at that conclusion based on your quote.

For the benefit of us with a poor intuition, do you mind walking us through how you arrived at your conclusion?

How to efficiently simulate a quantum circuit? Badum ching

I'll be here every night, ladies and gents.

Your comment has won the Internet. Now, let's see you stuff it in a bag and carry it home.

If you can prove that simulating a quantum circuit cannot be done in P, that's a breakthrough you should publish. I'm 80% sure that even if you prove it's not in PH, you'll be the first.

Quantum computing is coming. How quickly isn’t clear, although the first versions of this technology are expected to begin showing up over the next few years, with the rollout across more markets and applications expected by the middle of the next decade. https://semiengineering.com/quantum-computing-becoming-real/

Reply on news.ycombinator.com