I don’t know how any experiment like this could be taken seriously. Your action could change 15 minutes apart if you feel like having sugar, if the guy felt intimidating or not, if the last thing he said seemed friendly or if his facial expression was off at the very end, etc.
There must be a better way of judging the validity of a social experiment using first principles. There’s a huge psychological side that people completely ignore.
I’m not sure how interesting this is - of course rotation causes the paths to differ and become measurable.
I’ve been wondering about sending photons away from earth and having their paths bend due to gravity (and later have them interfere). That would be interesting because GR would be involved.
I was thinking of creating something like this but centered around posting one’s intuitions on research, instead of the papers themselves (which are hard to read, even the list of titles are hard to parse). But researchers are afraid to say anything stupid and would prefer saying nothing at all.
It’s a hard problem but could be a good platform for research discussions considering none exists today. Best of luck.
I just wanted to comment on how good the homepage is - it's immediately clear what you do. Most people working with "combinators" would feel a need to use lots of scary lingo, but OP actually shows the simple idea behind the tool (this is the opposite take of most academics, who instead show every last detail and never tell you what's going on). I really appreciate it - we need more of this.
A powerful method in math is to assume the thing you're looking for is continuous, in which case you can write it F(n) = a0 + a1 n + a2 n^2 + ... .
You can solve Fibonacci by writing it as
a0 + a1 n + a2 n^2 + ...
= a0 + a1 (n-1) + a2 (n-1)^2 + ...
+ a0 + a1 (n-2) + a2 (n-2)^2 + ...
Expand terms, then match the n, n^2, n^3 etc terms and solve for a0, a1, a2, etc. This works in solving differential equations too - it's called "Method of Frobenius" (easier in diffeq because you don't have to do annoying binomial coefficient math).
Yep, they're essentially giant brute force machines. You can find the period of a function by passing all the inputs through it at once and destructively interfering the result.
Why is there a speedup in quantum, though? Why can't you just brute force classically? The answer is that whether quantum or classical, you can always build a hard-coded circuit that essentially swaps the time and space complexity - just make it so that for every operation you were doing in time, instead, every operation happens at its own place in space.
Quantum is special because it also takes the "log" of the space complexity b/c n qubits represent 2^n bits. So quantum lets you swap space with time and then take the log of time, lol. Superposition, interference, etc aren't really even needed in the explanation.
Correct - superposition doesn't fork the world - measurement does. And correct, you can't communicate with the other universe after the split has happened [1]. I'm glad you mentioned that quantum computers can't solve NP-complete problems - my next blog post was going to be about why. Here's an overview of what I plan on saying:
A typical quantum algorithm like Shor's works by sending every possible input through a gate, and so you get every possible output out in a superposition. If you were to just measure that, you'd get a random result - so instead, you need to somehow interfere the output to get the actual result. You do this by taking advantage of the fact that the superposition is a periodic function and the amplitude repeats. This is literally the core assumption of the algorithm.(a common way of doing this using the QFT).
Every quantum algorithm requires some kind of structure in the output like this. Deustch's algo, dumb ones like Simon's algo, etc. NP-Complete problems have no structure to them, so even if you build a gate that creates the superposition you want, it's not possible to destructively interfere it to get an answer (I don't know how to prove that there's no structure to NP-Complete outputs - it just feels trivial, since they're only solvable in exponential time, so there must be an exponential amount of "structure" there).
---
[1] The only way to communicate with the other universe would be to try to use quantum mechanics with something like an entangled pair. But no information can be communicated through an entangled pair if all you just have 1 of the 2 particles! Measurement collapses a state nonlocally, and if you could somehow measure one particle and change the probability distribution of the other, you'd be communicating faster than light. The measurement genuinely changes the state and the amplitudes, but not in a way that the other person can detect. It's really interesting and leads to stuff like teleportation.
Since quantum computers can stimulate classical computers, presumably they can solve NP-complete problems, since classical computers, by definition, can. Perhaps you mean that they can’t solve NP-complete problems in polynomial time, but we don’t even know that of classical computers, so you would presumably have shown that P≠NP, which would be fairly impressive.
So you're nitpicking it for being too strong of a statement and too weak of a statement at the same time?
How about this, they can't do the thing NP stands for. They can't run a generic polynomial-time algorithm in a nondeterministically-branching way, and then pick the winner.
I considered multiple readings of the claim. Obviously different readings may differ in strength. I do not exclude a reading that is neither too strong nor too weak; the comment is an invitation to give one, which you appear to have taken up.
I do not see the distinction between what you have written in the second paragraph and the claim that P≠NP.
If P=NP, then there must exist a deterministic polynomial solution for any NP problem.
Because it is deterministic, that means it's using a different algorithm than the straightforward nondeterministic solution.
So any Turing machine can solve the problem, but it will have to use the former algorithm. It can't use the latter algorithm.
A lot of people think of quantum computers as basically a nondeterministic Turing machine, and the wording in the parent post is an attempt to correct that misconception.
Well, I also suspect BQP≠NP, but we don’t know that yet either.
I still don’t understand what is meant by ’straightforward nondeterministic solution’. If you mean that QTMs or quantum circuits aren’t formally the same as NTMs, I agree. But nor are two-tape (D)TMs and single-tape DTMs, and yet we have linear speedup. Presumably there is a stronger claim here, but I do not understand what that is.
> I still don’t understand what is meant by ’straightforward nondeterministic solution’.
I'm not sure how much better I can phrase it than "run a generic polynomial-time algorithm in a nondeterministically-branching way, and then pick the winner."
Let me lay out a scenario:
You have a problem with 2^n potential answers.
You have a fast polynomial algorithm you can apply to each potential answer, and you want to find the right answer.
A lot of people think that if you use a quantum computer, it will check every answer in parallel and quickly find the answer at polynomial speed.
But it doesn't work like that. To some extent it does check every answer in parallel, but you need to do a lot more to make the correct answer show up out of the noise. Let's say you need to use Grover's algorithm. That cuts 2^n down to 2^(n/2), which is a remarkable speedup but it's still exponential.
It's possible that P=NP and there's a totally different solution for both classical and quantum computers that isn't exponential. But that's a side issue. The important thing here is that it's not being quantum that lets you escape exponential purgatory.
> If you mean that QTMs or quantum circuits aren’t formally the same as NTMs, I agree.
Kind of?
But it's not really about formal equivalences. It's that tons of people think a QTM is literally a NTM.
I believe that it is an open question. Were I a betting man, I’d bet that P≠NP. I believe it would also be significant to show that P≠NP implies BQP≠NP but that may already be known.
Where is the best place a layman can dig into this statement “You do this by taking advantage of the fact that the superposition is a periodic function and the amplitude repeats.”? I’ve seen articles hinting at this in an obtuse way but I’d love to see something more approachable to help wrap my head around it.
I just tried finding a good resource and I can’t. All of them are mile long page scrolls… I don’t know how they have so much stuff to spew. Qiskit had amazing lessons with cool illustrations (although they did spew at the end) but I can’t even find that anymore on their site.
Don’t worry though, even the professional researchers I’ve worked with think it’s a waste of time. The field is screwed.
Here’s a quick explanation from me-
The state |x> means you have some qubits that represent the number x. Say you want to represent the number 13, that just means you have |1,0,1,1>, it just means you have 4 qubits in this configuration (quits can be 0 or 1). It’s also written |13>. If you want the state “13 AND 14 AND 15” in superposition where qubits are both 0 and 1, that’s represented by |1,0,1,1> + |1,1,0,0> + |1,1,0,1>. It’s in that superposition and can interact with itself until you choose to measure it. When you do go to measure it, you might measure any of the values (you dont get to choose which). Maybe you measure 15, that means the state is now |1,1,0,1>, you just deleted all the terms that aren’t 15.
If you look at the pic, main idea is the first layer of H’s creates the state sum_x=0…2^n-1 |x, 0>, then gate U turns that state into sum_x |x, f(x)>, then the measurements measure which f(x) you have, deleting all the terms that don’t have that f(x) in them, so for example if you measure that f(x) is 13, the state is now |0, 13> + |15, 13> + |30, 13> + |45, 13> + …
This is the periodic state. Now that we have it we can just apply a gate that takes the QFT (finds the frequency, which here turns the state into roughly |15, 13>), and then measures it, giving the answer period=15.
There must be a better way of judging the validity of a social experiment using first principles. There’s a huge psychological side that people completely ignore.