It's always O(20years), because you have to wait for the hardware to be created.
4 months ago | 7,000
I love how i was all proud that i took ONLY 5 minutes to read and understand the first part, only to read "quantum computer" and have no idea what he is talking about
4 months ago | 9,500
The answer is obviously a superposition of all four options, at least until your upcoming video collapses the wave function.
4 months ago | 5,000
There are some added details to make this a coherent question, namely specifying how that block box function would look for the quantum computer, or for that matter even defining what a quantum computer is! All that will be in the coming video, but I'm curious to get people's gut reactions to the (admittedly vague) question.
4 months ago | 2,300
THIS IS GROVER'S ALGORITHM there's a way for quantum computers to take an in a starting system where all the numbers have an equal probability of being the answer, this is called a superposition through a mix of constructive interference and amplification of the probability of the correct answer, you will eventually transform the state into a new system where the correct answer has the highest probability and the other's have a very low probability This is done several times to sufficiently increase the correct number's probability and decrease the incorrect numbers, and it turns out, the optimal number of times is a quadratic speedup over the classical method, and the algorithm returns the correct value in O(sqrt(N)) time! I love Quantum Computing :)
4 months ago | 1,900
... depends on how terribly the quantum computer is coded. looking at the total time, around O(n^n) for debugging
4 months ago | 2,200
O(1) would be wild. People have way too high expectations for quantum computers.
4 months ago | 931
@3blue1brown Could you add an "I don't have a clue" option in future? Otherwise it'll tilt the stats.
4 months ago | 398
Order of square root of N. This is just Grover’s Algorithm. For those who think O(1), there is one primary thing to understand. If you think quantum computers work by trying all possible paths at the same time and picking out the right solution, you’re wrong. It’s far more subtle than that.
4 months ago (edited) | 287
My guess is currently the most popular choice, which has immediately cratered my already low confidence in it.
4 months ago (edited) | 73
A quantum computer using Grovers algorithm needs only sqrt(N) iterations compared to a regular computer to brute-force a sequence of numbers. This phenomenon is called quadratic speedup and is one of the particular reasons quantum computers may help us in science.
4 months ago | 245
My research is in quantum computing, so I'm really excited for this upcoming video on Grover's search! My first ever quantum algorithm I designed was to find palindromic bit strings with it. Good memories!
4 months ago | 41
In quantum computing, the problem is that, at any time, the machine can be O(N) or O(FF).
4 months ago | 38
O(sqrt(N)) - I don’t know much about quantum computing but my reasoning is that if we’re still using the binary system - then each bit can be both 0 and 1 at the same time - so we should be able to figure out the correct number with a linear scan on the bits - the number of bits needed is about sqrt(N) for N
4 months ago | 5
I work in quantum cryptography and do a fair bit of sci-com so the vote spread here is so interesting to me
4 months ago | 13
I feel like the poll is missing O(N) as an answer option. Here is my reasoning: You can’t determine the answer if you don’t process at least N-1 possible values. If we are guaranteed that at least 1 value gives true. Now let’s say that the hardware has K modules for processing data. Or just take K as the number of wires that can transfer data from memory. Then we can process all of the options in about (N-1)/K cycles (multiplied by the function evaluation time). So can’t do better than O(N), since we need to load at least O(N) values and process them in some way.
4 months ago (edited) | 5
I'm guessing it's O(1) because you can just have a single wavefunction operation, but if you count each entanglement as an operation then it would be the ceiling of log base 2 of n
4 months ago | 0
How would a quantum computer interact with you blackbox? It still has to make N calls to your classical(?) blackbox. So wouldn’t the time complexity be O(N)?
4 months ago | 7
3Blue1Brown
Pop quiz time! Try to answer without looking it up.
Suppose I have a mystery function, and I tell you that there’s some secret value among all the numbers from 1 to N, where if you plug that value into my function, it returns True, otherwise, it returns false. For example, maybe it simply looks something like "f(n): return (n == 123)". But you can't see the inside of the function; it's a black box.
How long does it take to find this secret value? For a classical computer, there's no better method than to guess and check all N possibilities. Sometimes you're lucky and get it early; sometimes you're unlucky, and it takes closer to N; on average, it's N / 2. In CS, we call that an O(N) run time, disregarding the constant because we just care about how things scale as N grows.
Here's your quiz: How long would it take a quantum computer to do the same task?
4 months ago | [YT] | 6,266