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.
> 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.
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^^).
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.
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.
It's probably something about seemingly random nonce generation being (selectively) not-so-random after all.
The "not-so-random-but-seemingly-unrelated" nonces possessing relatable properties that permit discovery of secret keys, through little known, obscure relationships, preferably difficult to establish computationally, thus placing them on a shelf that not only few would look for, but also few could reach.
With this capacity to force the selective production of relatable private keys, given a public key generated according to said relationship, only a small audience would know to search for the related private key.
Ideally, the production of linked, discoverable public/private key pairs would be the default for the open public, and thus a deniable "accident" but with options to enable select, preferred chipsets (e.g. intel/amd brand only) to activate buses that will produce hardened, secure, unrelatable keys to those that have extra solder in all the right places.
Meanwhile, figure everything focuses on primes for integral quotients to prove clear relationships in most crypto problems, because it's easiest to reason correctness, so stacking tons and tons of layers on top of a desirable quotient will usually obscure such a fact from most snoops.
But, now we have new technology which binds massively parallel calculations (mostly by way of fast fourier transforms) to speed-of-light waveform oscillations. Such calculations that were not previously trivial, are reduced to, perhaps smallish functions with only the number of iterations to perform-and-test-output, before returning.
Determining whether the introduction of quantum computing is the only way such back doors could possibly be exposed to the general public, would be a necessity, prior to making advanced technology widely available.
If it does result in a high probability of exposure, then a narrative of controlled exposure also needs to be crafted, so that the old back doors can be retired in an orderly fashion, while ramping up new covert information vectors compatible with powerful quantum waveform calculations that put an exponentially larger amount of calculation cycles in the hands of civilians, which were previously unavailable with 20th century solid state electronics. Whether people have a clue how to use all those extra cycles or not.
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.
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.
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/
>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 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.
40 comments
[ 2.4 ms ] story [ 93.9 ms ] thread> 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.
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^^).
P means solvable in polynomial time relative to the size of the problem, which could still take longer than the universe has existed
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
> "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
Probably.
The "not-so-random-but-seemingly-unrelated" nonces possessing relatable properties that permit discovery of secret keys, through little known, obscure relationships, preferably difficult to establish computationally, thus placing them on a shelf that not only few would look for, but also few could reach.
With this capacity to force the selective production of relatable private keys, given a public key generated according to said relationship, only a small audience would know to search for the related private key.
Ideally, the production of linked, discoverable public/private key pairs would be the default for the open public, and thus a deniable "accident" but with options to enable select, preferred chipsets (e.g. intel/amd brand only) to activate buses that will produce hardened, secure, unrelatable keys to those that have extra solder in all the right places.
Meanwhile, figure everything focuses on primes for integral quotients to prove clear relationships in most crypto problems, because it's easiest to reason correctness, so stacking tons and tons of layers on top of a desirable quotient will usually obscure such a fact from most snoops.
But, now we have new technology which binds massively parallel calculations (mostly by way of fast fourier transforms) to speed-of-light waveform oscillations. Such calculations that were not previously trivial, are reduced to, perhaps smallish functions with only the number of iterations to perform-and-test-output, before returning.
Determining whether the introduction of quantum computing is the only way such back doors could possibly be exposed to the general public, would be a necessity, prior to making advanced technology widely available.
If it does result in a high probability of exposure, then a narrative of controlled exposure also needs to be crafted, so that the old back doors can be retired in an orderly fashion, while ramping up new covert information vectors compatible with powerful quantum waveform calculations that put an exponentially larger amount of calculation cycles in the hands of civilians, which were previously unavailable with 20th century solid state electronics. Whether people have a clue how to use all those extra cycles or not.
Probably.
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.
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.
I'll be here every night, ladies and gents.
>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.
2. You don't work off number of oracle calls, but number of total steps with an oracle call counting as one step.
Please correct me if I'm wrong.