\documentclass{article}
\usepackage{amssymb}


\title{On the solution of trivalent decision problems by quantum state identification}

\author{Karl Svozil\footnote{email:~svozil@tuwien.ac.at}\\
        Institut f\"ur Theoretische Physik, University of Technology Vienna,\\
        Wiedner Hauptstra\ss e 8-10/136, A-1040 Vienna, Austria\\ \\
        and \\   \\
        Josef Tkadlec\footnote{email:~tkadlec@fel.cvut.cz}\\
        Department of Mathematics, Faculty of Electrical Engineering, \\
        Czech Technical University,\\
        166\,27 Praha, Czech Republic
       }

\begin{document}
\maketitle
\begin{abstract}
The trivalent functions of a trit can be grouped into equipartitions of three elements. We discuss the separation of the corresponding functional classes by quantum state identifications.
\end{abstract}



%\pacs{03.67.Lx,03.65.Ud}
%\keywords{Trits, trivalent decision problems, quantum state identification}


\section{Quantum computation by state identification}

One of the advantages of quantum computation \cite{Gruska,nielsen-book,mermin-07,benn:97,Ozhigov:1997,bbcmw-01,cleve-99,fortnov-03}
over classical algorithms \cite{rogers1,odi:89} is due to
the fact that throughout a quantum computation, some classically useful information
can be encoded by distributing it over different particles or quanta,
such that \cite{mermin-02,svozil-2005-ko}
\begin{itemize}
\item
measurements of {\em single} quanta are irrelevant, yield ``random'' results,
and even destroy the original information (by asking complementary questions);
\item
well defined correlations exist and can be defined among different particles or quanta ---
even to the extend that a state is solely defined by propositions
about {\em collective} (or {\em relative})  properties of the particles or quanta involved;
and
\item
identifying a given state of a quantized system can yield information about
{\em collective} (or {\em relative})  properties of the particles or quanta involved.
\end{itemize}
That is, unlike classical physical states, quantum states can also be characterized with respect to
propositions and properties not encoded into a {\em single} quantum, but ``spread among''
quanta in an entangled multi-partite state
\cite{zeil-99,zeil-bruk-99,zeil-bruk-99a,zeil-bruk-02,DonSvo01,svozil-2002-statepart-prl,svozil-2003-garda}.
Stated differently, according to Brukner, Zukowski and Zeilinger~\cite{zeil-Zuk-bruk-01},
the essence of entanglement can be identified by two observations: the finiteness of the amount of information per participating quantum,
and the possibility that {\em ``the information in a composite system resides more
in the correlations than in properties of individuals.''}
This is also evident from the fact that entangled states cannot be represented as the product of the individual states of the participating quanta
(cf. Ref.~\cite{mermin-07}, Sect. 1.5).

Suppose one is interested in a decision problem which could be associated with some {\em ``collective''} property or behaviour;
related to or involving, for instance,
\begin{itemize}
\item
a function over a wide range of its arguments,
\item
which is of ``comparative'' nature; that is, only the relative functional values count;
\item
for which the single functional values are irrelevant;
e.g., are of no interest, ``annoying'' or are otherwise unnecessary.
\end{itemize}
Then it is not completely unreasonable to speculate that one could use the
kind of distributive  information capacity encountered in the quantum physics of multipartite states
for a more effective (encryption of the) solution.

The potentiality to quantum mechanically solve decision problems
by quantum computing an appropriate multipartite state is not only present in binary decision problems of the usual type,
such as Deutsch's algorithm \cite{deutsch,deutsch:92,cleve:98,nielsen-book,mermin-07}.
It can be extended to $d$-ary decision problems on dits. (For the related state determination problem,
see  Ref.~\cite{zeil-99}, footnote 6,
and Ref.~\cite{svozil-2002-statepart-prl}.)


In what follows we shall consider as the simplest of such problems
the trivalent functions of one trit.
We shall group them in three functional classes
corresponding to an equipartition of the set of functions into three elements.
We then investigate
the possibility to separate each of these classes by
quantum state identifications \cite{DonSvo01,svozil-2002-statepart-prl}.


A strategy to identify an observable associated with the solution of a decision problem
can be implemented
via the method of general state identification  \cite{DonSvo01,svozil-2002-statepart-prl,svozil-2003-garda}
as follows \cite{svozil-2005-ko}:
\begin{enumerate}
\item
Re-encode the behaviour of the algorithm or function involved in the decision problem
into an orthogonal set of states, such that every distinct function results in
a {\em single} distinct state orthogonal to all the other ones.
Suppose that this is impossible because the number of functions exceeds the number of orthogonal states, then
\begin{enumerate}
\item
one could attempt to find a suitable representation of the functions in terms of the base states;
e.g., the generalized Deutsch algorithm in Ref.~\cite{svozil-2005-ko}.
\item
Alternatively, the dimension of the Hilbert space could be increased by the addition of auxiliary Qbits.
The latter method is hardly feasible for general $q$-ary functions of $n$ dits,
since the number of possible functions increases with $q^{d^n}$, as compared to the dimension $d^n$ of the Hilbert space
of the input states.

In our case of trivalent ($q=3$) functions of a single ($n=1$) trit ($d=3$), there are 27 such functions on three-dimensional Hilbert space.
[For the original Deutsch algorithm computing the parity (constancy or nonconstancy) of the four binary functions of one bit, there are  $2^{2^1}=4$ such functions.]
For a one-to-one correspondence between functions and orthogonal states,
trivalent decision problems among the 27 trivalent functions of a single trit  require
three three-state quanta associated with
the set of $3^3=27$ states corresponding to some orthogonal base in ${\mathbb{C}}^3\otimes {\mathbb{C}}^3\otimes {\mathbb{C}}^3$.
\end{enumerate}


\item
Create three {\em equipartitions} containing  three elements per partition --- thus, every such partition element contains nine orthogonal states ---
such that
\begin{enumerate}
\item
{\em one of the partitions} corresponds to the solution of the decision problem.
\item
The other two partitions ``complete'' the system of partitions such that
the set theoretic intersection of any three arbitrarily chosen elements of the three partition
with {\em one element per partition} always yields a {\em single} base state.
\end{enumerate}

\item
Formally, the three partitions correspond to a system of three co-measurable
{\em filter operators} $\textsf{\textbf{F}}_i$, $i=1,2,3$
with the following properties:
\begin{enumerate}
\item[(F1)]
Every filter $\textsf{\textbf{F}}_i$
corresponds to an operator (or a set of operators)
which generates one of the three
equipartitions.
(A filter is said to separate two eigenstates if their eigenvalues are different.)
\item[(F2)]
From each one of the three partitions of (F1), take an arbitrary element.
The intersection of these elements of all different partitions (one element per partition)
results in a {\it single} one of the $27$ different states.
\item[(F3)]
The union of all those single states generated by the intersections of (F2)
is the entire set of states.
\end{enumerate}

\item
As the first partition corresponds to the solution of the decision problem,
the corresponding first filter operator corresponds to the ``quantum oracle'' operator solving the decision problem
on the set of states corresponding to the different cases or branches involved --- one state per case or branch.

\end{enumerate}


Ideally, in order for the above strategy to work in three-dimensional Hilbert space of a single Qtrit,
one should find a function $g$ on the set of trivalent functions of a trit ``folding'' the decision problem  into a  {\em single} triple of orthogonal vectors.
However, as has been already pointed out, because the number of functions may exceed the dimension of the Hilbert space, this task might be impossible.
For some decision problem, it might still be possible to find a suitable vector representation for the functional values.
Another possibility might be the enlargement of Hilbert space by the inclusion of more auxiliary Qbits.

\section{Options for ``folding'' the decision problem into a single Qtrit}

For the sake of demonstration, let us again consider our example of trivalent functions of a single trit.
Formally, we shall consider the functions $$f \,{:}\linebreak[0]\,\;
\{-,0,+\} \to \{-,0,+\}$$ which will be denoted as triples
$$\bigl( f(-), f(0), f(+) \bigr)\; .$$
There are $3^{3^1} = 27$ such functions.
They can be enumerated in lexicographic order ``$-<0<+$'' as in Table~\ref{2007-tkadlec-svozil-t1}.
\begin{table*}
\label{2007-tkadlec-svozil-t1}
\renewcommand{\tabcolsep}{2pc} % enlarge column spacing
\renewcommand{\arraystretch}{1.2} % enlarge line spacing
\begin{tabular}{c}
\hline
$
\begin{array}{lllll}
\begin{array}{ll}
f_{0}: & (---)\\  f_{1}: & (--0)\\  f_{2}: & (--+)\\ f_{3}: & (-0-)\\  f_{4}: & (-00)\\  f_{5}: & (-0+)\\  f_{6}: & (-+-)\\  f_{7}: & (-+0)\\  f_{8}: & (-++)\\
\end{array}
&   \qquad  &
\begin{array}{ll}
f_{9}: & (0--)\\  f_{10}: & (0-0)\\  f_{11}: & (0-+)\\ f_{12}: & (00-)\\  f_{13}: & (000)\\  f_{14}: & (00+)\\ f_{15}: & (0+-)\\  f_{16}: & (0+0)\\  f_{17}: & (0++)\\
\end{array}
&   \qquad &
\begin{array}{ll}
f_{18}: & (+--)\\  f_{19}: & (+-0)\\  f_{20}: & (+-+)\\ f_{21}: & (+0-)\\  f_{22}: & (+00)\\  f_{23}: & (+0+)\\ f_{24}: & (++-)\\  f_{25}: & (++0)\\  f_{26}: & (+++)
\end{array}
\end{array}
$   \\
\hline
\end{tabular}
\caption{Enumeration of all trivalent functions of a single trit  in lexicographic order ``$-<0<+$.''}
\end{table*}

 The trits will be coded by
elements of some  orthogonal base in ${\mathbb{ C}}^3$. Without loss of
generality we may take
$(1,0,0) = |-\rangle$, $(0,1,0) = |0\rangle$,
$(0,0,1) = |+\rangle $.

For a given ``quantum oracle'' function
$$g \,{:}\linebreak[0]\,\;
\{-,0,+\} \to {\mathbb{ C}}$$
we represent a function
$f
\,{:}\linebreak[0]\,\; \{-,0,+\} \to \{-,0,+\}$ by a linear subspace of
${\mathbb{ C}}^3$ generated by the vector
  $$g\bigl(f(-)\bigr)\,|-\rangle +
    g\bigl(f(0)\bigr)\,|0\rangle +
    g\bigl(f(+)\bigr)\,|+\rangle\,,$$
i.e., by the vector
$$\bigl(g(f(-)), g(f(0)), g(f(+))\bigr).$$


In order to be able to implement the first, re-encoding, step of the above strategy,
we will be searching for a function $g$ such that the subspaces representing functions
$\{-,0,+\} \to \{-,0,+\}$ are nonzero and form the smallest possible number --- ideally only one ---
of orthogonal triples.

First, let us show that we may find a function $g$ such that we obtain three orthogonal triples of orthogonal vectors,
each one of the three triples containing nine triples of the form  $\bigl( f(-), f(0), f(+) \bigr)$  associated with cases of the functions $f$
which can grouped into three partitions of three triples of the form $\bigl( f(-), f(0), f(+) \bigr)$.
Let the values of $g$ be the $\sqrt[3]{1}$ (in the set
of complex numbers). Let us, for the sake of simplicity and briefness of notation,
denote $\alpha ={\rm e}^{2\pi {\rm i}/3}=-{1\over 2}(1-i\sqrt{3})$. Then the values of $g$ are
$\alpha$, $\alpha^2 = \alpha^\ast  = {\rm e}^{-2\pi {\rm i}/3}=-{1\over 2}(1+i\sqrt{3})$ and $\alpha^3=1$. Moreover, $\alpha
\alpha^\ast  = 1$ and $\alpha + \alpha^\ast = -1$. Then, the ``quantum
oracle'' function $g$ might be given by the following table:
  $$
  \begin {array}{c||c|c|c}

  x    & -       & 0 & +\\\hline
  g(x) & \alpha^\ast  & 1 & \alpha    \\

  \end {array}
  $$
and (if we identify `$-$' with `$-1$' and `$+$' with `$+1$') might be
expressed by
  $$g(x) = \alpha^x = {\rm e}^{2\pi{\rm i}x/3}\,.$$



$g$ maps the 27 triples of functions $\bigl( f(-), f(0), f(+) \bigr)$ into nine groups of three triples of functions,
such that triples within the nine groups are assigned the same vector (except a nonzero multiple)
by the scheme enumerated
in Table~\ref{2007-tkadlec-svozil-t0}.
In every column we obtain an orthogonal triple of vectors
$$
\begin {array}{rcl}
t_1&=&\left\{(1,1,1),(1,1,\alpha),(1,1,\alpha^\ast )\right\}, \\
t_2&=&\left\{(1,\alpha,\alpha^\ast ),(1,\alpha,1), (1,\alpha^\ast ,1)\right\},\\
t_3&=&\left\{(1,\alpha^\ast ,\alpha),(\alpha,1,1),(\alpha^\ast ,1,1) \right\}.
\end {array}
$$
Moreover,
vectors from different orthogonal triples are apart by the same angle $\phi$, for which
$\cos \phi = \sqrt3/3$.



Now, let us prove by contradiction that in general the function $g$ cannot be defined
in such a way that we obtain at most two orthogonal triples of subspaces.
This implies that $g$ cannot ``generate'' a {\em single} triple of orthogonal vectors or subspaces,
--- with nine different functions $\bigl( f(-), f(0), f(+) \bigr)$ per element element of that triple ---
required for the method of computation by state identification in three-dimensional Hilbert space.

For the sake of contradiction, let us suppose that this proposition is
false, e.g., that there is a function $g$ such that we obtain at most two
orthogonal triples of subspaces.


First, all values $g(-), g(0), g(+)$ are nonzero [if, e.g., $g(-) = 0$
then the vector $\bigl(g(-),g(-),g(-)\bigr)$ assigned to the function
$(-,-,-)$ is a zero vector]. Hence, we obtain a vector
$\bigl(g(-),g(-),g(-)\bigr)$ that is a nonzero multiple of the vector
$(1,1,1)$.


Second, $g(-), g(0), g(+)$ cannot have the same value (in this case we
obtain only one subspace generated by the vector $(1,1,1)$).


Let us show that the vectors assigned to the functions $(-,-,0)$ and
$(-,0,0)$ are not orthogonal. Indeed, if $\bigl(g(-),g(-),g(0)\bigr)$ and
$\bigl(g(-),g(0),g(0)\bigr)$ are orthogonal, then they have a zero scalar
product $0 = g(-) \,  {g(-)}^\ast + g(-) \,  {g(0)}^\ast + g(0) \,
{g(0)}^\ast = |g(-)|^2 + g(-) \,  {g(0)}^\ast + |g(0)|^2$ and
therefore $g(-) \, {g(0)}^\ast$ is a negative real number. Hence $0 =
|g(-)|^2 - |g(-)| \cdot |g(0)| + |g(0)|^2 = \bigl( |g(-)| - \frac 12 \,
|g(0)| \bigr)^2 + \frac 34 \, |g(0)|^2$ and therefore $g(0) = 0$ that is
impossible.


Let us show that all values $g(-), g(0), g(+)$ are different. Indeed, let,
e.g., $g(-) = g(0)$. Since $g(-), g(0), g(+)$ cannot have the same value, we
obtain $g(+) \neq g(-)$ and therefore the vectors $\bigl( g(-), g(-), g(+)
\bigr)$ and $\bigl( g(-), g(+), g(+) \bigr)$ are not multiples of the vector
$(1,1,1)$ and do not generate the same subspace. Analogously as in the
previous paragraph we can show that the vectors $\bigl( g(-), g(-), g(+)
\bigr)$ and $\bigl( g(-), g(+), g(+) \bigr)$ are not orthogonal, hence they
do not belong to one orthogonal triple and therefore at least one of
these vectors is orthogonal to $(1,1,1)$. Let, e.g., $\bigl( g(-), g(-),
g(+) \bigr)$ is orthogonal to $(1,1,1)$. Then we obtain a zero scalar
product $0 = 2\,g(-) + g(+)$ and therefore the vector $\bigl( g(-), g(-),
g(+) \bigr)$ is a multiple of $(1,1,-2)$. The subspace making an orthogonal
triple with subspaces generated by vectors $(1,1,1)$ and $(1,1,-2)$ is
generated by $(1,-1,0)$. But, since all values $g(-), g(0), g(+)$ are
nonzero, this subspace is not obtained.

\begin{table*}
\label{2007-tkadlec-svozil-t0}
%\renewcommand{\tabcolsep}{2pc} % enlarge column spacing
\renewcommand{\arraystretch}{1.2} % enlarge line spacing
\begin{tabular}{c}
\hline
\small
$
  \begin {array}{ccc}

\;\\
\left.
  \begin {array}{c}
  (-,-,-) \\
  (0,0,0) \\
  (+,+,+) \\
  \end {array}
\right\}
\mapsto  (1,1,1)
&
\left.
  \begin {array}{ccc}
 (-,-,0) \\
(0,0,+)\\
(+,+,-)\\
\end {array}
\right\}
 \mapsto (1,1,\alpha)
&
\left.
  \begin {array}{ccc}
(-,-,+) \\
(0,0,-)\\
(+,+,0) \\
\end {array}
\right\}
 \mapsto (1,1,\alpha^\ast ) \\
\;\\
%%%
\left.
  \begin {array}{ccc}
 (-,0,+)\\
 (0,+,-) \\
 (+,-,0)\\
\end {array}
\right\}
\mapsto  (1,\alpha,\alpha^\ast )
&
\left.
  \begin {array}{ccc}
&(-,0,-)\\
&(0,+,0) \\
&(+,-,+)\\
\end {array}
\right\}
\mapsto  (1,\alpha,1)
&
\left.
  \begin {array}{ccc}
&(-,+,-)\\
&(0,-,0)   \\
&(+,0,+)\\
\end {array}
\right\}
 \mapsto (1,\alpha^\ast ,1)\\
\;\\
%%%
 \left.
  \begin {array}{ccc}
 (-,+,0)\\
 (+,0,-) \\
 (0,-,+)\\
\end {array}
\right\}
\mapsto (1,\alpha^\ast ,\alpha)
&
\left.
  \begin {array}{ccc}
&(0,-,-)\\
&(+,0,0) \\
&(-,+,+)\\
\end {array}
\right\}
 \mapsto (\alpha,1,1)
&
\left.
  \begin {array}{ccc}
&(+,-,-)\\
&(-,0,0)\\
&(0,+,+)\\
\end {array}
\right\}
 \mapsto  (\alpha^\ast ,1,1)\\
\;\\

  \end {array}
  $
\\
\hline
\end{tabular}
\caption{Enumeration of the map $g$ of all trivalent functions $\bigl( f(-), f(0), f(+) \bigr)$ into nine groups of three triples of functions,
such that triples within the nine groups are assigned the same vector (except a nonzero multiple).}
\end{table*}

We have shown that the subspaces assigned to functions $(-,-,0)$ and
$(-,0,0)$ are not orthogonal and do not coincide (otherwise $g(-) = g(0)$).
Hence they do not belong to one orthogonal triple and at least one of them
should belong to an orthogonal triple with the space generated by the vector
$(1,1,1)$. Let, e.g., $\bigl( g(-), g(-), g(0) \bigr)$ is orthogonal to the
vector $(1,1,1)$. Then we obtain a zero scalar product $0 = 2 \, g(-) +
g(0)$. Analogously (using the transformations $(-,0) \to (-,+)$ and $(-,0)
\to (0,+)$) we can show that one of the vectors $\bigl( g(-), g(-),
g(+)\bigr)$ and $\bigl( g(-), g(+), g(+) \bigr)$ ($\bigl( g(0), g(0), g(+)
\bigr)$ and $\bigl( g(0), g(+), g(+) \bigr)$, resp.) is orthogonal to the
vector $(1,1,1)$ and therefore $0 = 2 \, g(-) + g(+)$ or $0 = g(-) + 2 \,
g(+)$ ($0 = 2 \, g(0) + g(+)$ or $0 = g(0) + 2 \, g(+)$, resp.). Since all
values $g(-), g(0), g(+)$ are different and $0 = 2 \, g(-) + g(0)$, we
obtain that $0 \neq 2 \, g(-) + g(+)$ and $0 \neq g(0) + 2 \, g(+)$. Hence
$0 = g(-) + 2 \, g(+)$ and $0 = 2 \, g(0) + g(+)$. The system of equations
$0 = 2 \, g(-) + g(0)$, $0 = g(-) + 2 \, g(+)$ and $0 = 2 \, g(0) + g(+)$
has the only solution $g(-) = g(0) = g(+) = 0$, which results in a complete
contradiction.

\section{Increasing the dimension of state space by additional quanta}

The geometric constraints obtained in the last section can be interpreted
as the impossibility to ``fold'' a decision problem
into an appropriate quantum state identification in low-dimensional Hilbert space.
As has been mentioned already, this can be circumvented by the introduction of additional quanta,
thereby increasing the dimension of Hilbert space.
In that way, the functions of a small number of bits can be mapped one-to-one onto orthogonal quantum states.
However, this strategy fails for a large number of arguments, since the ratio
of the number of $q$-ary functions of $n$ dits to the dimension of the Hilbert space of $n$ dits
$d^{-n} q^{d^n}$ increases fast with growing $n$.

One possibility of mapping the 27 trivalent functions of one trit into the 27 orthogonal base states of the Hilbert space spanned by three Qtrits
is
$$|h\bigl(f(-)\bigr)\rangle \otimes
    |h\bigl(f(0)\bigr)\rangle \otimes
    |h\bigl(f(+)\bigr)\rangle\,,$$
with $h= id$ being the identity function.
A reversible implementation of this function can be given by
$$
\begin{array}{lll}
&&h:\; \prod_{x \in \{-,0,+\}} \vert x\rangle |0\rangle  \rightarrow
\\
&&
\quad \rightarrow
\prod_{x \in \{-,0,+\}} \vert x\rangle |0\oplus h(f(x))\rangle =  \\
&&
\qquad \qquad \prod_{x \in \{-,0,+\}} \vert x\rangle |h(f(x))\rangle
\,
,
\end{array}
$$
where ``$\oplus$'' stands for modulo-two addition.

For the sake of demonstration, consider the following trivalent decision problem associated with the three triples of vectors
$t_1$,
$t_2$, and
$t_3$ as follows:
\begin{quote}
{\em
Given some trivalent function of a single trit $f_i (x)$, $i\in \{0,\ldots ,26\}$, $x\in \{-,0,+\}$.
Find the triple of vectors $t$ among the three triples
$t_1$,
$t_2$ and
$t_3$, such that
$g(f_i)\in t$.
}
\end{quote}


\section{Summary}

In summary we find that, in three-dimensional Hilbert space, we cannot solve the type of trivalent decision problems
discussed above by a single query.
Such a behavior has already been observed for the problem to find the
parity of an unknown binary function $f:\{0,1\}^k \rightarrow \{0,1\}$ of $k$ bits,
which turned out to be quantum computationally hard
\cite{Farhi-98,bbcmw-01,Miao-2001,orus-04,stadelhofer-05}.
We conjecture that this hardness increases with the number $d$ of possible states of a single bit.

We have also explicitly discussed a trivalent decision problem which can be interpreted as the solution of a quantum
state identification problem.



\section *{Acknowledgements}


The work was supported by the research plan of the Ministry of Education of
the Czech Republic no.~6840770010 and by the grant of the Grant Agency of
the Czech republic no.~201/07/1051 and by the exchange agreement
of both of our universities.


%\bibliography{svozil}
%\bibliographystyle{osa}
%\bibliographystyle{apsrev}


\begin{thebibliography}{10}
\newcommand{\enquote}[1]{``#1''}
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{{#1}}\fi
\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{}\fi

\bibitem{Gruska}
J.~Gruska, {\em Quantum Computing\/} (McGraw-Hill, London, 1999).

\bibitem{nielsen-book}
M.~A. Nielsen and I.~L. Chuang, {\em Quantum Computation and Quantum
  Information\/} (Cambridge University Press, Cambridge, 2000).

\bibitem{mermin-07}
N.~D. Mermin, {\em Quantum Computer Science\/} (Cambridge University Press,
  Cambridge, 2007).

\bibitem{benn:97}
C.~H. Bennett, E.~Bernstein, G.~Brassard, and U.~Vazirani, \enquote{Strengths
  and Weaknesses of Quantum Computing,} SIAM Journal on Computing {\bf 26},
  1510--1523 (1997).
\newline http://dx.doi.org/10.1137/S0097539796300933

\bibitem{Ozhigov:1997}
Y.~Ozhigov, \enquote{Quantum Computer Can Not Speed Up Iterated Applications of
  a Black Box,} Lecture Notes In Computer Science {\bf 1509}, 152--159 (1998).
\newline http://dx.doi.org/10.1007/3-540-49208-9

\bibitem{bbcmw-01}
R.~Beals, H.~Buhrman, R.~Cleve, M.~Mosca, and R.~de~Wolf, \enquote{Quantum
  Lower Bounds by Polynomials,} Journal of the ACM {\bf 48}, 778--797 (2001).
\newline http://dx.doi.org/10.1145/502090.502097

\bibitem{cleve-99}
R.~Cleve, \enquote{An Introduction to Quantum Complexity Theory,} in {\em
  Collected Papers on Quantum Computation and Quantum Information Theory\/},
  C.~Macchiavello, G.~Palma, and A.~Zeilinger, eds.,  pp. 103--127 (2000).

\bibitem{fortnov-03}
L.~Fortnow, \enquote{One complexity theorist's view of quantum computing,}
  Theoretical Computer Science {\bf 292}, 597--610 (2003).
\newline http://dx.doi.org/10.1016/S0304-3975(01)00377-2

\bibitem{rogers1}
H.~{Rogers, Jr.}, {\em Theory of Recursive Functions and Effective
  Computability\/} (MacGraw-Hill, New York, 1967).

\bibitem{odi:89}
P.~Odifreddi, {\em Classical Recursion Theory, Vol. 1\/} (North-Holland,
  Amsterdam, 1989).

\bibitem{mermin-02}
N.~D. Mermin, \enquote{From {C}bits to {Q}bits: Teaching computer scientists
  quantum mechanics,} American Journal of Physics {\bf 71}, 23--30 (2003).
\newline http://dx.doi.org/10.1119/1.1522741

\bibitem{svozil-2005-ko}
K.~Svozil, \enquote{Characterization of quantum computable decision problems by
  state discrimination,} in {\em Quantum Theory: Reconsideration of Foundations
  - 3\/}, G.~Adenier, A.~Khrennikov, and T.~M. Nieuwenhuizen, eds.,  {\bf 810},
  271--279 (2006).
\newline http://link.aip.org/link/?APC/810/271/1

\bibitem{zeil-99}
A.~Zeilinger, \enquote{A Foundational Principle for Quantum Mechanics,}
  Foundations of Physics {\bf 29}, 631--643 (1999).
\newline http://dx.doi.org/10.1023/A:1018820410908

\bibitem{zeil-bruk-99}
{\v{C}}.~Brukner and A.~Zeilinger, \enquote{Malus' law and quantum
  information,} Acta Physica Slovaca {\bf 49}, 647--652 (1999).

\bibitem{zeil-bruk-99a}
{\v{C}}.~Brukner and A.~Zeilinger, \enquote{Operationally invariant information
  in quantum mechanics,} Physical Review Letters {\bf 83}, 3354--3357 (1999).

\bibitem{zeil-bruk-02}
{\v{C}}.~Brukner and A.~Zeilinger, \enquote{Information and fundamental
  elements of the structure of quantum theory,} in {\em Time, Quantum and
  Information\/}, L.~Castell and O.~Ischebek, eds.  (Springer, Berlin, 2003),
  pp. 323--355.

\bibitem{DonSvo01}
N.~Donath and K.~Svozil, \enquote{Finding a state among a complete set of
  orthogonal ones,} Physical Review A (Atomic, Molecular, and Optical Physics)
  {\bf 65}, 044\,302 (2002).
\newline http://dx.doi.org/10.1103/PhysRevA.65.044302

\bibitem{svozil-2002-statepart-prl}
K.~Svozil, \enquote{Quantum information in base $n$ defined by state
  partitions,} Physical Review A (Atomic, Molecular, and Optical Physics) {\bf
  66}, 044\,306 (2002).
\newline http://dx.doi.org/10.1103/PhysRevA.66.044306

\bibitem{svozil-2003-garda}
K.~Svozil, \enquote{Quantum information via state partitions and the context
  translation principle,} Journal of Modern Optics {\bf 51}, 811--819 (2004).
\newline http://dx.doi.org/10.1080/09500340410001664179

\bibitem{zeil-Zuk-bruk-01}
{\v{C}}.~Brukner, M.~Zukowski, and A.~Zeilinger, \enquote{The essence of
  entanglement,}  (2002), translated to Chinese by Qiang Zhang and Yond-de
  Zhang, New Advances in Physics (Journal of the Chinese Physical Society).
\newline http://xxx.lanl.gov/abs/quant-ph/0106119

\bibitem{deutsch}
D.~Deutsch, \enquote{Quantum theory, the {C}hurch-{T}uring principle and the
  universal quantum computer,} Proceedings of the Royal Society of London.
  Series A, Mathematical and Physical Sciences (1934-1990) {\bf 400}, 97--117
  (1985).
\newline http://dx.doi.org/10.1098/rspa.1985.0070

\bibitem{deutsch:92}
D.~Deutsch and R.~Jozsa, \enquote{Rapid solution of problems by quantum
  computation,} Proceedings of the Royal Society: Mathematical and Physical
  Sciences (1990-1995) {\bf 439}, 553--558 (1992).
\newline http://dx.doi.org/10.1098/rspa.1992.0167

\bibitem{cleve:98}
R.~Cleve, A.~Ekert, C.~Macchiavello, and M.~Mosca, \enquote{Rapid solution of
  problems by quantum computation,} Proceedings of the Royal Society A:
  Mathematical, Physical and Engineering Sciences {\bf 454}, 339--354 (1998).
\newline http://dx.doi.org/10.1098/rspa.1998.0164

\bibitem{Farhi-98}
E.~Farhi, J.~Goldstone, S.~Gutmann, and M.~Sipser, \enquote{Limit on the Speed
  of Quantum Computation in Determining Parity,} Physical Review Letters {\bf
  81}, 5442--5444 (1998).
\newline http://dx.doi.org/10.1103/PhysRevLett.81.5442

\bibitem{Miao-2001}
X.~Miao, \enquote{A polynomial-time solution to the parity problem on an {NMR}
  quantum computer,}  (2001).

\bibitem{orus-04}
R.~Orus, J.~I. Latorre, and M.~A. Martin-Delgado, \enquote{Systematic Analysis
  of Majorization in Quantum Algorithms,} European Physical Journal D {\bf 29},
  119--132 (2004).
\newline http://dx.doi.org/10.1140/epjd/e2004-00009-3

\bibitem{stadelhofer-05}
R.~Stadelhofer, D.~Suterand, and W.~Banzhaf, \enquote{Quantum and classical
  parallelism in parity algorithms for ensemble quantum computers,} Physical
  Review A (Atomic, Molecular, and Optical Physics) {\bf 71}, 032\,345 (2005).
\newline http://dx.doi.org/10.1103/PhysRevA.71.032345

\end{thebibliography}


\end {document}

