For the paper “Exact quantum query complexity of EXACT and THRESHOLD” by Andris Ambainis, Jānis Iraids & Juris Smotrovs; Maris Ozols, on his blog has posted an excellent analysis of this paper.
Andris Ambainis, Jānis Iraids, and Juris Smotrovs recently have obtained some interesting quantum query algorithms [AIS13]. In this blog post I will explain my understanding of their result.
Throughout the post I will consider a specific type of quantum query algorithms which I will refer to as MCQ algorithms (the origin of this name will become clear shortly). They have the following two defining features:
- they are exact (i.e., find answer with certainty)
- they measure after each query
Quantum effects in an MCQ algorithm can take place only for a very short time — during the query. After the query the state is measured and becomes classical. Thus, answers obtained from two different queries do not interfere quantumly. This is very similar to deterministic classical algorithms that also find answer with certainty and whose state is deterministic after each query.
Basics of quantum query complexity
Our goal is…
View original post 1,265 more words
kryptomusing 