imported>TCSseminar |
imported>TCSseminar |
| Line 1: |
Line 1: |
| *每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。
| | {{Infobox |
| | |name = Infobox |
| | |bodystyle = |
| | |title = <font size=3>量子计算 |
| | <br>Quantum Computation</font> |
| | |titlestyle = |
|
| |
|
| == Problem 1 == | | |image = |
| Suppose we want to estimate the value of <math>Z</math>. Let <math>\mathcal{A}</math> be an algorithm that outputs <math>\widehat{Z}</math> satisfying
| | |imagestyle = |
| <math>\Pr[ (1-\epsilon)Z \leq \widehat{Z} \leq (1+\epsilon )Z] \geq \frac{3}{4} .</math>
| | |caption = |
| | |captionstyle = |
| | |headerstyle = background:#ccf; |
| | |labelstyle = background:#ddf; |
| | |datastyle = |
|
| |
|
| We run <math>\mathcal{A}</math> independently for <math>s</math> times, and obtain the outputs <math>\widehat{Z}_1,\widehat{Z}_2,\ldots,\widehat{Z}_s</math>.
| | |header1 =Instructor |
| | |label1 = |
| | |data1 = |
| | |header2 = |
| | |label2 = |
| | |data2 = 姚鹏晖 |
| | |header3 = |
| | |label3 = Email |
| | |data3 = pyao@nju.edu.cn |
| | |header4 = |
| | |label4= Office |
| | |data4= 计算机系 502 |
| | |header5 = Class |
| | |label5 = |
| | |data5 = |
| | |header6 = |
| | |label6 = Class meetings |
| | |data6 = 周三, 8:00-9:50 <br> 仙 I-101 |
| | |header7 = |
| | |label7 = Place |
| | |data7 = |
| | |header8 = |
| | |label8 = Office hours |
| | |data8 = 周二, 14:00-16:00 <br>计算机系 502 |
| | |header9 = Textbooks |
| | |label9 = |
| | |data9 = |
| | |header10 = |
| | |label10 = |
| | |data10 = https://ae01.alicdn.com/kf/Ub17686c32db841e5851e7ed0062118ef0.jpg |
| | |header11 = |
| | |label11 = |
| | |data11 = Michael A. Nielsen / Isaac L. Chuang <br>''Quantum Computation and Quantum Information''.<br> Cambridge Univ Press, 2011. |
| | |header12 = Teaching Assistant |
| | |data13= 赵铭南 |
| | |label14= Email |
| | |data14= DZ20330042@smail.nju.edu.cn |
| | |label15= Office |
| | |data15=计算机系 410 |
| | |belowstyle = background:#ddf; |
| | |below = |
| | }} |
|
| |
|
| Let <math>X</math> be the '''median''' (中位数) of <math>\widehat{Z}_1,\widehat{Z}_2,\ldots,\widehat{Z}_s</math>. Find the number <math>s</math> such that <math>\Pr[ (1-\epsilon)Z \leq X \leq (1+\epsilon )Z] \geq 1 - \delta .</math>
| |
|
| |
|
| Express <math>s</math> as a function of <math>\delta</math>. Make <math>s</math> as small as possible.
| |
|
| |
|
| '''Remark''': in this problem, we boost the probability of success from <math>\frac{3}{4}</math> to <math>1-\delta</math>. This method is called the median trick.
| | = Announcement = |
| | * (2021/3/8) 从第二周开始进行<font color=red >线下</font>授课。 |
|
| |
|
| '''Hint''': Chernoff bound. | | = Course info = |
| == Problem 2 ==
| | * '''Instructor ''': 姚鹏晖 ([mailto:pyao@nju.edu.cn pyao@nju.edu.cn]) |
| In class, we saw how to estimate the number of distinct elements in a data stream using the Flajolet-Martin algorithm. Consider the following alternative formulation of the distinct elements problem: given an <math>N</math> dimensional vector <math>x</math>, we want to process a stream of arbitrary increments to entries in <math>x</math>. In other words, if we see a number <math>i\in 1,\dots,N</math> in the stream, we update entry <math>x_i\gets x_i + 1</math>. Our goal is to estimate <math>\left \|x\right \|_0</math>, which measures the number of non-zero entries in <math>x</math>. With <math>x</math> viewed as a histogram that maintains counts for <math>N</math> potential elements, <math>\left \|x\right \|_0</math> is exactly the number of distinct elements processed.
| | * '''Teaching assistant''': 赵铭南 ([mailto:DZ20330042@smail.nju.edu.cn DZ20330042@smail.nju.edu.cn]) |
| In this problem we will develop an alternative algorithm for estimating <math>\left \|x\right \|_0</math> that can also handle '''decrements''' to entries in x. Specifically, instead of the stream containing just indices <math>i</math>, it contains pairs <math>(i, +)</math> and <math>(i, −)</math>. On receiving <math>(i, +)</math>, <math>x</math> should update so that <math>x_i\gets x_i + 1</math> and on receiving <math>(i, −)</math>, <math>x</math> should update so that <math>x_i\gets x_i - 1</math>. For this problem we will assume that, at the end of our stream, each <math>x_i \ge 0</math> (i.e. for a specific index we can’t receive more decrements than increments).
| | * '''Class meeting''': 周三, 8:00-9:50, 仙 I-101. |
| * Consider a simpler problem. For a given value <math>T</math>, let’s design an algorithm that succeeds with probability <math>(1 − \delta)</math>, outputing '''LOW''' if <math>T < \frac{1}{2}\left \|x\right \|_0</math> and '''HIGH''' if <math>T > 2\left \|x\right \|_0</math>: | | * '''Office hour''': 周二, 14:00-16:00, 计算机系 502. |
| ** Assume we have access to a completely random hash function <math>h(\cdot)</math> that maps each <math>i</math> to a random point in <math>[0, 1]</math>. We maintain the estimator <math>s=\sum_{i:h(i)<\frac{1}{2T}}x_i</math> as we receive increment and decrement updates. Show that, at the end of our stream,<br>(i) If <math>T < \frac{1}{2}\left \|x\right \|_0</math>, <math>Pr_h[s=0]<1/e\approx 0.37</math>;<br>(ii) If <math>T > 2\left \|x\right \|_0</math>, <math>Pr_h[s=0]>0.5</math>.
| | * '''QQ group''': 808749651(2021量子计算课程群) <font color=red >(加群时请注明学号和姓名)</font> |
| ** Using this fact, show how to use <math>k=O(\log 1/\delta)</math> independent random hash functions, and corresponding individual estimators <math>s_1, s_2, . . . , s_k</math>, to output '''LOW''' if <math>T < \frac{1}{2}\left \|x\right \|_0</math> and '''HIGH''' if <math>T > 2\left \|x\right \|_0</math>. If neither event occurs you can output either '''LOW''' or '''HIGH'''. Your algorithm should succeed with probability <math>(1 − \delta)</math>. | |
| * Using <math>O(\log N)</math> repetitions of your algorithm for the above decision problem (with <math>\delta</math> set appropriately), show how to obtain an estimate <math>F</math> for <math>\left \|x\right \|_0</math> such that <math>\frac{1}{4}\left \|x\right \|_0\le F\le 4\left \|x\right \|_0</math> w.h.p.(with probability <math>1-O(1/N)</math>).
| |
|
| |
|
| == Problem 3 == | | = Course materials = |
| Let <math>U</math> be a universal set.
| | * [https://m.tb.cn/h.4PWyao7?sm=59c340 A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition.] |
| We use <math>2^U</math> to denote the collection of all subsets of <math>U</math>.
| | * [https://www.cs.umd.edu/~amchilds/qa/qa.pdf Andrew M. Childs. Lecture Notes on Quantum Algorithms.] |
| Let <math>\mathcal{F}</math> be a family of hash functions, in which each hash function <math>h:2^U \rightarrow \{0,1\}^m</math> maps subsets of <math>U</math> to 0-1 vectors of length <math>m</math>.
| | * [https://arxiv.org/abs/1907.09415 Ronald de Wolf. Quantum Computing: Lecture Notes.] |
| A locality sensitive hashing scheme is a distribution on a family <math>\mathcal{F}</math> of hash functions operating on <math>2^U</math>, such that for two subsets <math>A,B \in 2^U</math>,
| | 如果在获取教材方面有困难可以联系助教。(仅限英文版) |
|
| |
|
| <math>(1) \qquad \Pr_{h\in\mathcal{F}}[h(A)=h(B)]=sim(A,B).</math>
| | = Assignments = |
| | * 每章结束后有4~5道题目，在第二次上课前发送到助教（赵铭南）邮箱 DZ20330042@smail.nju.edu.cn。 |
|
| |
|
| Here <math>sim:2^U \times 2^U \rightarrow [0,1] </math> is called the similarity function. Given a hash function family <math> \mathcal{F} </math> that satisfies Equation (1), we will say that <math>\mathcal{F}</math> is a locality sensitive hash function family corresponding to similarity function <math>sim(\cdot,\cdot)</math>.
| | * 每道题要有完整的解题过程，中英文不限。 |
|
| |
|
| *For any similarity function <math> sim(A,B)</math> that admits a locality sensitive hash function family as defined in Equation (1), prove that the distance function <math> d(A,B) \triangleq 1-sim(A,B)</math> satisfies triangle inequality, formally,
| | = Lecture Notes = |
| | | 如果有下载课件的问题请及时联系助教。 |
| <math> \forall A,B,C \in 2^U :\quad d(A,B) + d(B,C) \geq d(A,C).</math>
| | # Lecture 1([http://1.15.137.158/qc2021spring/lec1.pptx slides]) |
| | |
| *Show that there is no locality sensitive hash function family corresponding to Dice's and the Overlap coefficient. Dice's coefficient is defined as:
| |
| | |
| <math>sim_{Dice}(A,B)=\frac{2|A\cap B|}{|A| + |B|}.</math>
| |
| | |
| Overlap coefficient is defined as:
| |
| | |
| <math>sim_{Ovl}(A,B) = \frac{|A\cap B|}{\min(|A|, |B|)}.</math>
| |
| | |
| <font color = "blue">Hint: use the triangle inequality result. </font>
| |
| | |
| * Construct a collection of hash function <math>\mathcal{B}</math> where <math>f : \{0,1\}^m \rightarrow \{0,1\}</math> for each <math>f \in \mathcal{B}</math>, together with a probability distribution on <math>\mathcal{B}</math> such that
| |
|
| |
| <math>\forall x, y \in \{0,1\}^m:\quad
| |
| \Pr_{f \in \mathcal{B}}[f(x) = f(y)] = \begin{cases}
| |
| 1 &\text{ if } x= y;\\
| |
| \frac{1}{2} &\text{ if } x \neq y.
| |
| \end{cases}
| |
| </math>
| |
| | |
| Then use the hash function family <math>\mathcal{B}</math> to prove the following result.
| |
| Given a locality sensitive hash function family <math>\mathcal{F}</math> (<math>h:2^U \rightarrow \{0,1\}^m</math> for each <math>h \in \mathcal{F}</math>) corresponding to a similarity function <math>sim(A,B)</math>, we can obtain a locality sensitive hash function <math>\mathcal{F}'</math> (<math>h':2^U \rightarrow \{0,1\}</math> for each <math>h' \in \mathcal{F}'</math>) corresponding to the similarity function <math>\frac{1+sim(A,B)}{2}</math>.
| |
| == Problem 4 ==
| |
| Let <math>G(V,E)</math> be an undirected graph with positive edge weights <math>w:E\to\mathbb{Z}^+</math>. Given a partition of <math>V</math> into <math>k</math> disjoint subsets <math>S_1,S_2,\ldots,S_k</math>, we define
| |
| :<math>w(S_1,S_2,\ldots,S_k)=\sum_{uv\in E\atop \exists i\neq j: u\in S_i,v\in S_j}w(uv)</math>
| |
| as the cost of the '''<math>k</math>-cut''' <math>\{S_1,S_2,\ldots,S_k\}</math>. Our goal is to find a <math>k</math>-cut with maximum cost.
| |
| # Give a poly-time greedy algorithm for finding the weighted max <math>k</math>-cut. Prove that the approximation ratio is <math>(1-1/k)</math>.
| |
| # Consider the following local search algorithm for the weighted max cut ('''max 2-cut''').
| |
| ::Fill in the blank parenthesis. Give an analysis of the running time of the algorithm. And prove that the approximation ratio is 0.5.
| |
| <center>
| |
| {| class="wikitable"
| |
| | start with an arbitrary bipartition of <math>V</math> into disjoint <math>S_0,S_1</math>;
| |
| while (true) do
| |
| :if <math>\exists i\in\{0,1\}</math> and <math>v\in S_i</math> such that <font color=red>(______________)</font>
| |
| ::then <math>v</math> leaves <math>S_i</math> and joins <math>S_{1-i}</math>;
| |
| ::continue;
| |
| :end if
| |
| :break;
| |
| end
| |
| |}
| |
| </center>
| |
