/
2-oracle.aux
76 lines (76 loc) · 2.92 KB
/
2-oracle.aux
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
\relax
\citation{ambainis00quantum}
\@writefile{toc}{\contentsline {chapter}{Chapter\ 2\hskip 1em\relax Lower Oracle Query Bounds}{13}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{ch:oracle}{{2}{13}}
\citation{ambainis00quantum}
\@writefile{toc}{\contentsline {section}{\numberline {2.1}Preliminaries}{14}}
\@writefile{toc}{\contentsline {subsubsection}{Useful Definitions}{14}}
\@writefile{toc}{\contentsline {subsubsection}{Quantum Oracle Models}{14}}
\newlabel{sec:qom}{{2.1}{14}}
\citation{beals98quantum}
\citation{ambainis00quantum}
\citation{ambainis00quantum}
\@writefile{toc}{\contentsline {subsubsection}{A Lower Query Bound Proving Framework due to Ambainis}{16}}
\newlabel{th:amb}{{2.1.1}{16}}
\@writefile{toc}{\contentsline {paragraph}{The Quantum Adversary:}{16}}
\@writefile{toc}{\contentsline {section}{\numberline {2.2}A Lemma for Proving Lower Query Bounds}{18}}
\newlabel{sec:lplqb}{{2.2}{18}}
\newlabel{lm:1xky}{{2.2.1}{18}}
\citation{beals98quantum}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2.1}Application to Generalized XOR}{19}}
\newlabel{sec:gXOR}{{2.2.1}{19}}
\newlabel{th:gXOR}{{2.2.1}{19}}
\@writefile{toc}{\contentsline {section}{\numberline {2.3}Determining the Oracle String}{19}}
\newlabel{sec:dos}{{2.3}{19}}
\newlabel{th:dosbad}{{2.3.1}{19}}
\citation{beals98quantum}
\newlabel{th:dosgood}{{2.3.2}{20}}
\@writefile{toc}{\contentsline {section}{\numberline {2.4}Singleton Functions}{20}}
\newlabel{sec:torf1}{{2.4}{20}}
\newlabel{th:1sqn}{{2.4.1}{20}}
\newlabel{th:best}{{2.4.1}{20}}
\newlabel{cor:ambbad}{{2.4.2}{21}}
\@writefile{toc}{\contentsline {section}{\numberline {2.5}Partially Symmetric Functions}{21}}
\newlabel{sec:lqbsym}{{2.5}{21}}
\newlabel{def:sym}{{2.5.1}{21}}
\newlabel{th:ptsym}{{2.5.1}{22}}
\citation{beals98quantum}
\citation{beals98quantum}
\@writefile{toc}{\contentsline {section}{\numberline {2.6}AND, OR, MAJORITY, and PARITY}{23}}
\newlabel{sec:AOMP}{{2.6}{23}}
\@writefile{toc}{\contentsline {subsubsection}{AND and OR}{23}}
\newlabel{th:AND}{{2.6.1}{23}}
\citation{beals98quantum}
\@writefile{toc}{\contentsline {subsubsection}{MAJORITY and PARITY}{24}}
\newlabel{th:MAJORITY}{{2.6.2}{24}}
\citation{beals98quantum}
\citation{beals98quantum}
\@writefile{toc}{\contentsline {section}{\numberline {2.7}Nonconstant Symmetric Functions}{25}}
\newlabel{sec:lqbnsf}{{2.7}{25}}
\newlabel{th:sym}{{2.7.1}{25}}
\@setckpt{2-oracle}{
\setcounter{page}{27}
\setcounter{equation}{0}
\setcounter{enumi}{4}
\setcounter{enumii}{0}
\setcounter{enumiii}{0}
\setcounter{enumiv}{0}
\setcounter{footnote}{0}
\setcounter{mpfootnote}{0}
\setcounter{part}{0}
\setcounter{chapter}{2}
\setcounter{section}{7}
\setcounter{subsection}{0}
\setcounter{subsubsection}{0}
\setcounter{paragraph}{0}
\setcounter{subparagraph}{0}
\setcounter{figure}{0}
\setcounter{table}{0}
\setcounter{parentequation}{0}
\setcounter{theorem}{1}
\setcounter{lemma}{0}
\setcounter{defi}{0}
\setcounter{corollary}{0}
}