A different subroutine succeeds 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 different BQP\mathrm{BQP} subroutine succeeds with probability p=0.8p=0.8 on each independent run. Using the Hoeffding bound e−2k(p−1/2)2e^{-2k(p-1/2)^2} for the error of a majority vote over kk runs, find the smallest odd number of runs kk that brings this bound below ϵ=10−8\epsilon = 10^{-8}.

Browse the problem library