Quantum Evaluation of Multi-Valued Boolean Functions
Kazuo Iwama$^{\dag, \dag\dag}$
Akinori Kawachi$^{\dag, \dag\dag}$
Hiroyuki Masuda$^{\dag, \dag\dag}$
Raymond H. Putra$^{\dag, \dag\dag}$ and Shigeru Yamashita$^{\dag, \dag\dag\dag}$
$^{\dag}$Quantum Computation and Information
ERATO
Japan Science and Technology Corporation (JST)
$^{\dag\dag}$Graduate School of Informatics
$^{\dag\dag\dag}$NTT Communication Science Laboratories
0.tex
\section*{Abstract}
%Our problem is to evaluate the value of a Boolean functions through oracle calls.
%Such an oracle is defined as $f(a,x): \{0,1\}^n\times\{0,1\}^n \rightarrow
%\{0,1\}$, for example, the $EQ$-oracle is defined as $f(a,x)=1$ iff $x
%=a$. Let $N = 2^n$ and a specific oracle $f$ is given as
%a truth table $T_f$ of size $N\times N$. Let $K$ be the maximum number
%of $1$'s in a single column of $T_f$. Then we can show that the query
%complexity for the problem is heavily governed by this single
%parameter $K$. Namely: ($i$) The query complexity is
%$\Omega(\sqrt{N/K})$. ($ii$) This lower bound is tight in the sense that we
%can construct an explicit oracle whose query complexity is
%$O(\sqrt{N/K})$. ($iii$) The tight complexity,
%$\Theta(\frac{N}{K}+\log{K})$, is also obtained for the classical
%case. Thus, the quantum algorithm needs a quadratically less number of
%oracle calls when $K$ is small and this merit becomes larger when $K$
%is large, e.g., $\log{K}$ v.s. constant when $K = cN$.

%One might consider our search problem is similar to Grover search
%problem with multiple solutions (GSPMS), i.e., the query complexity for our
%problem seems to be a direct consequence of that of GSPMS. 

%Our setting is similar to multi-solution (MS) Grover search problem.
%However, it should be noted that they are different problems, and we
%show that there exist gaps between the query complexities for the
%two problems in some cases. 

%By using the lower bound for our search problem, we also show an
%interesting fact that there exists a case when the query complexity
%for GSPMS does not change even if we have the information about $T_f$. 

Our problem is to evaluate a multi-valued Boolean function $F$ through oracle calls.
If $F$ is one-to-one and the size of its domain and range is the same,
then our problem can be formulated as follows: Given an oracle $f(a,x): 
\{0,1\}^n\times\{0,1\}^n \rightarrow \{0,1\}$ and a fixed (but hidden)
value $a_0$, we wish to obtain the value of $a_0$ by querying the oracle $f(a_0,x)$.
Our goal is to minimize the number of such oracle calls (the query complexity) using a quantum mechanism.

Two popular oracles are the EQ-oracle defined as $f(a,x)=1$ iff $x=a$ and the IP-oracle
defined as $f(a,x)= a\cdot x \mod 2$. It is also well-known that the query 
complexity is $\Theta(\sqrt{N})$ ($N=2^n$) for the EQ-oracle while only $O(1)$ 
for the IP-oracle. The main purpose of this paper is to fill this gap or to investigate
what causes this large difference. To do so, we introduce a parameter $K$ as the maximum
number of 1's in a single column of $T_f$ where $T_f$ is the $N\times N$ truth-table of the oracle $f(a,x)$.
Our main result shows that the (quantum) query complexity is heavily governed by this 
parameter $K$: ($i$) The query complexity is $\Omega(\sqrt{N/K})$. ($ii$) This lower bound 
is tight in the sense that we can construct an explicit oracle whose query complexity is 
$O(\sqrt{N/K})$. ($iii$) The tight complexity, $\Theta(\frac{N}{K}+\log{K})$, is also obtained 
for the classical case. Thus, the quantum algorithm needs a quadratically less number of
oracle calls when $K$ is small and this merit becomes larger when $K$
is large, e.g., $\log{K}$ v.s. constant when $K = cN$.


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: 

1.tex
\section{Introduction}

%Let $n$ be an integer $\ge 1$ and $N = 2^n$. A {\it search problem} is to
%find a target sequence $a \in \{0,1\}^n$ by using oracle calls, where
%an oracle is given as a function $f(a,x): \{0,1\}^n \times \{0,1\}^n
%\rightarrow \{0,1\}$. 
%This oracle model is the same as the one in~\cite{Ki02}, i.e., the
%black box has the information of a fixed and hidden $a$, and it
%answers the value of $f(a,x)$ when it is asked with $x$. 
%For example, the Grover's original paper \cite{Gro96} deals
%with this search problem where he uses the so-called EQ-oracle defined
%as  
%$$
%f(a,x) = EQ_a(x) = \begin{cases} 1 &\text{if $x =a$},\\
%0 &\text{otherwise}.\end{cases}
%$$
%Another popular oracle is called the Inner Product (IP) oracle, defined as 
%$$
%f(a,x) = IP_a(x) = a\cdot x \mod 2,
%$$
%where $a \cdot x$ means the inner product of two $n$-bit sequences $a$
%and $x$. It is well-known that the query complexity, the number of
%oracle calls to get the target $a$, is $\Theta(\sqrt{N})$ for the
%$EQ$-oracle \cite{Amb02,BBCMW98,BBBV97,Gro96,Vaz98} while it is only $O(1)$ for the
%$IP$-oracle \cite{AC02,Bernstein97}. In this 
%paper, the complexity always means the quantum complexity, i.e., the
%complexity for quantum algorithms unless otherwise stated.  


% \input{EQOracle.tex}
% \input{IPOracle.tex}


\begin{figure}[tb]
\begin{center}
%\vspace{-3mm}
\resizebox{14cm}{!}{ 
\includegraphics*{EQOracle.eps} 
}
\caption{$f(a,x) = EQ_a(x)$}
\end{center}
\end{figure}


\begin{figure}[tb]
\begin{center}
\resizebox{14cm}{!}{ 
\includegraphics*{IPOracle.eps} 
}
\caption{$f(a,x) = a\cdot x = \sum_i a_i \cdot x_i\quad\mod 2$}
\end{center}
\end{figure} 


%The difference between the two oracles, $EQ_a$ and $IP_a$, becomes
%clear if we observe their truth-tables, which are illustrated (for $n
%= 4$) in Figs. 1 and 2, respectively.
In \cite{Amb02}, Ambainis introduced the problem of evaluating a
(multi-valued and incompletely specified) Boolean function
$F(x_0,\ldots,x_{N-1})$ using a quantum mechanism. This problem includes
many interesting specific problems. For example, if we define 
$$
F(x_0,\ldots,x_{N-1}) = \begin{cases} a &\text{if $x_a = 1$ and $x_j =
0$ for all $j \neq a$},\\
\text{undefined} & \text{otherwise},\end{cases}
$$
then evaluating this function $F$ is the same as the so-called Grover
search. Also, if we define 
$$
F(x_0,\ldots,x_{N-1}) = \begin{cases} a &\text{if $x_i = a\cdot i$ mod 2 for
all $0 \le i \le N-1$},\\
\text{undefined} & \text{otherwise},\end{cases}
$$
then this is the same as the so-called Bernstein-Vazirani problem
\cite{Bernstein97} introduced in \cite{Gru99}. ``Quantum evaluation''
assumes that we can obtain the value of variable $x_i$ only through an oracle
$O(i)$. Since both functions are one-to-one, 
and their domain and range are of the same size, 
we can formulate the problem as follows. 

Let $n$ be an integer $\geq 1$ and $N = 2^n$. Then, given an oracle defined 
as a function 
$$
f(a,x):\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}
$$
such that $f(a_1,x) \neq f(a_2,x)$ for some $x$ if $a_1\neq a_2$,
and a fixed (and hidden) value $a$, we wish to obtain the value 
$a$, using the oracle $f(a,x)$. 
For the Grover search, one can easily see that the definition as 
$$
f(a,x) = \begin{cases} 1 &\text{if $x =a$},\\
0 &\text{otherwise},\end{cases}
$$
completely specifies the problem. This oracle is sometimes called the
EQ oracle and is denoted by $EQ_a(x)$. See Fig.~1 for $n =
4$. As illustrated in this figure, 
$f(a,x)$ is given by a truth table of size $N\times N$,
where each row gives the value of the function $F$ of the previous
definition. For example, we have $F(1,0,\ldots,0) = 0000$ from the
first row of the table. 
If the hidden value $a$ is $0010$ for example, the oracle returns value $1$ only when it 
is queried with $x=0010$. 
For the Bernstein-Vazirani problem, the similar definition is given as 
$$
f(a,x) = a \cdot x \quad\text{mod $2$},
$$
which is called the inner product (IP) oracle and denoted by
$IP_a(x)$. Its truth table for $n = 4$ is given in Fig.~2. 
(Through this paper, we assume that the domain 
of the Boolean function $F$ has the same size as its range. 
More general cases, e.g., the size of the range is larger than the domain,
will be mentioned briefly in the last section.)

As usual, our interest is in the ({\it quantum}) {\it query complexity}, i.e.,
how many oracle calls are needed to obtain the hidden value of
$a$. It is well-known that the query complexity for the EQ-oracle is
$\Theta(\sqrt{N})$\cite{Amb02, BBCMW98, BBBV97, BBHT96, Gro96, Vaz98}, while only $O(1)$ for the IP-oracle\cite{AC02, Bernstein97}. Why does such a
big difference exist between the EQ and IP oracles?
The difference might become clearer if we compare their truth tables
given in Figs. 1 and 2. One can immediately see that the table for
$IP_a$ is well-balanced in  terms of the numbers of $0$'s and $1$'s,
but quite unbalanced for $EQ_a$. The natural consequence is that there
should be intermediate oracles between those extreme ones for which
the query complexity is also intermediate between $\Theta(\sqrt{N})$
and $O(1)$. Furthermore these intermediate oracles could be
characterized by  some parameter in such a way that the query
complexity heavily depends upon this parameter value and both $EQ_a$
and $IP_a$ are obtained as special cases. The main purpose of this
paper is to show that this conjecture is true.  

{\bf Our Contribution.} Let $T_{f}$ be the truth-table of an oracle
$f(a,x)$ like the ones given in Figs.~1 and~2. We can assume 
without loss of generality that the number of $1$'s
is less than or equal to the number of $0$'s in each column of
$T_f$. Let $\#_i(T_{f})$ denote the number of $1$'s ($\le N/2$) in the $i$-th 
column of $T_{f}$ and $\#(T_{f}) = \displaystyle\max_i
\#_i(T_{f})$. Then we can 
show that this single parameter $\#(T_f)$ plays a key role, namely: ($i$) Let
$f(a,x)$ be any oracle and $K = \#(T_{f})$. Then the query 
complexity of the search problem for $f(a,x)$ is
$\Omega(\sqrt{N/K})$. For this result, we extend the main theorem in \cite{Amb02}.
Although the extension may seem moderate in terms of the statement, it actually 
increases a lot of usefulness of the theorem. 
($ii$) This lower bound is tight in the sense
that we can construct an explicit oracle whose query complexity is
$O(\sqrt{N/K})$. This oracle again includes both EQ and IP oracles
as special cases. ($iii$) The tight complexity,
$\Theta(\frac{N}{K}+\log{K})$, is also obtained for the classical 
case. Thus, the quantum algorithm needs a quadratically less number of
oracle calls when $K$ is small and the merit is even larger when $K$
is large, e.g., $\log{K}$ v.s. constant when $K = cN$.  
%One might consider our search problem is similar to Grover search problem
%with multiple solutions (GSPMS)\cite{BBHT96}, i.e., the query complexity for 
%our problem seems to be a direct consequence of that of GSPMS.
%Our setting is similar to Grover search problem with multiple solutions (GSPMS)\cite{BBHT96}.
%However, it should be noted that they are different problems, and we
%show that there exits the gap between the query complexities for the
%two problems in some cases. 
%By using the lower bound for our search problem, we also show an
%interesting fact that there exists a case when the query complexity
%for GSPMS does not change even if we have the information about
%$T_f$. 

It should be noted that our (tight) bound $\Theta(\sqrt{N/K})$
looks similar to the tight bound of the $K$-solution Grover
search\cite{BBHT96}. This paper also examines the similarity and dissimilarity between
our problem and the multi-solution (MS) Grover: In our notation, 
MS-Grover is the problem for obtaining, for a fixed oracle $f(a,x)$ and
a fixed value $a$ both of which are hidden, the value $b \in \{0,1\}^n$ such that $f(a,b) =
1$. ($i$) There is an oracle for which our problem needs
$\Omega(\sqrt{N})$ oracle calls while MS-Grover $O(1)$ ones. ($ii$)
The complexity of the two problems is approximately the same if the
oracle is ``balanced'' (defined later) and $K \le N^{1/3}$. 
Intuitively our problem seems at least as hard as MS-Grover,
but we can also show the existence of an oracle which objects this intuition.  

{\bf Related Results.} Query complexity has constantly been one of the
central topics in quantum computation, especially in proving lower
bounds of quantum algorithms with oracles. Generally speaking, there are two
popular techniques to derive quantum lower bounds, i.e., polynomials and
adversary methods. The polynomials method was firstly introduced in
quantum computation by \cite{BBCMW98} who borrowed the idea from the
classical polynomial method. For example, it was shown that for
bounded error cases, evaluations of $AND$ and $OR$ functions need
$\Theta(\sqrt{N})$ number of queries, while parity and majority
functions at least $N/2$ and $\Theta(N)$, respectively. Recently, 
\cite{Aar02,Yi02} used the polynomials method to show the lower bounds
for collisions and element distinctness problems.

The adversary method was used in \cite{BBBV97,Vaz98}, although their
method resembles the classical one and for that reason it is called
the hybrid method. Their method can be used, for example, to show the
lower bound of the Grover Search.  Recently, Ambainis introduced a
quite general method, which is known as quantum adversary argument,
for obtaining lower bounds of various problems, e.g., the Grover
Search, AND of ORs and inverting a permutation\cite{Amb02}. Some lower
bounds are easier to obtain using the quantum adversary method than
the polynomials one. The most recent result is by \cite{BS02} who
extended \cite{Amb02} to establish a lower bound of $\Omega(\sqrt{N})$
on the bounded-error quantum query complexity of read-once Boolean
functions.   

%Our lower bound result is obviously related to the Ambainis' result. Note
%that his result is very general but, probably because of that, it is a
%bit hard to capture its intuitive meaning in a simple form. In
%contrast, our current result is less general (only for the function evaluation) 
%but it is simple and gives us a nice intuition of the
%characteristics of oracles and its relation to the query complexity. 

%Finally, we must note the result of \cite{BBHT96} which shows that the
%query complexity for GSPMS is $\Theta(\sqrt{N/K})$ if the number 
%of solutions is $K$. We can treat this GSPMS within our oracle model, 
%namely, if we restrict that the possible oracles to GSPMS are only $N$ 
% oracles, the possible $N$ oracles can be written as the  
% truth-table of size $N\times N$ as our oracle model. 
%Then, we consider the problem to find one $x$ such that $f(a, x)=1$
%where the oracle have the information of a hidden $a$.  
%This problem is essentially the same as the GSPMS if we do not have
%the information about the truth-table unlike our search problem. 
%To sum up, the result of \cite{BBHT96} is different to ours at some 
%points, i.e., ($i$) Their parameter $K$ is defined as the number of
%$1$'s at each row (if we see their oracle in the above 
%interpretation) while ours is defined as that at each column, ($ii$)
%They consider the case when the information of the truth-table is not
%available and ($iii$) Their problem seems to be somewhat easier;
%finding an $x$ such that $f(a,x) = 1$ whereas our search problem to
%find $a$.  The relation between the query complexities for our search
%problem and GSPMS will be discussed in Section~5. 


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: 

2.tex
\section{Quantum Lower Bounds}

%See Fig.~1 again. It turns out that this table can also be viewed as
%defining a function $F(x_0, x_1, \ldots, x_{N-1})$ from $D \subseteq
%\{0, 1\}^N$ into some range $R$. Namely, 
%$F(f(a,0), f(a,1), \ldots, f(a,N-1)) = a$.
%For example, the first row of the table
%shows that $F(1,0, \ldots, 0) = 0000$. The literature often uses this
%formulation for oracle computation, i.e., to evaluate the
%function $F(x_0, x_1, \ldots, x_{N-1})$ by asking (via oracle call) the
%value of $x_i$. In our search problem, $|D| = |R| = 2^n = N$ and $R= \{0,
%1\}^n$. 

Our lower bound result is related to the main theorem of \cite{Amb02}. 
In this section, we give a slight
extension of the Ambainis' result, from which our result immediately
follows. We first review Theorem 5.1 in \cite{Amb02}. 
(Note that the statement uses the original definition of our problem.)

\begin{proposition}
Let $F(x_0, \ldots, x_{N-1})$ be a function of $N$ $\{0,1\}-$valued
variables and $X, Y$ be two sets of inputs such that $F(x) \neq F(y)$
if $x \in X$ and $y \in Y$. Let $R \subset X \times Y$ be such that \\
\hspace{6mm}1. For every $x \in X$, there exist at least $m$ different  
   $y \in Y$ such that $(x, y) \in R$. \\
\hspace{6mm}2. For every $y \in Y$, there exist at least $m'$ different  
   $x \in X$ such that $(x, y) \in R$. \\
\hspace{6mm}3. For every $x$ and $i \in \{0, \ldots, N-1\}$, there are at most $l$
different $y \in Y$ such that $(x, y) \in R$ and $x_i \neq y_i$. \\
\hspace{6mm}4. For every $y$ and $i \in \{0, \ldots, N-1\}$, there are at most $l'$
different $x \in X$ such that $(x, y) \in R$ and $x_i \neq y_i$. \\
Then, any quantum algorithm computing $F$ uses 
$\Omega(\sqrt{\frac{m m'}{l l'}})$ queries. 
\end{proposition}

Our extension is due to the fact that the selection of the two 
sets, $X$ and $Y$, may not necessarily be unique but may alter 
for each column. 

\begin{theorem}
Let $F(x_0, \ldots, x_{N-1})$ be a function of $N$ $\{0,1\}-$valued
variables and $X_i, Y_i$, for $i\in\{0, \ldots, N-1 \}$, be sets of inputs such
that $F(x) \neq F(y)$ 
if $x \in X_i$ and $y \in Y_i$, and $X_0 \cup Y_0=\cdots=X_{N-1} \cup Y_{N-1}$. Let $R_i \subset X_i \times Y_i$ be
such that  \\
\hspace{6mm}1. For every $x \in X_i$, there exist at least $m$ different  
   $y \in Y_i$ such that $(x, y) \in R_i$. \\
\hspace{6mm}2. For every $y \in Y_i$, there exist at least $m'$ different  
   $x \in X_i$ such that $(x, y) \in R_i$. \\
\hspace{6mm}3. For every $x$ and $j \in \{0, \ldots, N-1\}$, there are at most $l$
different $y \in Y_i$ such that $(x, y) \in R_0 \cup \cdots \cup R_{N-1}$ and $x_j \neq y_j$. \\
\hspace{6mm}4. For every $y$ and $j \in \{0, \ldots, N-1\}$, there are at most $l'$
different $x \in X_i$ such that $(x, y) \in R_0 \cup \cdots \cup R_{N-1}$ and $x_j \neq y_j$. \\
%5. $X_i$ and $Y_i$ are two sets of inputs such that $f(x) \neq f(y)$
%   if $x \in X_i$ and $y \in Y_i$. 
%6. $X_i \cup Y_i = X \cup Y$ for every $i \in \{1, \cdots, N\}$. 
%7. $|X_i| = |X|$ and $|Y_i| = |Y|$ for every $i \in \{1, \cdots,
%N\}$. 
Then, any quantum algorithm computing $F$ uses 
$\Omega(\sqrt{\frac{m m'}{l l'}})$ queries. 
\end{theorem}

\begin{proof}
Omitted since it is enough to make word-to-word replaces in the
original proof of \cite{Amb02}.
%\hfill $\Box$ 
\end{proof}

Now our lower-bound result is almost immediate. Recall that our oracle
is defined by 
 $f(a,x): \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$. If we use
 the notation $F$, its range is $\{0,1\}^n$ and for any $x, y \in
\{0,1\}^N$ such that $x \neq y$, it is guaranteed that $F(x) \neq
F(y)$ if they are defined.  

\begin{corollary}
Let $f$ be an oracle such that $\#(T_{f}) = K$.  
Then any quantum algorithm that computes a target $a$ with probability 
$1-\varepsilon$ needs  $\Omega(\sqrt{N/K})$ oracle calls for
some fixed $\varepsilon < 1/2$.   
\end{corollary}

\begin{proof}  
Recall that $K \leq N/2$. So we can select 
 $X_i$ and $Y_i$ of Theorem~1 such that $|X_i| = |Y_i| = N/2$ and if
 $x_i = 1$ then $x \in X_i$ (i.e., all $Y_i$ do not include $y$ such
that $y_i=1$).  
Now it is not hard to see that we can set $m=m'= l = N/2$ and $l'=K$. 
Hence, Theorem~1 implies that the query complexity is 
$\Omega(\sqrt{\frac{m m'}{l l'}}) = 
\Omega(\sqrt{\frac{(N/2)^2}{NK/ 2}})=
\Omega(\sqrt{\frac{N}{K}})$.
\end{proof}


Note that Proposition 1 is, if we use it as it is, not so powerful;
we cannot prove the lower bound of the Grover search for instance.
In \cite{Amb02}, Ambainis made a different kind of extension against 
Proposition 1 to prove several lower bounds including Grover's.
This extension is quite powerful but does not seem appropriate for 
our purpose. Our extension is also powerful, which will be used later 
to prove other lower bounds.


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: 

3.tex
\section{Quantum Upper Bounds}
In this section, we show that there exists a specific oracle whose query 
complexity is $O(\sqrt{N/K})$. 
The oracle intuitively works partly as the EQ-oracle and partly as the
IP-oracle and therefore we call it a {\it hybrid oracle}. 
The hybrid oracle with a parameter $1\leq k \leq n$, denoted by $h_k(a,x)$, is
defined as follows ($k$ indicates the size of its IP-part): Let
$a=(a_1, a_2,\ldots, a_{n-k}, a_{n-k+1},\ldots, a_{n})$
and $x=(x_1, x_2,\ldots, x_{n-k}, x_{n-k+1},\ldots, x_{n}).$ Then
$h_k(a,x)=1$ iff 
(i) $(a_1,..., a_{n-k})=(x_1,..., x_{n-k})$ and 
(ii) $(a_{n-k+1},...,a_{n})\cdot (x_{n-k+1},..., x_{n}) =0$ (mod $2$). Fig.~3
shows $h_2$ for $n=4$. One can see that the small $4\times 4$ matrix is the negation of
the IP-oracle.
\begin{theorem}
There exists a quantum algorithm to find a target $a$ using $O(\sqrt{2^{n-k}})$ calls of $h_k$.
\end{theorem}
%\textbf{Theorem 2.}  
%There exists a quantum algorithm to find a target $a$ 
% with $O(\sqrt{2^{n-k}})$ oracle calls whose function
% $f_k(a, x)$ is defined with parameter $k$ such that 
%$f^k(a, x) = 1$ if $B_j(x)= B_j(a)$ for all $j \leq n-k$  and 
%$\sum_{j=n-k+1}^{n}(B_j(x) \cdot B_j(a))\,\,\mbox{mod 2} = 0$, where $B(x)$ denotes
%the binary representation of $x$ and $B_i(x)$ denotes the $i$-th bit 
%from the left of $B(x)$. (Fig.~3 shows the truth table for $f_k(a,x)$ when $n=4$ and $k=2$.) 
%\input{HybridOracle.tex}
%\input{HybridOracle2.tex}


\begin{figure}[tb]
\begin{center}
\resizebox{14cm}{!}{ 
\includegraphics*{HybridOracle.eps} 
}
\caption{The hybrid oracle with $n=4$ and $k=2$}
\end{center}
\end{figure} 



\begin{proof} 
We combine Grover search\cite{Gro96, BBHT96} with BV
algorithm\cite{Bernstein97} to find a target $a$ using the hybrid oracle
$h_k$. At first, we can determine the first $n-k$ bits of $a$. Fixing the
last $k$ bits to $|0 \rangle$, we apply Grover search using oracle $h_k$
for the first $n-k$ bits to determine $a_1,...,a_{n-k}$.
 It should be noted that $h_k(a, (a_1, \ldots, a_{n-k}, 0, \ldots, 0))
= 1$ and $h_k(a, (x_1, \ldots, x_{n-k}, 0, \ldots, 0))=0$ for any
$x_1,...,x_k \neq a_1,...,a_k$.
Next, we apply BV algorithm to determine the remaining $k$ bits.
This algorithm requires $O(\sqrt{N/K})$ queries for Grover search and 
$O(1)$ queries for BV algorithm. 
%$\Box$
\end{proof}
%Our algorithm is as follows. 
%
%\noindent\hspace{6mm}{\it Step 1.} We determine the first $n-k$ bits by using
%the Grover search as follows. \\
%\hspace{6mm}{\it Step 1.1.} We initialize the index register to $|0^{(n)}\rangle$. \\
%\hspace{6mm}{\it Step 1.2.} We apply the Hadamard transformation to each of 
%the first $n-k$ bits  of the index register.  
%     the $k+1$-st  to the $n$-th bits
%\[
%$
%|0^{(n)}\rangle \rightarrow 
% \sum_{j=0}^{2^{n-k}-1} 
%\frac{1}{\sqrt{2^{n-k}}}|j\rangle   \otimes  |0^{(k)}\rangle. 
%\]
%$
%\\
%\hspace{6mm}{\it Step 1.3.} We call the oracle $h_k$. \\
%\hspace{6mm}{\it Step 1.4.} We apply the Hadamard transformation to each of 
%the first $n-k$ bits of the index register. \\
%\hspace{6mm}{\it Step 1.5.} We apply a unitary transformation to the index
%register such that only the amplitude of $|0^{(n)}\rangle$ is
%inverted. \\
%\hspace{6mm}{\it Step 1.6.} After $O(\sqrt{2^{n-k}})$ repetitions of Step 1.2. to
%Step 1.5., we measure the index register to get 
%$|x_l\rangle|0^{(k)}\rangle$. We then determine 
%the first $n-k$ bits of the target $a$ as the same bit string as $x_l$. \\
%\hspace{6mm}{\it Step 2.} We determine the remaining $k$ bits by the same
%algorithm in~\cite{Bernstein97}.  \\
%\hspace{6mm}{\it Step 2.1.} We initialize the index register to
%$|x_l\rangle|0^{(k)}\rangle$.  \\
%\hspace{6mm}{\it Step 2.2.} We apply the Hadamard transformation to each of
%the last $k$ bits of the index register. \\
%\hspace{6mm}{\it Step 2.3.} We call the oracle $h_k$. \\
%\hspace{6mm}{\it Step 2.4.} We apply the Hadamard transformation to each of
%the last $k$ bits of the index register. \\
%\hspace{6mm}{\it Step 2.5.} We measure the last $k$ bits of the index
%register to determine the remaining $k$ 
%bits of the target $a$.   
%
%Now let us examine how the algorithm finds the correct answer.  
%Recall that $x_l$ is the first $n-k$ bits of $x$. If the oracle is called with
%the index register $|i\rangle$ where the last $k$ bits of the register
%are fixed to $0$, the oracle works as an EQ 
%oracle to find a bit string $x_l$ in the first $n-k$ bits 
%of the index register.  
%Therefore, the transformation of Step 1.2. to Step 1.5. corresponds
%to the Grover iteration for a search problem among $2^{n-k}$ possible 
%solutions. 
%Thus the query complexity of Step 1 is $O(\sqrt{2^{n-k}})$ which
%dominates the query complexity of the algorithm.  

%After determining $x_l$, if the oracle is called with the index
%register $|i\rangle$ where the first $n-k$ bits of $i$ are fixed 
%as exactly same as $x_l$, the oracle works as the negated
%IP oracle against the last $k$ bits of the index register. 
%Therefore, by using this oracle only once, we can determine the
%remaining $k$ bits of the target $a$ in the same way
%as~\cite{Bernstein97}. \hfill $\Box$ 

%It is easy to see that $\#_i(T_{h_k}) = 2^k$ or $2^{k-1}$ for all $i$. Thus, we have
%the following result from Theorem~2 by setting $K=2^k$ and $N=2^n$.  

\begin{corollary}
There exists an oracle $f$ such that $\#(T_f)=K$ and its query complexity is $O(\sqrt{N/K})$.
\end{corollary}
%\textbf{Corollary 2.}
%There exists a quantum algorithm to find $a$ 
%with $O(\sqrt{\frac{N}{K}})$ oracle calls whose function $f$ satisfies
% that $\#(T_{f}) = O(K)$

%Accordingly, by Corollary~1 and Corollary~2, we conclude that 
%$\#(T_{f})$, denoted by $K$ in the corollaries, has a correlation to the
%query complexity for search problems. It should be noted that Corollary~1 
%and Corollary~2 also hold for the EQ- and IP-oracles.   

Thus Corollary 1 is tight in the sense that we cannot improve it in general.
Note that both Corollaries 1 and 2 hold for the EQ- and IP-oracles.
We can also prove the same upper bound, $O(\sqrt{N/K})$, for a more general 
class of oracles if we restrict the value of $K$. An oracle $f$ is said to be
{\it balanced} if all columns and all rows have the same number of 1's.

%So far we have shown the relation between $\#(T_f) = K$ and the query
%complexity of evaluating functions for a special case, i.e., when
%hybrid oracles are considered. A natural question is whether the above
%result also holds for other types of oracles with $\#(T_f) = K$. The
%answer is affirmative for {\it balanced} oracles when $K$ is not so
%big. An oracle $f$ is called {\it balanced with} $K$ if each column and row
%of $T_f$ has exactly $K$\ 1's. 
\begin{theorem} 
For a balanced oracle $f(a,x)$ with $K \leq N^{1/3}$, there exists a
quantum algorithm to find a target $a$ using $O(\sqrt{N/K})$ queries
of $f$. 
\end{theorem}
\begin{proof} 
%Similarly to the previous theorem, we denote $f(a,x) \in \{0,1\}$
%as the element of $T_f$ where $a$ and $x$ are the hidden target and
%the query's index, respectively. 
Since $f(a,x)$ is balanced, each row and each column of $T_f$ has 
exactly $K$\ 1's. 
Our algorithm consists of two parts; the first part is quantum and 
the second part classical:  
The first part of the algorithm is to reduce the size of the search
space from $N$ to $K$ which is achieved by using (multi-solution) Grover search. It first
finds an $x$ such that $f(a,x) = 1$. Since 
each row of $T_f$ has $K$\ 1's, the query complexity of this first part is
$O(\sqrt{N/K})$. 
Also since each column has $K$\ 1's, the number of $a$ satisfying $f(a,x) = 1$ for a
particular $x$ is exactly $K$. Now, let a subset $R = \{a|f(a,x) = 1\}$, 
which includes the candidates of $a$. 

The second part of the algorithm is to repeatedly choose an index $y$
such that $\exists a,b \in R$ where $f(a,y) \neq f(b,y)$. Clearly,
unless $|R| = 1$, there must exist such $y$, 
which can reduce the number of the candidates at least by one. 
More formally, let the query's result for such 
$y$ is $m \in \{0,1\}$. Then, we can substitute $R \cap
\{b|f(b,y) = m\}$ for $R$, by which $|R|$ decreases at least by one.
The total query complexity is thus $O(\sqrt{N/K}) + K$, which is $O(\sqrt{N/K})$ 
for $K \leq N^{1/3}$. 
\end{proof}
%$\Box$



%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: 

4.tex
\section{Relation to Grover Upper and Lower Bounds}
%In Section~2, we prove quantum lower bounds for our search problem 
%by generalizing the Ambainis' method.
As described in Section~1, our problem is closely related to MS-Grover.
However, there exist some gaps between those two problems. 
In this section, we show some explicit oracles such that 
the query complexities of those two problems are quite different.
%One might consider that our lower bound is a direct consequence 
%of GSPMS\cite{BBHT96}. Namely, one might try to apply lower bounds for 
%GSPMS to make our proof easier, since our problem seems harder than GSPMS. 
%However, we should note that our problem is different from GSPMS.
%Indeed, there exists oracles such that our problem is
%still hard, but GSPMS becomes extremely easy.  
%We show the relationship between the problems in this section. 
%Thus, there exist some gaps between our search problem and Grover
%search problem.
%Here we consider the following three problems. 
%, including our search problem and GSPMS. 
%\textbf{Problem 1.} By querying an oracle $f$, find a target $a$ 
% with the information of the truth-table $T_f$. 
%\textbf{Problem 2.} By querying an oracle $f$, find $x$ such that
%$f(a,x)=1$  with the information of the truth-table $T_f$. 
%\textbf{Problem 3.} By querying an oracle $f$, find 
%$x$ such that $f(a,x)=1$ without the information of the truth-table $T_f$. 
%One can easily identify Problem 1 as our search problem discussed in
%the previous sections, and  Problem~3 is essentially the same as GSPMS. 
%Let $C_i(f)$ be the query complexity of Problem $i$ for an oracle $f$. 
%\textbf{Remark 1.} For any oracle $f$, $C_1(f) \geq C_2(f), C_3(f)
%\geq C_2(f)$ and $C_3(f) = 
%\Theta\left(\sqrt{N/K}\right)$\cite{BBHT96}. 
%Note that we cannot simply compare $C_1(f)$ with $C_3(f)$. 
The following theorem shows the oracle such that our problem is harder than MS-Grover.
\begin{theorem} There is an oracle $f$ such that the query complexity of our search problem is $\Omega(\sqrt{N})$ and 
that of MS-Grover is $O(1)$.
\end{theorem}
\begin{proof} Consider an oracle $f$ whose truth-table is such that the
upper left and the lower right of the table is exactly the same as the
EQ-oracle, and all the elements of the upper right and the lower left
of the table are 1's. (See Fig.~4 for $N=16$.) Then it is obvious 
that we need only $O(1)$ queries to find $x$ such that $f(a,x)=1$
since the number of such $x$ is so large that even choosing $x$ randomly suffices. 
%since either one of $f(a, x)$ with  
%$x=0000$ and $x=1111$ becomes $1$ for the oracle. 
%On the other hand, 
%to identify $a$ among $N/2$ candidates, we can apply lower bounds of
%Grover search problem with a single solution
%over the upper left or the lower right of the table. $\Box$ 
On the other hand, we can show the hardness of finding $a$ for this
oracle by Theorem 1. We select $X_i$ and $Y_i$ of Theorem 1 such that $X_i \cup Y_i$ is
equal to the upper half of the truth-table, $|X_i|=|Y_i|=N/4$ and if
$x_i=1$ then $x \in X_i$ for $i \leq N/2$.
Then, one can easily see that $m=m'=l=N/4$ and $l'=1$. Therefore, we 
need $\Omega(\sqrt{N})$ queries to find $a$. 
\end{proof}

\begin{figure}[tb]
\begin{center}
\resizebox{14cm}{!}{ 
\includegraphics*{example.eps} 
}
\caption{A truth-table where our problem is harder than MS-Grover}
\end{center}
\end{figure} 

%Also, there is another case such that our problem is easier.
%\begin{theorem} There is an oracle $f$ such that the query complexity
%of our search problem is $O(1)$ and that of MS-Grover is $\Omega(\sqrt{N})$.
%\end{theorem}
%\begin{proof} We consider a slightly different oracle $f$ from $IP_a$.
%This $f$ satisfies that $f(0,0)=1$ and $f(a,x)= a\cdot x$ for $a\neq
%0$ and $x\neq 0$. We can find $a$ for the oracle $f$ by BV algorithm with high
%probability although $f$ is slightly different from $IP$-oracle.
%However, when $a=0$, we require $\Omega(\sqrt{N})$ queries to find $x$
%such that $f(a,x)=1$. 
%\end{proof}
%\noindent\hspace{6mm}{\it Step 1.} We initialize the index register to $|0^{n}\rangle$.  \\
%\hspace{6mm}{\it Step 2.} We apply the Hadamard transformation to the index register. 
%$
%\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle
%$ \\
%\hspace{6mm}{\it Step 3.} We call the oracle $f$.
%$
%\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}(-1)^{f(a,x)}|x\rangle
%$ \\
%\hspace{6mm}{\it Step 4.} We apply the Hadamard transformation to the index register. 
%$ 
%\frac{1}{N}\sum_{x=0}^{N-1}(-1)^{f(a,x)}\sum_{y=0}^{N-1}(-1)^{x \cdot y}|y\rangle
%$ \\
%\hspace{6mm}{\it Step 5.} We measure the index register to determine the target $a$. 

%In the case of $a = 0^{n}$, final state of the index register is 
%$\frac{N-2}{N}|0^{n}\rangle-\frac{2}{N}\sum_{x \neq 0}|x\rangle$. 
%Therefore, the error probability of this algorithm is $O(1/N)$ and the number of queries for $f$ is $O(1)$.

%The above two theorems imply that 
%the query complexity of our search problem is not 
%a direct consequence from that of MS-Grover and we cannot simply compare 
%the query complexities of these problems. 
%However, the complexity of our problem is almost equal to that of MS-Grover in a certain case.
%We consider a balanced oracle, defined in Sec~3, again.
%As shown in Sec~3, for a balanced oracle $f$ with $K \leq N^{1/3}$, we can find a target $a$ with $\Theta(\sqrt{N/K})$ queries.
%On the other hand, Grover search can find an $x$ such that $f(a,x)=1$ and 
%it is optimal since if more efficient algorithm exists then we can find $a$ using this algorithm with less than $O(\sqrt{N/K})$ queries.
%Thus the query complexity of MS-Grover for this oracle is also $\Theta(\sqrt{N/K})$, which is equal to that of our problem.
Thus our problem is much harder than MS-Grover in this particular oracle. 
It is also true, as shown in the previous section, that our problem has 
approximately the same query complexity as MS-Grover for balanced oracles with
$K \leq N^{1/3}$. 
Then, is there any oracle for which MS-Grover is {\it harder} than our problem? 
We have no formal answer to this question, but the following example suggests 
that the answer is probably yes: 
Let $IP_{a}'$ be an oracle which is exactly the same as $IP_a$ except 
that $f(0,z)=1$ for some single $z$ (recall that $f(0,z)=0$ in $IP_a$).
Then, if we simply use the Grover search, it needs $\sqrt{N}$ queries when $a=0$. 
(Recall that we assumed that MS-Grover does not have any information 
on the oracle table $T_f$ so that this seems to be the best we can do.) 
In contrast, if we use the BV algorithm, then we can get 
the value of $a$ with high probability since $IP_{a}'$ is so close to $IP_{a}$. 
(It is easy to compute the success probability, which may be omitted.)

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: 

51.tex
\section{Classical Lower and Upper Bounds}

We first give the classical lower bound and then prove the matching upper bound using the same oracle given in the previous section.

\begin{theorem}
Suppose that $f$ is an arbitrary oracle such that $\#(T_f)$ is $K$. Then any classical algorithm needs at least 
$\lfloor\frac{N}{K}\rfloor+\lfloor\log{K}\rfloor-2$ oracle calls to obtain a target in the worst case.
\end{theorem}

\begin{proof}
The following proof is due to the standard adversary argument. Let $A$ be any classical algorithm using the oracle $f$. 
Suppose that the target is $a \in \{0,1\}^n$. Then the execution of $A$ is described as follows:
(i) In the first round, $A$ calls the oracle with the predetermined value $x_0$ and the oracle answers with $d_0=f(a,x_0)$. 
(ii) In the second round, $A$ calls the oracle with value $x_1$, which is determined by $d_0$ and the oracle answers with $d_1=f(a,x_1)$. 
(iii) In the $(i+1)$-st round, $A$ calls the oracle with $x_{i}$ which is determined by $d_0,d_1,...,d_{i-1}$ and 
the oracle answers with $d_{i} = f(a, x_{i})$.
(iv) In the $m$-th round $A$ outputs the target $a$ which is determined by
$d_0, d_1,..., d_{m-1}$ and stops. Thus, the execution of $A$ is
completely determined by the sequence $(d_0, d_1,..., d_{m-1})$
which is denoted by $A(a)$. (Obviously, if we fix a specific target
$a$, then $A(a)$ is uniquely determined).

Let $m_0 = \lfloor N/K \rfloor + \lfloor \log K \rfloor -3$ and suppose that $A$
halts in the $m_0$-th round. We compute the sequence
$(c_0,c_1,\ldots,c_{m_0}),\, c_i\in\{0,1\}$, and another sequence 
$(L_0,L_1,\ldots,L_{m_0}),\, L_i\subseteq \{a|a\in\{0,1\}^n\}$, as follows (note
that $c_0,\ldots,c_{m_0}$ are similar to $d_0,...,d_{m-1}$ above and are chosen by the adversary): (i) $L_0 = \{0,1\}^n$.
(ii) Suppose that we have already computed $L_0,...,L_i$, and $c_0,...,c_{i-1}$. Let $x_i$ be the value
with which $A$ calls the oracle in the $(i+1)$-st round.
(Recall that $x_i$ is determined by $c_0,...,c_{i-1}$.)
Let $L^0 = \{s\, |\, f(s,x_i) =0\}$ and $L^1 = \{s\, |\, f(s,x_i)=1\}$.
Then if $|L_i \cap L^0| \geq |L_i \cap L^1|$ then we set $c_i = 0$ and $L_{i+1} = L_i \cap L^0$.
Otherwise, i.e., if $|L_i\cap L^0|<|L_i\cap L^1|$, then we set $c_i = 1$ and $L_{i+1} = L_{i} \cap L^1$.

Now we can make the following two claims.

\textbf{Claim 1.} $|L_{m_0}|\geq 2$. 
(Reason: Note that $|L_0|=N$ and the size of $L_i$ decreases as $i$
increases. By the construction of $L_i$, one can see that until
$|L_i|$ becomes $2K$, its size decreases additively by at most $K$ in
a single round and after that it decreases multiplically at most one
half. The claim then follows by a simple calculation.) 

\textbf{Claim 2.} If $a \in L_{m_0}$, then $(c_0,\ldots ,c_{m_0})=A(a)$.
(Reason: Obvious since $a\in L_0\cap L_1\cap \cdots\cap L_{m_0}$.)

Now it follows that there are two different $a_1$ and $a_2$ in $L_{m_0}$ such that $A(a_1)=A(a_2)$
by Claims 1 and 2. Therefore $A$ outputs the same answer for two
different targets $a_1$ and $a_2$, a contradiction. 
%$\Box$
\end{proof}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: 

52.tex
Next, we consider classical upper bounds for the hybrid oracle
discussed in Section 3. Recall that $K = 2^k$. 

\begin{theorem}
There exists a classical algorithm to find a target $a$ using
$O(\frac{N}{K}+\log{K})$ calls of $h_k$. 
\end{theorem}

\begin{proof} The algorithm consists of an exhaustive and a binary search.
First, we determine the first $n-k$ bits by fixing the last $k$ bits to all $0$'s and using exhaustive search. 
Second, we determine the last $k$ bits by using binary search.
This algorithm needs $2^{n-k} (=\frac{N}{K})$ queries in the exhaustive search, 
and $O(k)(=O(\log{K}))$ queries in the binary search. 
Therefore, the total complexity of this algorithm is $O(2^{n-k}+ k)
(=O(\frac{N}{K}+\log{K}))$. 
%$\Box$
\end{proof}
6.tex
\section{Concluding Remarks}
We have assumed through this paper that the size of $T_f$ is $N \times N$, i.e., 
the size of the domain and the size of the range of the Boolean function $F$ are the same. 
This restriction can of course be removed. 
For example, consider the 
$
\left(
\begin{array}{c}
N \\
K
\end{array}
\right) 
\times N
$ 
table $T_f$ which includes every string $y$ consisting of $K~1$'s and 
$(N-K)~0$'s in its rows. 
One can see this is exactly the same as the $K$-solution Grover search if 
our answer is to obtain an $x$ such that $f(a,x)=1$ and its complexity 
is $\Theta(\sqrt{\frac{N}{K}})$. 
Recall again that our present problem is different, 
i.e., we need to obtain $a$. 
We can also use Theorem~1, which implies (details are omitted) 
a lower bound of $\Omega(\sqrt{\frac{N}{K}})$. 
This lower bound is the same as the lower bound of MS-Grover and seems 
too weak as a lower bound of obtaining $a$. 
Fortunately it is not hard to improve this lower bound up to 
$\Omega(\sqrt{N})$ if $K=cN$: 
By selecting $K$ rows appropriately, we can obtain a smaller table 
which is similar to the table given in Fig.~4. 
Nevertheless, this $\sqrt{N}$ lower bound still seems weak; 
the real bound is probably much larger than $\sqrt{N}$. 
To obtain such a ``{\it huge}" lower bound for natural oracles 
(\cite{Amb02} has obtained one for an artificial oracle) 
should be interesting future work.


Another future direction is to find 
a different parameter which can control {\it upper} bounds of the query
complexity of evaluating functions. Note that the Hamming distance
between two rows of $T_f$ is $O(1)$ for the EQ-oracle and $N/2$ for
the IP-oracle. This fact might be a good hint for this direction. 
%The
%other is to consider different problems other than the search problem,
%for which the formulation of oracles by $F$ mentioned in Section 2
%should be good suggestions. 


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: 

bib.tex
\begin{thebibliography}{1}



\bibitem{Aar02}
S.~Aaronson.
\newblock Quantum lower bound for the collision problem.
\newblock In {\em Proceedings of the 34th Symposium on Theory of Computing},
  pages 635--642, 2002.

\bibitem{AC02}
 M.~Adcock and R.~Cleve.
 \newblock {A quantum Goldreich-Levin theorem with cryptographic applications}.
 \newblock In {\em Proceedings of the 19th International Symposium on Theoretical Aspects
   of Computer Science, H. Alt and A. Ferreira (Eds.),
   LNCS, Vol. 2285, Springer-Verlag}, pages
   323--334, 2002.

\bibitem{Amb02}
A.~Ambainis.
\newblock Quantum lower bounds by quantum arguments.
\newblock {\em Journal of Computer and System Sciences}, 64:750--767, 2002.

\bibitem{BS02}
H.~Barnum and M.~Saks.
\newblock A lower bound on the quantum query complexity of read-once functions.
\newblock In {\em quant-ph/0201007}, 2002.

\bibitem{BBCMW98}
R.~Beals, H.~Buhrman, R.~Cleve, M.~Mosca, and R.~de~Wolf.
\newblock Quantum lower bounds by polynomials.
\newblock In {\em Proceedings of 39th IEEE Symposium on Foundation of Computer
  Science}, pages 352--361, 1998.


\bibitem{BBBV97}
C.~Bennett, E.~Bernstein, G.~Brassard, and U.~Vazirani.
\newblock Strengths and weaknesses of quantum computing.
\newblock {\em SIAM J. Comput.}, 26(5):1510--1523, 1997.


\bibitem{BBHT96}
M.~Boyer, G.~Brassard, P.~H\o yer, and A. Tapp.
\newblock Tight bounds on quantum searching.
\newblock {\em Fortschritte der Physik}, vol. 46(4-5), 493-505, 1998.




\bibitem{Bernstein97}
E.~Bernstein and U.~Vazirani.
\newblock {Quantum complexity theory}.
\newblock {\em \it SIAM J. Comput.}, 26(5):1411--1473, October 1997.


\bibitem{Gro96}
L.~K. Grover.
\newblock A fast quantum mechanical algorithm for database search.
\newblock In {\em Proceedings of the 28th ACM Symposium on Theory of
  Computing}, pages 212--219, 1996.

\bibitem{Gru99}
J. Gruska.
\newblock Quantum Computing.
\newblock {\em McGraw-Hill}, 1999.

\bibitem{Ki02}
A.~Yu.~Kitaev, A.~H.~Shen and M.~N.~Vyalyi. 
\newblock Classical and quantum computation.
\newblock {\em American Mathematical Society}, 2002.


\bibitem{Yi02}
Y.~Shi.
\newblock Quantum lower bounds for the collision and the element distinctness
  problems.
\newblock In {\em Proceedings of the 43rd  IEEE Symposium on the Foundation of Computer
  Science}, 2002.

\bibitem{Vaz98}
U.~Vazirani.
\newblock On the power of quantum computation.
\newblock {\em Philosophical Transaction of the Royal Society of London, Series
  A}, (356):1759--1768, 1998.


\end{thebibliography}

main.tex
\documentclass[11pt]{article}
\usepackage[dvips]{graphicx}
\usepackage{latexsym}
\usepackage[fleqn]{amsmath}

\setlength{\textwidth}{170mm} 
\setlength{\textheight}{230mm}
\setlength{\topmargin}{-10mm}
\setlength{\parskip}{3mm}
% letter size hight = 279.4 mm
% letter size width = 215.9 mm
%\sidemargin = (\pagewidth(215.9) - \textwidth)/2 - 25.4 mm

\setlength{\oddsidemargin}{-2.45mm}
\setlength{\evensidemargin}{-2.45mm}
%\setlength{\evensidemargin}{-10mm}

%\renewcommand{\baselinestretch}{2.0}


\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}

\newcommand{\bsquare}{\hbox{\rule{6pt}{6pt}}}
\newcommand{\qedsymb}{\hfill{\rule{2mm}{2mm}}}
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\def\qed{\hspace*{\fill}
        \vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}\smallskip}
\newenvironment{proof}{\begin{trivlist}
  \item[\hspace{\labelsep}{\em\noindent Proof.~}]
  }{\qed\end{trivlist}}

% 100 word abstract
% 
%
%     *  a cover page, with the author's full name, address, fax number,
%        e-mail address, a 100-word abstract and keywords;


 \title{Quantum Evaluation of Multi-Valued Boolean Functions} 

   \author{Kazuo Iwama$^{\dag,  \dag\dag}$,  Akinori
     Kawachi$^{\dag,  \dag\dag}$,  
    Hiroyuki Masuda$^{\dag,  \dag\dag}$, \\
   Raymond H. Putra$^{\dag,  \dag\dag}$ and Shigeru Yamashita$^{\dag,
     \dag\dag\dag}$ \\    
   $^{\dag}$Quantum Computation and Information,  ERATO,  \\
   Japan Science and Technology Corporation (JST) \\
   $^{\dag\dag}$Graduate School of Informatics,  Kyoto University\\
   $^{\dag\dag\dag}$NTT Communication Science Laboratories\\ 
  E-mail: \{iwama,  kawachi,  hiroyuki, raymond, ger\}@kuis.kyoto-u.ac.jp.\\  
 }

\pagestyle{plain}

\begin{document}

% \thispagestyle{empty}
% \begin{description}
% \item[Title:] Quantum Query Complexity and the Number of Inverted States

% \item[Authors] Kazuo Iwama,  Akinori Kawachi, Hiroyuki Masuda, Rudy
%   Raymond H.P. and Shigeru Yamashita

% \item[Abstract:] 
% In this paper, we consider the relation between $K$, 
% the number of quantum states inverted by one quantum 
% oracle call, with the oracle query complexity, i.e., 
% the number of queries to obtain the solution out of 
% $N$ candidates. 
% It is well known that $K = 1$ and the query complexity 
% is $\Theta(\sqrt{N})$ for quantum EQ oracles, while 
% $K = N/2$ and the query complexity is $\Theta(1)$ for 
% quantum IP oracles. Under a proper assumption, we show 
% that the query complexity of general oracles, including 
% EQ and IP oracles, is $\Theta(\sqrt{N/K})$. We also show 
% that there is an quantum oracle whose query complexity is 
% $O(\sqrt{N/K})$. 

% \item[Keywords:] Quantum EQ oracle, Quantum IP oracle, Quantum Query Complexity

% \item[Contact Author]\ 
%   \begin{description}
%   \item[Name:] Dr. Shigeru Yamashita 
%   \item[Affiliation:] Quantum Computation and Information, ERATO,
%     Japan Science and Technology Corporation (JST)
%   \item[Tel\&Fax:]  Telephone: +81 75 257 0063   Fax: +81 75 257 0062
%   \item[E-MAIL:] yamasita@qci.jst.go.jp
%   \item[Address:]  Matsuo Building 2F, 406, Iseya-Che, 
%  Kamigyou-ku, Kyoto, Kyoto 602-0873 Japan
%  \end{description}
% \end{description}

% \renewcommand{\baselinestretch}{2}
% \large \normalsize
% \newpage



\setcounter{page}{1}
\date{}
\maketitle

%\section*{Abstract}
%
% In this paper, we consider the relation between $K$, the number of
% quantum states inverted by one quantum oracle call, with the oracle
% query complexity, i.e., the number of queries to obtain the solution
% out of $N$ candidates. 
% It is well known that $K = 1$ and the query complexity 
% is $\Theta(\sqrt{N})$ for quantum EQ oracles, while $K = N/2$ and the
% query complexity is $\Theta(1)$ for quantum IP oracles.
% Under a proper assumption, we show that the query complexity of
% general oracles, including EQ and IP oracles, is $\Theta(\sqrt{N/K})$.
% We also show that there is an quantum oracle whose query complexity is 
% $O(\sqrt{N/K})$. 


%\renewcommand{\baselinestretch}{2}
%\Large \normalsize
\input{0.tex}
\input{1.tex}
\input{2.tex}
\input{3.tex}
\input{4.tex}
\input{51.tex}
\input{52.tex}
\input{6.tex}
\input{bib.tex}

%\bibliography{ref_masuda.bib}
%\bibliographystyle{plain}

%\begin{thebibliography}{1}



%\bibitem{Aar02}
%S.~Aaronson.
%\newblock Quantum lower bound for the collision problem.
%\newblock In {\em Proceedings of the 34th Symposium on Theory of Computing},
%  pages 635--642, 2002.

%\bibitem{AC02}
% M.~Adcock and R.~Cleve.
% \newblock {A quantum Goldreich-Levin theorem with cryptographic applications}.
% \newblock In {\em Proceedings of the 19th International Symposium on Theoretical Aspects
%   of Computer Science, H. Alt and A. Ferreira (Eds.),
%   LNCS, Vol. 2285, Springer-Verlag}, pages
%   323--334, 2002.

%\bibitem{Amb02}
%A.~Ambainis.
%\newblock Quantum lower bounds by quantum arguments.
%\newblock {\em Journal of Computer and System Sciences}, 64:750--767, 2002.

%\bibitem{BS02}
%H.~Barnum and M.~Saks.
%\newblock A lower bound on the quantum query complexity of read-once functions.
%\newblock In {\em quant-ph/0201007}, 2002.

%\bibitem{BBCMW98}
%R.~Beals, H.~Buhrman, R.~Cleve, M.~Mosca, and R.~de~Wolf.
%\newblock Quantum lower bounds by polynomials.
%\newblock In {\em Proceedings of 39th IEEE Symposium on Foundation of Computer
%  Science}, pages 352--361, 1998.


%\bibitem{BBBV97}
%C.~Bennett, E.~Bernstein, G.~Brassard, and U.~Vazirani.
%\newblock Strengths and weaknesses of quantum computing.
%\newblock {\em SIAM J. Comput.}, 26(5):1510--1523, 1997.


%\bibitem{BBHT96}
%M.~Boyer, G.~Brassard, P.~H\o yer, and A. Tapp.
%\newblock Tight bounds on quantum searching.
%\newblock {\em Fortschritte der Physik}, vol. 46(4-5), 493-505, 1998.




%\bibitem{Bernstein97}
%E.~Bernstein and U.~Vazirani.
%\newblock {Quantum complexity theory}.
%\newblock {\em \it SIAM J. Comput.}, 26(5):1411--1473, October 1997.


%\bibitem{Gro96}
%L.~K. Grover.
%\newblock A fast quantum mechanical algorithm for database search.
%\newblock In {\em Proceedings of the 28th ACM Symposium on Theory of
%  Computing}, pages 212--219, 1996.

%\bibitem{Gru99}
%J. Gruska.
%\newblock {\em Quantum Computing}.
%\newblock McGrow-Hill, London, 1999.

%\bibitem{Ki02}
%A.~Yu.~Kitaev, A.~H.~Shen and M.~N.~Vyalyi. 
%\newblock Classical and quantum computation.
%\newblock {\em Americn Mathematical Society}, 2002.


%\bibitem{Yi02}
%Y.~Shi.
%\newblock Quantum lower bounds for the collision and the element distinctness
%  problems.
%\newblock In {\em Proceedings of the 43rd  IEEE Symposium on the Foundation of Computer
%  Science}, 2002.

%\bibitem{Vaz98}
%U.~Vazirani.
%\newblock On the power of quantum computation.
%\newblock {\em Philosophical Transaction of the Royal Society of London, Series
%  A}, (356):1759--1768, 1998.


%\end{thebibliography}



\end{document}



quant-ph0304131.extracted_bib
\begin{thebibliography}{1}



\bibitem{Aar02}
S.~Aaronson.
\newblock Quantum lower bound for the collision problem.
\newblock In {\em Proceedings of the 34th Symposium on Theory of Computing},
  pages 635--642, 2002.

\bibitem{AC02}
 M.~Adcock and R.~Cleve.
 \newblock {A quantum Goldreich-Levin theorem with cryptographic applications}.
 \newblock In {\em Proceedings of the 19th International Symposium on Theoretical Aspects
   of Computer Science, H. Alt and A. Ferreira (Eds.),
   LNCS, Vol. 2285, Springer-Verlag}, pages
   323--334, 2002.

\bibitem{Amb02}
A.~Ambainis.
\newblock Quantum lower bounds by quantum arguments.
\newblock {\em Journal of Computer and System Sciences}, 64:750--767, 2002.

\bibitem{BS02}
H.~Barnum and M.~Saks.
\newblock A lower bound on the quantum query complexity of read-once functions.
\newblock In {\em quant-ph/0201007}, 2002.

\bibitem{BBCMW98}
R.~Beals, H.~Buhrman, R.~Cleve, M.~Mosca, and R.~de~Wolf.
\newblock Quantum lower bounds by polynomials.
\newblock In {\em Proceedings of 39th IEEE Symposium on Foundation of Computer
  Science}, pages 352--361, 1998.


\bibitem{BBBV97}
C.~Bennett, E.~Bernstein, G.~Brassard, and U.~Vazirani.
\newblock Strengths and weaknesses of quantum computing.
\newblock {\em SIAM J. Comput.}, 26(5):1510--1523, 1997.


\bibitem{BBHT96}
M.~Boyer, G.~Brassard, P.~H\o yer, and A. Tapp.
\newblock Tight bounds on quantum searching.
\newblock {\em Fortschritte der Physik}, vol. 46(4-5), 493-505, 1998.




\bibitem{Bernstein97}
E.~Bernstein and U.~Vazirani.
\newblock {Quantum complexity theory}.
\newblock {\em \it SIAM J. Comput.}, 26(5):1411--1473, October 1997.


\bibitem{Gro96}
L.~K. Grover.
\newblock A fast quantum mechanical algorithm for database search.
\newblock In {\em Proceedings of the 28th ACM Symposium on Theory of
  Computing}, pages 212--219, 1996.

\bibitem{Gru99}
J. Gruska.
\newblock Quantum Computing.
\newblock {\em McGraw-Hill}, 1999.

\bibitem{Ki02}
A.~Yu.~Kitaev, A.~H.~Shen and M.~N.~Vyalyi. 
\newblock Classical and quantum computation.
\newblock {\em American Mathematical Society}, 2002.


\bibitem{Yi02}
Y.~Shi.
\newblock Quantum lower bounds for the collision and the element distinctness
  problems.
\newblock In {\em Proceedings of the 43rd  IEEE Symposium on the Foundation of Computer
  Science}, 2002.

\bibitem{Vaz98}
U.~Vazirani.
\newblock On the power of quantum computation.
\newblock {\em Philosophical Transaction of the Royal Society of London, Series
  A}, (356):1759--1768, 1998.


\end{thebibliography}