7 votes

What is the computational power of classically mixed states?

(The other answers and comments have already touched on the main points, but I have to take the opportunity to answer in my own words.) What you're describing is known as randomized or probabilistic ...
John Watrous's user avatar
  • 5,703
2 votes

What is the computational power of classically mixed states?

"Nondeterministic" as used in theoretical computer science is a legacy term popularized from at least the 70's, and imagines a special Turing machine (that's the machine with an infinite ...
Mark Spinelli's user avatar
1 vote

Understanding how to solve group isomorphism given the state $\sum_{\pi \in S_n} |\pi(G) \rangle$

There are several pretty standard approaches to "solving" graph isomorphism given access to uniform superpositions over all the permutations of particular graphs (untensored with garbage). ...
Mark Spinelli's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible