CS378 quantum QIS HW8
1. Deustch-Jozsa Problem
Recall that in the Deustch-Jozsa problem we are given oracle access
Copyright By PowCoder代写 加微信 powcoder
to an unknown function f: {0,1}”
› {0,1}, a function that maps n-bit strings to a single bit. We’re
promised that the function is either constant or balanced, where balanced means that it has an equal
number of 0 and 1 outputs (2″-1 of each). There exists a quantum algorithm that can determine whether
f is constant or balanced using only a single query to f.
a) 3 Points Prove that any classical deterministic algorithm for this problem requires 92(2″) queries.
Therefore, quantum computers give an exponential speedup over deterministic classical computers for
this problem.
Give a constructive proof, meaning that if I claim my algorithm A which makes queries Q = {91,92, . .., qm}
for m << 2" always gets the right answer, then show how to construct an input on which the algorithm is
incorrect. In particular, you might begin by supposing my algorithm actually is correct on some particular
input, and show it will fail on another.
b) [3 Points Explain why, nevertheless, this speedup is not very impressive, in the sense that it is not
an exponential quantum speedup over all classical computing for this problem. Give a full explanation
and analysis of the any runtime or likelihood of success involved in vour explanation.
2. Bernstein-Vazirani
In the Bernstein-Vazirani problem, recall that we're given oracle access to a
Boolean function f: (0,1)"
› {0,11. We're promised that there exists a "secret string" s € {0,1}" such
that f(r) = s•r (mod 2) for all 2. The problem is to recover s. The Bernstein-Vazirani algorithm solves
this problem with just a single quantum query to f.
Consider a variant of this problem where we are promised that f(x)
= s. I (mod 2) for a (1
fraction of the inputs 2 and that f(r) = s•2 + 1 (mod 2) for the remaining e fraction of inputs, where
a) [4 Points) Calculate the probability that a single run of the standard Bernstein-Vazirani algorithm
nevertheless succeeds in recovering s. Show your work
b) [3 Points] Explain what happens when € = 1/2. Further, give a short explanation why no algorithm
can possibly succeed at recovering s when € = 1/2.
Introduction to QIS
The Universitv of Texas
3. Toffoli-based Addition [2 Points) Could vou implement addition mod 2 of two 2-bit numbers
using Toffoli gates without using ancilla bits? In other words, there are four input bits which are also the
output bits. You mav ignore carry-out/overflow. Prove your answer.
4. Two Secrets (5 Points Suppose the function f : {0,1}"
- 50.11n is such that there are two
n-bit secret strings s and t such that s ‡ t, neither are the all zeros string, and f(2) = f(y) if and only
if 2 © y equals any of O, s, t, or sOt.
Give a quantum algorithm which finds an a € {0,1}" such that a ‡ 0" and a • s
= a • t = 0 (mod 2).
Prove that it works.
(You should assume set ‡ 0", which is necessary for a nonzero a to exist.)
Hint: Your algorithm should not require any classical postprocessing. This problem can be tricky: focus
on what the condition on f(r) = f(y) implies.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com