6533b7dcfe1ef96bd127169d
RESEARCH PRODUCT
Optimal one-shot quantum algorithm for EQUALITY and AND
Andris AmbainisJanis Iraidssubject
FOS: Computer and information sciencesDiscrete mathematicsOne shotQuantum PhysicsGeneral Computer ScienceProbabilistic logicFOS: Physical sciencesFunction (mathematics)Computational Complexity (cs.CC)Computer Science - Computational ComplexityProbability of errorComputation complexityQuantum algorithmQuantum Physics (quant-ph)Boolean functionQuantumMathematicsdescription
We study the computation complexity of Boolean functions in the quantum black box model. In this model our task is to compute a function $f:\{0,1\}\to\{0,1\}$ on an input $x\in\{0,1\}^n$ that can be accessed by querying the black box. Quantum algorithms are inherently probabilistic; we are interested in the lowest possible probability that the algorithm outputs incorrect answer (the error probability) for a fixed number of queries. We show that the lowest possible error probability for $AND_n$ and $EQUALITY_{n+1}$ is $1/2-n/(n^2+1)$.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2017-01-24 |