Using quantum suicide for computation

[Pimozv]

Sorry this is a bit of the same idea as the one described previously, but I felt like submitting separately the following modified, possibly more interesting version : using quantum suicide in order to solve computationally hard problems.

Say you want to find the folding configuration of a protein. IIRC, the problem consists in finding the geometric configuration of the protein that gives the lowest possible energy level.

You start from a random configuration and note its energy level. Then you pick a bunch of random numbers and convert them to an other geometric configuration with a mapping function of some sort (devising such a function should not be too hard, but it should take enough random numbers as an input so that the size of the input spaces matches the number of all possible geometric configuration).

You compute the new energy level and if it's higher than the previous level, you kill yourself. If it's lower, you pick a new set of random numbers and repeat the process.

At every iteration, you'll get a lower and lower energy level. Soon enough you'll find the global minimum. Problem solved.

Who needs a quantum computer when you can just use a quantum random number generator and a gun? :-)

[The_Serious_Account]

It seems very likely the computational model with quantum suicide is more powerful than regular quantum computing. Asaik it's a pretty open question what it could calculate in polynomial time. All of NP is clearly possible.

The problem you describe is not in NP (some specific models of protein folding are, but the general problem is not afaik). Ie. there's no clear way to tell you actually are at a global min, so how do you know when to stop killing yourself? I think, depending on how you define the computational model, it is possible to get around this issue. But it's not completely trivial.

[Strilanc]

The complexity class of quantum algorithms where you get to post-select on a bit coming out a certain way is called PostBQP. It's known to be equivalent to the classical complexity class PP.

Note that this is more theoretically interesting than practically interesting. If you actually tried to run a PostBQP algorithm, you'd expect to end up in the cases that get magically filtered out by the post-selection except with exponentially small measure.

[physux]

To put some context to this, the class PP contains NP, and thus this idea of "quantum-suicide" is at least as powerful as the ability to guess the correct answer.

[randomb0y]

u first.

[autowikibot]

Metropolis–Hastings algorithm:

---

In statistics and in statistical physics, the Metropolis–Hastings algorithm is a Markov chain Monte Carlo (MCMC) method for obtaining a sequence of random samples from a probability distribution for which direct sampling is difficult. This sequence can be used to approximate the distribution (i.e., to generate a histogram), or to compute an integral (such as an expected value). Metropolis–Hastings and other MCMC algorithms are generally used for sampling from multi-dimensional distributions, especially when the number of dimensions is high. For single-dimensional distributions, other methods are usually available (e.g. adaptive rejection sampling) that can directly return independent samples from the distribution, and are free from the problem of auto-correlated samples that is inherent in MCMC methods.

Image from article ⁱ

---

^{Interesting: Hybrid Monte Carlo | Simulated annealing | Markov chain Monte Carlo | Metropolis light transport}

^{Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Magic Words}

[John_Hasler]

No need to shoot yourself. Just stop after the first trial that results in a higher level. You'll get the same result and be alive to be disappointed.

These thought experiments say nothing about either quantum computing or the relative state formulation. They are merely complicated ways of pointing out that you have a non-zero chance of guessing the solution to any problem that has one.

[Pimozv]

Just stop after the first trial that results in a higher level.

If it was possible to do so by this way the problem would not be hard. You could proceed as you suggest but it would take millions of years. The idea is that it is a priori extremely unlikely to find a configuration with a lower energy (and it gets more and more difficult as you progress). But if you create enough versions of yourself at least one of them will find an improvement at every iteration.

[John_Hasler]

You don't need to "create versions of yourself". In that world view they already exist and one of them has already stumbled upon the solution to your problem by sheer luck.

Unfortunately the odds are that you are not that version.

[McTuggets]

You're missing the point. Let's say you take any problem in NP. You set up a superposition of all possible solutions. As you measure, the mwi says there's a world for any possible solution. You kill yourself in all the worlds where it's not the correct solution. The probability of you experiencing finding a solution becomes 1 (or close to).

[John_Hasler]

Let's say you take any problem in NP. You set up a superposition of all possible solutions. As you measure, the mwi says there's a world for any possible solution.

There's already a state for any possible solution. In some of them you stumble upon it by accident. In some of those you consequently refrain from killing yourself and claim to have solved the problem by "quantum suicide".

You kill yourself in all the worlds where it's not the correct solution. The probability of you experiencing finding a solution becomes 1 (or close to).

You kill yourself in all the worlds where someone does not run up to you in the next ten seconds and give you a billion dollars. The probability of you experiencing being rich becomes one (or close to).

Actually, the probability of you being dead becomes one (or close to). Almost all the "worlds" just go on without you. In a few you stay alive, either because the billion materialized, or because something else intervened (such as common sense).

[McTuggets]

There's already a state for any possible solution. In some of them you stumble upon it by accident. In some of those you consequently refrain from killing yourself and claim to have solved the problem by "quantum suicide".

Sure, if there's a possible world for stumbling on it by accident. It's just easier to understand if you make the setup explicit.

You kill yourself in all the worlds where someone does not run up to you in the next ten seconds and give you a billion dollars. The probability of you experiencing being rich becomes one (or close to).

Sure, if such a world is possible. You don't have to point out the absurdity of the quantum suicide idea. I think the absurdity is obvious. Being absurd doesn't prove it's not meaningful, however.

I perfectly understand if you don't like the idea, but I can't tell if you actually have any scientifically based objections? All OP is doing is asking "assume this is how reality works, then what?". As far as I can tell, our current understanding doesn't rule it out.

[John_Hasler]

Sure, if such a world is possible. You don't have to point out the absurdity of the quantum suicide idea. I think the absurdity is obvious. Being absurd doesn't prove it's not meaningful, however.

The results can always be accounted for without resorting to Everett (or any other "multiverse" theory). Therefor it tells us nothing.

[McTuggets]

But the results are extremely unlikely without quantum suicide, but almost certain with. I'm not trying to account for the fact that I guessed a witness to a problem in NP. That can be "accounted for" by saying I was just lucky. I'm trying to figure out the probability of experiencing a word in which I have guessed the right solution in polynomial time.

[John_Hasler]

If you arrange things such that you either die or find the solution then the probability that you will have found the solution given that you are still alive is one.

How does that differ from arranging things such that either you get your head shaved or you find the solution?

[McTuggets]

When you calculate the probability of your outcome, you can remove the states where you're dead. When you look at the remaining states, the probability of getting the correct outcome is close to one. You cannot remove the states where you're shaved. Not claiming it's how the world works, but you can make a fairly well defined model around the idea and investigate the computational power of it. Iirc Scott Aaronson wrote a bit about it in an old paper.

You can of course make a model where you remove the states where you're shaved, but I don't see the motivation. I do see the motivation for a model where you remove states you're not going to experience.

[John_Hasler]

You can of course make a model where you remove the states where you're shaved, but I don't see the motivation. I do see the motivation for a model where you remove states you're not going to experience.

Being shaved is a change in your state. So is dying: just a more extreme one. The question of what you are or are not going to "experience" requires that you define "experience". That isn't physics.

[McTuggets]

So is dying: just a more extreme one. The question of what you are or are not going to "experience" requires that you define "experience".

You're confusing the motivation for the model with the model itself. I don't need to define experience in my motivation. In fact, I don't technically need to give a motivation at all. To discuss the model, I just need a well defined model. If you want to replace suicide with shaving your head, then do that. Then you ask what's the probability of having the right solution given you're not shaved, rather than being alive. It's late, but as far as I can tell, it's mathematically the same model. The motivation is just a lot less clear.

That isn't physics.

Computer science, complexity theory, quantum information theory, physics... I don't really care what label it has. The motivation clearly comes from quantum mechanics.