Ex7 4

$\def\abs#1{|#1|}\def\i{\mathbf {i}}\def\ket#1{|{#1}\rangle}\def\bra#1{\langle{#1}|}\def\braket#1#2{\langle{#1}|{#2}\rangle}\def\tr{\mathord{\mbox{tr}}}\mathbf{Exercise\ 7.4}$

a) Prove that any classical algorithm requires at least two calls to $C_f$ to solve Deutsch's problem.

b) Prove that any classical algorithm requires $2^{n-1} + 1$ calls to $C_f$ to solve the Deutsch-Jozsa problem with certainty.

c) Describe a classical approach to the Deutsch-Jozsa problem that solves it with high probability using fewer than $2^{n-1} + 1$ calls. Calculate the success probability of your approach as a function of the number of calls.

page revision: 0, last edited: 18 Nov 2012 19:30