Using restarts to prove QMA in PP

Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers. Stack Overflow for Teams is now called Stack Internal. Bring the best of human thought and AI automation together at your work. Bring the best of human thought and AI automation together at your work. Learn more TeamsQ&A for workConnect and share knowledge within a single location that is structured and easy to search.I am going through Ryan O'Donnell's quantum computing class homeworks, and on problem 6 of this assignment you are asked to prove $QMA$ in $PP$ using the fact that $RestartingPP = PP$, where $RestartingPP$ contains the languages $L$ for which there exists a "restarting PP machine" that decides it in the usual $PP$ sense, where, for a general randomized model of computation $M$, a "restarting $M$ machine" is defined as follows:We define [a restarting $M$ machine] as follows: At any time during the $M$-computation, the machine is allowed to “hit the restart button” (if you like, think of this as entering a special kind of Turing Machine state). When this occurs, every aspect of the computation is set back to its initial value, and computation begins again. Nothing from the earlier computation is remembered. The machine may do multiple restarts, and each is called a run. Assuming that we are interested in the time complexity of M, we define the time complexity of a Restarting $M$ computation to be the maximum of the time of the runs (not the total time). Basically, if the $M$ computation does not like the way a computation is going, it can freely restart (but has to forget everything).Now, I get that this is essentially what is going on with post selection (Kuperberg even calls post selection the "free to retry" property (link)). What confuses me, though, is that to prove $QMA \subseteq PP$, one typically uses strong error reduction for $QMA$ (as in Marriott-Watrous amplification (link)), and here, in this homework set, it is implicitly implied that you actually don't need strong error reduction for this result. I'd really appreciate it if someone could walk me through this proof using the restarting machine approach, because I don't see how to do it without using strong error reduction and the usual technique described in this TCS stack exchange post.Thanks for contributing an answer to Quantum Computing Stack Exchange!But avoid …Use MathJax to format equations. MathJax reference.To learn more, see our tips on writing great answers.Required, but never shown By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy. Start asking to get answersFind the answer to your question by asking.Explore related questionsSee similar questions with these tags.To subscribe to this RSS feed, copy and paste this URL into your RSS reader. Site design / logo © 2025 Stack Exchange Inc; user contributions licensed under CC BY-SA . rev 2025.11.20.37056