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.

Let’s use text to describe everything!

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.

It’s a hard problem but could be a good platform for research discussions considering none exists today. Best of luck.

Somehow just by internalizing the old meaning of the world “dynamic”, I feel I have a better idea of what the world felt like back then.

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).

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.

This is a full pic of Shor’s algorithm https://images.app.goo.gl/ZE5rDxHScm4LUqms6

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.

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.

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.

Comments URL: https://news.ycombinator.com/item?id=40292452

Points: 58

# Comments: 46

-organized intelligently

-simpler explanations than what you find online

(==> more efficient)

We’re super proud of our content, and we've helped a bunch of people land FAANG offers: just recently 2 people have landed Amazon using our platform. We made sure to cover all the ideas you learn from the Blind75 and NeetCode150, and people actually feel ready for their interviews after using our platform.

We've had 30,000+ users so far, and we're even officially used in classes at Cornell University and UTDallas. We also have a growing Discord community. Don't hesitate to reach out here or in our Discord if you have any questions (they can even be LeetCode questions).

You can start free, and if you're ready to buy, use code "Recursion" for a sizable HN discount :)

Comments URL: https://news.ycombinator.com/item?id=40291309

Points: 2

# Comments: 0

Comments URL: https://news.ycombinator.com/item?id=40289386

Points: 1

# Comments: 2

-organized intelligently

-has simpler explanations than you find online

We’re super proud of our content and just recently 2 people have landed Amazon with us. People actually feel ready for interviews with us. Give it a go :).

Comments URL: https://news.ycombinator.com/item?id=40283747

Points: 1

# Comments: 0