11–20 of 41 posts
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.
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
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.
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.
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 .
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 )…
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.
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.
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.
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 )…
I'll be here every night, ladies and gents.
How to efficiently simulate a quantum circuit? Badum ching I'll be here every night, ladies and gents.