Component mixers and a hardness result for counterfeiting quantum money

Understand

In this paper we give the first proof that, under reasonable assumptions, a problem related to counterfeiting quantum money from knots [Farhi et al.

• 2010] is hard.
• Along the way, we introduce the concept of a component mixer, define three new classical query problems and associated complexity classes related to graph isomorphism and group membership, and conjecture an oracle separating QCMA from QMA.