Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

quantamagazine.org

Post reply on HN
Print view View original

1–10 of 41 posts

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

#2

Post by fyi1183 »

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.

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

#3

Post by wintorez »

fyi1183 wrote: post #2

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.

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

#5

Post by evanpw »

fyi1183 wrote: post #2

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.

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.

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

#6

Post by utopcell »

fyi1183 wrote: post #2

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.

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.

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

#7

Post by [deleted] »

wintorez wrote: post #3
fyi1183 wrote: post #2

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.

[deleted]

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

#8

Post by transmissible » 

  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.

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

#9

Post by theptip »

evanpw wrote: post #5
fyi1183 wrote: post #2

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.

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.

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

#10

Post by supermdguy »

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.

Post reply on HN