6 ms·

Superposition does not fork the world. This common misconception arises due to confusion between superposition and the many-worlds interpretation of quantum mec

Superposition does not fork the world. This common misconception arises due to confusion between superposition and the many-worlds interpretation of quantum mechanics, but it’s easy to see that the two are only superficially similar. States in a superposition still interfere—that's the essence of the double-slit experiment. In contrast, when arguing that the timeline 'splits' due to measurements, the resulting universes do not interact at all and remain completely unaware of each other—they can never even know if the others exist. If quantum computers truly 'forked' the world, they would be equivalent to non-deterministic Turing machines (capable of solving NP-complete problems in polynomial time), but quantum computing experts agree that they can still be modeled as deterministic Turing machines. It's better to think of quantum computers as a type of analog computer, capable of solving certain problems that fit their model well, but not generally more powerful. It’s like an Intel CPU having SIMD or AVX instructions that allow it to perform certain operations faster, but these don't fundamentally change its capabilities. The no-free-lunch theorem applies.

snarkconjecture 2y ago
Quantum computers are generally more powerful in the sense that they can solve a larger set of problems in polynomial time. i.e. BPP is contained in BQP but the converse is thought to be false.
- andrewp123 2y ago
  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.
andrewp123 2y ago
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.
- timmattison 2y ago
  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.
  - andrewp123 2y ago
    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. This is a full pic of Shor’s algorithm https://images.app.goo.gl/ZE5rDxHScm4LUqms6 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.
cbsmith 2y ago
Thanks for restoring my sanity. Every now and then I read articles about quantum computing that upend my (limited) understanding of how it functions, and I feel like I really know nothing about it. In fairness, I do know close to nothing about it, it just turns out that "close to nothing" is still more than a good chunk of the discussion about quantum computing.

snarkconjecture 2y ago

Quantum computers are generally more powerful in the sense that they can solve a larger set of problems in polynomial time. i.e. BPP is contained in BQP but the converse is thought to be false.

andrewp123 2y ago
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.

andrewp123 2y ago

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.

timmattison 2y ago
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.
- andrewp123 2y ago
  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. This is a full pic of Shor’s algorithm https://images.app.goo.gl/ZE5rDxHScm4LUqms6 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.

cbsmith 2y ago

Thanks for restoring my sanity. Every now and then I read articles about quantum computing that upend my (limited) understanding of how it functions, and I feel like I really know nothing about it. In fairness, I do know close to nothing about it, it just turns out that "close to nothing" is still more than a good chunk of the discussion about quantum computing.