Component mixers and a hardness result for counterfeiting quantum money

2011/07/01 by Andrew Lutomirski, Lutomirski, Andrew · 2 citations
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.1107.0321

14 pages, 1 figure

arxiv created 2011/07/01 · openalex publication_date 2011/07/01 · arxiv updated 2011/07/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Creating superpositions that correspond to efficiently integrable probability distributions

Cited by

• Quantum Money from Hidden Subspaces
• Almost Public Quantum Coins

Related

• Another Round of Breaking and Making Quantum Money: How to Not Build It from Lattices, and More
• Applications of the Adversary Method in Quantum Query Algorithms
• CountCrypt: Quantum Cryptography between QCMA and PP
• Quantum money from knots
• Open Problems Related to Quantum Query Complexity