A algorithm answers correctly with probability on each independent run

PHYSICS · Subjective · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch What quantum computers can compute efficiently

Problem

A BQP\mathrm{BQP} algorithm answers correctly with probability p=0.7p=0.7 on each independent run. Using the Hoeffding bound quoted for the error of a majority vote over kk runs, e−2k(p−1/2)2e^{-2k(p-1/2)^2}, find the smallest odd number of runs kk that brings this bound below ϵ=10−5\epsilon = 10^{-5}.

Browse the problem library