31–40 of 41 posts
>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…
>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…
Oh?
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.
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'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.
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 )…
For the benefit of us with a poor intuition, do you mind walking us through how you arrived at your conclusion?
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.
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.
How to efficiently simulate a quantum circuit? Badum ching I'll be here every night, ladies and gents.
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.
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