4 ms·

> if you think about quantum computing in terms of “parallel universes” (and whether you do or don’t is up to you) But if you do think of it that way, why not

> if you think about quantum computing in terms of “parallel universes” (and whether you do or don’t is up to you) But if you do think of it that way, why not just pick a random number using some quantum process, classically test whether or not it's a divisor of the number you're trying to factor, and kill yourself if it's not? In every universe where you survive (which, for sake of argument, are the only ones you care about) you find a factor on the first try.

cwillu 4y ago
Then you're talking about the complexity class PostBQP, rather than the class BQP. Postselection is ridiculously powerful, as you've noted.
__ryan__ 4y ago
In every universe where you survive (which, for sake of argument, are the only ones you care about) you find a factor on the first try. What’s more likely, randomly guessing a prime factor of a giant number, or miraculously surviving and being permanently incapacitated? Or being interrupted, saved by modern medicine, bitten by a black widow immediately after getting it right… You have to think that the odds really aren’t in your favor there.
- shagie 4y ago
  Quantum immortality is a neat thing ( https://en.wikipedia.org/wiki/Quantum_suicide_and_immortality https://en.wikipedia.org/wiki/Quantum_suicide_and_immortalit... ). I'd suggest the short story All the Myriad Ways by Larry Niven ( https://erenow.net/common/the-best-alternate-history-stories-of-the-20th-century/6.php https://erenow.net/common/the-best-alternate-history-stories... ) and the exceedingly long story Nangurz ol Arny Fgrcurafba (rot13 because it kind of is a spoiler).
  - JadeNB 4y ago
    When discussing quantum immortality and sci-fi, one must also mention Greg Egan's early Quarantine (https://en.wikipedia.org/wiki/Quarantine_(Egan_novel) https://en.wikipedia.org/wiki/Quarantine_(Egan_novel)).
    - ctoth 4y ago
      Also when discussing Quantum Immortality and Sci Fi, one must certainly mention Divided By Infinity. https://www.tor.com/2010/08/05/divided-by-infinity/ https://www.tor.com/2010/08/05/divided-by-infinity/
  - Groxx 4y ago
    As a middleground, at around 42 pages long, there's Divided by Infinity: https://www.tor.com/2010/08/05/divided-by-infinity/ https://www.tor.com/2010/08/05/divided-by-infinity/
- cwillu 4y ago
  The universe likes to play with its food. (What, did you think this logic is only valid when you're trying to gain godlike powers?)
quickthrower2 4y ago
That is quite the prisoners dilemma!
YetAnotherNick 4y ago
The thing is that even in that sense collapse will select a random universe. So you will get a universe with killed output or whatever you said it. Also quantum parallel universe is not what you expect parallel universe to be. Universes interact with each other.
kspinka 4y ago
This is thought provoking, but suffers from a fundamental flaw. Let’s play this out…now you’re alive and have Satoshi’s keys, but all of the would-be bidders and pumpers in your universe have killed themselves, value goes to zero. I think you may have accidentally discovered the Quantum Bag Holder Paradox.
- fauria 4y ago
  I googled that paradox, but can only see your comment. What is it about?
  - mrfox321 4y ago
    It's a joke, lol.
espadrine 4y ago
> why not just pick a random number using some quantum process, classically test whether or not it's a divisor of the number you're trying to factor, and kill yourself if it's not? All universes affect the probability of something occurring in each universe. That is how each universe contributes a bit of the Fourier offset which gives off the period in pretty much all universes. Because finding the right divisor is so unlikely, you run a high risk of killing yourself in all universes. As Scott emphasizes, quantum computers don’t run possibilities in parallel!
layer8 4y ago
For the winner (survivor) it doesn’t matter whether their “clones” in the other branches kill themselves, so why plan that in the first place? Also, the losers will probably prefer to not kill themselves, despite not getting lucky with their random number. So, the end result is the same as for any regular random guess.
- moffkalast 4y ago
  Besides, infinite universes doesn't mean they'll collectively give you a mutually exclusive and exhaustive set like everyone is for some reason assuming. You could just as well get the same wrong number in all of them and kill yourself off permanently in the entire multiverse. That's the nature of true randomness, if you set up a dice throw a million times they could just as well all come up as six. Incredibly unlikely, but possible.
  - alisonkisk 4y ago
  - layer8 4y ago
    Uhm, no. If you use quantum events, like radioactive decay, or the usual quantum particle experiments, or (supposedly) an app like Universe Splitter [0], you are guaranteed that the two different possible outcomes will both occur, according to quantum mechanics (if you believe in many-worlds, which is out premise). And then you can build up a binary number of arbitrary size from a sequence of such experiments. When you perform the experiment N times, there will be branches for all N-bit numbers. Or just use a QRNG service like [1] which does it for you. [0] https://cheapuniverses.com/ https://cheapuniverses.com/ [1] https://qrng.anu.edu.au/ https://qrng.anu.edu.au/
smegsicle 4y ago
note that this is what CERN is doing to 'manipulate the timeline'- the entire planet is obliterated except in cases pursuant to their interests, with none the wiser since in those cases, they 'didn't do anything'
buu700 4y ago
Sounds like quantum bogosort: https://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort https://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort The algorithm generates a random permutation of its input using a quantum source of entropy, checks if the list is sorted, and, if it is not, destroys the universe. Assuming that the many-worlds interpretation holds, the use of this algorithm will result in at least one surviving universe where the input was successfully sorted in O(n) time.
Strilanc 4y ago
Isn't the multiverse where one version of you solves the problem and the other versions don't die strictly better than the version where they commit suicide? It's not like their experiences and memories get merged into the surviving copy. They're just gone, instead of not gone.
- alisonkisk 4y ago
einpoklum 4y ago
I believe that you would enjoy this film: https://www.imdb.com/title/tt0482571/ https://www.imdb.com/title/tt0482571/
Moodles 4y ago
What would happen (most likely) is that the wave function collapses and you find yourself in a universe where the random number you chose is not in fact a divisor and so, according to your algorithm, you now have to kill yourself. Probably, you don’t feel like doing it and so this algorithm does not work.

cwillu 4y ago

Then you're talking about the complexity class PostBQP, rather than the class BQP. Postselection is ridiculously powerful, as you've noted.

__ryan__ 4y ago

In every universe where you survive (which, for sake of argument, are the only ones you care about) you find a factor on the first try. What’s more likely, randomly guessing a prime factor of a giant number, or miraculously surviving and being permanently incapacitated? Or being interrupted, saved by modern medicine, bitten by a black widow immediately after getting it right… You have to think that the odds really aren’t in your favor there.

shagie 4y ago
Quantum immortality is a neat thing ( https://en.wikipedia.org/wiki/Quantum_suicide_and_immortality https://en.wikipedia.org/wiki/Quantum_suicide_and_immortalit... ). I'd suggest the short story All the Myriad Ways by Larry Niven ( https://erenow.net/common/the-best-alternate-history-stories-of-the-20th-century/6.php https://erenow.net/common/the-best-alternate-history-stories... ) and the exceedingly long story Nangurz ol Arny Fgrcurafba (rot13 because it kind of is a spoiler).
- JadeNB 4y ago
  When discussing quantum immortality and sci-fi, one must also mention Greg Egan's early Quarantine (https://en.wikipedia.org/wiki/Quarantine_(Egan_novel) https://en.wikipedia.org/wiki/Quarantine_(Egan_novel)).
  - ctoth 4y ago
    Also when discussing Quantum Immortality and Sci Fi, one must certainly mention Divided By Infinity. https://www.tor.com/2010/08/05/divided-by-infinity/ https://www.tor.com/2010/08/05/divided-by-infinity/
- Groxx 4y ago
  As a middleground, at around 42 pages long, there's Divided by Infinity: https://www.tor.com/2010/08/05/divided-by-infinity/ https://www.tor.com/2010/08/05/divided-by-infinity/
cwillu 4y ago
The universe likes to play with its food. (What, did you think this logic is only valid when you're trying to gain godlike powers?)

quickthrower2 4y ago

That is quite the prisoners dilemma!

YetAnotherNick 4y ago

The thing is that even in that sense collapse will select a random universe. So you will get a universe with killed output or whatever you said it. Also quantum parallel universe is not what you expect parallel universe to be. Universes interact with each other.

kspinka 4y ago

This is thought provoking, but suffers from a fundamental flaw. Let’s play this out…now you’re alive and have Satoshi’s keys, but all of the would-be bidders and pumpers in your universe have killed themselves, value goes to zero. I think you may have accidentally discovered the Quantum Bag Holder Paradox.

fauria 4y ago
I googled that paradox, but can only see your comment. What is it about?
- mrfox321 4y ago
  It's a joke, lol.

espadrine 4y ago

> why not just pick a random number using some quantum process, classically test whether or not it's a divisor of the number you're trying to factor, and kill yourself if it's not? All universes affect the probability of something occurring in each universe. That is how each universe contributes a bit of the Fourier offset which gives off the period in pretty much all universes. Because finding the right divisor is so unlikely, you run a high risk of killing yourself in all universes. As Scott emphasizes, quantum computers don’t run possibilities in parallel!

layer8 4y ago

For the winner (survivor) it doesn’t matter whether their “clones” in the other branches kill themselves, so why plan that in the first place? Also, the losers will probably prefer to not kill themselves, despite not getting lucky with their random number. So, the end result is the same as for any regular random guess.

moffkalast 4y ago
Besides, infinite universes doesn't mean they'll collectively give you a mutually exclusive and exhaustive set like everyone is for some reason assuming. You could just as well get the same wrong number in all of them and kill yourself off permanently in the entire multiverse. That's the nature of true randomness, if you set up a dice throw a million times they could just as well all come up as six. Incredibly unlikely, but possible.
- alisonkisk 4y ago
- layer8 4y ago
  Uhm, no. If you use quantum events, like radioactive decay, or the usual quantum particle experiments, or (supposedly) an app like Universe Splitter [0], you are guaranteed that the two different possible outcomes will both occur, according to quantum mechanics (if you believe in many-worlds, which is out premise). And then you can build up a binary number of arbitrary size from a sequence of such experiments. When you perform the experiment N times, there will be branches for all N-bit numbers. Or just use a QRNG service like [1] which does it for you. [0] https://cheapuniverses.com/ https://cheapuniverses.com/ [1] https://qrng.anu.edu.au/ https://qrng.anu.edu.au/

smegsicle 4y ago

note that this is what CERN is doing to 'manipulate the timeline'- the entire planet is obliterated except in cases pursuant to their interests, with none the wiser since in those cases, they 'didn't do anything'

buu700 4y ago

Sounds like quantum bogosort: https://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort https://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort The algorithm generates a random permutation of its input using a quantum source of entropy, checks if the list is sorted, and, if it is not, destroys the universe. Assuming that the many-worlds interpretation holds, the use of this algorithm will result in at least one surviving universe where the input was successfully sorted in O(n) time.

Strilanc 4y ago

Isn't the multiverse where one version of you solves the problem and the other versions don't die strictly better than the version where they commit suicide? It's not like their experiences and memories get merged into the surviving copy. They're just gone, instead of not gone.

alisonkisk 4y ago

einpoklum 4y ago

I believe that you would enjoy this film: https://www.imdb.com/title/tt0482571/ https://www.imdb.com/title/tt0482571/

Moodles 4y ago

What would happen (most likely) is that the wave function collapses and you find yourself in a universe where the random number you chose is not in fact a divisor and so, according to your algorithm, you now have to kill yourself. Probably, you don’t feel like doing it and so this algorithm does not work.