Quantum certificate complexity

DOI10.1016/j.jcss.2007.06.020zbMath1147.68517arXivquant-ph/0210020OpenAlexW1988998010MaRDI QIDQ2475404

Scott Aaronson

Publication date: 11 March 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/0210020

zbMATH Keywords

decision treequantum computingBoolean functionquery complexityblock sensitivityadversary methodBlack boxMerlin-Arthur

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Related Items (8)

Low-Sensitivity Functions from Unambiguous Certificates. ⋮ All Classical Adversary Methods are Equivalent for Total Functions ⋮ Quantum weakly nondeterministic communication complexity ⋮ Composition limits and separating examples for some Boolean function complexity measures ⋮ On block sensitivity and fractional block sensitivity ⋮ Unnamed Item ⋮ Quadratically tight relations for randomized query complexity ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Properties of complexity measures for PRAMs and WRAMs
• Hardness vs randomness
• A note on quantum black-box complexity of almost all Boolean functions
• Complexity measures and decision tree complexity: a survey.
• Arthur-Merlin games in Boolean decision trees
• Quantum lower bound for the collision problem
• CREW PRAM<scp>s</scp> and Decision Trees
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Strengths and Weaknesses of Quantum Computing
• Nondeterministic Quantum Query and Communication Complexities
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Natural proofs

This page was built for publication: Quantum certificate complexity