%\documentclass[pra,amsfonts,showpacs,preprint,showkeys]{revtex4}
%\documentclass[pra,showpacs,showkeys,amsfonts]{revtex4}
%\usepackage[T1]{fontenc}
%\usepackage{textcomp}
%\usepackage{graphicx}
%\documentstyle[amsfonts]{article}
%\RequirePackage{times}
%\RequirePackage{courier}
%\RequirePackage{mathptm}
%\renewcommand{\baselinestretch}{1.3}

%\begin{document}
%\sloppy

\documentclass{aipproc}
\layoutstyle{8x11single}

\usepackage[T1]{fontenc}
\RequirePackage{times}
\RequirePackage{mathptm}
\usepackage{graphicx}
\begin{document}

\title{Characterization of quantum computable decision problems by state discrimination}

\author{Karl Svozil}{address={Institute of Theoretical Physics, Vienna
    University of Technology, Wiedner Hauptstra\ss e 8-10/136, A-1040
    Vienna, Austria},email={svozil@tuwien.ac.at}}



%\title{Characterization of quantum computable propositions by state discrimination}

%\author{Karl Svozil}
%\email{svozil@tuwien.ac.at}
%\homepage{http://tph.tuwien.ac.at/~svozil}
%\affiliation{Institut f\"ur Theoretische Physik, University of Technology Vienna,
%Wiedner Hauptstra\ss e 8-10/136, A-1040 Vienna, Austria}


\begin{abstract}
One advantage of quantum algorithms over classical computation
is the possibility to spread out, process, analyse and extract information
in multipartite configurations in coherent superpositions of classical states.
This will be discussed
in terms of quantum state identification problems
based on a proper partitioning of mutually orthogonal sets of states.
The question arises whether or not it is possible
to encode equibalanced decision problems
into quantum systems, so that a single invocation
of a filter used for state discrimination suffices to obtain the result.
\end{abstract}

%\pacs{03.67.-a,03.67.Lx}
\keywords{Quantum computation, quantum information}

\maketitle



\section{Outline}

The question as to what might be considered the ``essence'' of quantum computation,
and its possible advantages over classical computation, has been the topic of
numerous considerations, both from a physical
(e.g., Ref.~\cite{ekerj96,pres-97,pres-ln,nielsen-book,galindo-02,mermin-04,eisert-wolf-04})
as well as from a computer science
(e.g., Ref.~\cite{Gruska,benn:97,Ozhigov:1997,bbcmw-01,cleve-99,fortnov-03}) perspective.
Contributing to this ongoing research,
we will present an analysis of novel propositional structures
in quantum mechanics; i.e.,
on the issue of what kind of propositions about
quantum computers exist which do not correspond to any classical statement.
We will consider coherent superpositions of  states and will
make explicit use of the fact that in quantum mechanics information
can be coded in or ``spread among'' entangled multipartite systems in such a way that
information about the single quanta is not useful for (and even makes impossible)
a decryption of the quantum computation.


Alas, it is quite evident that not all decision problems
have a proper encoding
into some quantum mechanical system
such that their resources (computation time, memory usage) is bound by some
criterion such as polynomiality or even finiteness.
Take, as a concrete example, a particular type of halting problem:
Alice presents Bob a black box with input and output interfaces.
Bob's task is to find out whether an arbitrary function of $n$ bits encoded in the black box
will ever output "0."
As this configuration could essentially get as worse as a {\em busy beaver} problem
\cite{rado},
the time it takes for Alice's box to ever output a "0" may grow faster than
any recursive (i.e., computable \cite{rogers1,odi:89}) function of $n$.



Is it possible to
characterize the exact domain of functions
and propositions about them which can be ``reasonably''
(e.g., polynomially) coded into a quantum computation,
given an fairly general set of coding strategies, such as unitary transformations?
In what follows, an attempt is made to characterize the class of quantum computable functions whose
computational complexity grows {\em linearly} with the number of bits
by considering partitioning of states and the associated propositions and observables
\cite{zeil-99,DonSvo01,svozil-2002-statepart-prl,svozil-2003-garda}.
Certain quantum computations such as the Deutsch algorithm
will be expressed as state identification problems,
resulting in the systematic construction of a great variety of computations
corresponding to (incomplete) state identifications
based on superposition and interference.

The notation of Mermin~\cite{mermin-02,mermin-04,mermin-qc} will be adopted.
Consider at first a single qubit in its most general form
$
\vert \psi \rangle
=
\alpha_0
\vert 0 \rangle
+
\alpha_1
\vert 1 \rangle
$
with
$
\vert
\alpha_0
\vert^2
+
\vert
\alpha_1
\vert^2
=1$
as a coherent superposition
between some ``quasi-classical''
states
$
\vert 0 \rangle
$ and
$
\vert 1 \rangle
$
of the computational basis representable by the set of orthogonal vectors
$\{\vert 0 \rangle \equiv (1,0)^T,\vert 1 \rangle \equiv (0,1)^T\}$
(the superscript $T$ indicates transposition).
A 50:50 mixture of the quasi-classical states
is obtained by
$\textsf{\textbf{H}} \vert 0 \rangle
=
(1/\sqrt{2})\left(
\vert 0 \rangle
+
\vert 1 \rangle
\right)
$ or $\textsf{\textbf{H}} \vert 1 \rangle
=
(1/\sqrt{2})\left(
\vert 0 \rangle
-
\vert 1 \rangle
\right)
$
where $\textsf{\textbf{H}}$ is the normalized Hadamard matrix
$\frac{1}{\sqrt{2}}\left(
\begin{array}{rr}
1&1\\
1&-1\\
\end{array}
\right)$.
According to quantum logic
\cite{birkhoff-36,v-neumann-55,svozil-ql},
the interpretation of
$
\textsf{\textbf{H}} \vert 0 \rangle
$
or
$
\textsf{\textbf{H}} \vert 1 \rangle
$
it is the proposition,
{\em ``the quant is in the state associated with the projector}
$(1/2)\left(\textsf{\textbf{1}} \pm \textsf{\textbf{X}}\right)$,''
where $\textsf{\textbf{1}}$ is the unitity and $\textsf{\textbf{X}}
=
\left(
\begin{array}{rr}
0&1\\
1&0\\
\end{array}
\right)$ is the {\em not}-operator.
Classically, neither these states nor the projectors correspond to any
opertionalizable physical entity.
Quantum mechanically, they have,
for instance, an interpretation in terms of electron or neutron spin states
and spin state measurements by a Stern-Gerlach apparatus,
or in terms of photon polarization states and polarization measurements.
Since
$(1/2)(\textsf{\textbf{1}} \pm  \textsf{\textbf{X}})=
(1/2)\left[\textsf{\textbf{1}} + {\bf \sigma}( \theta =\pm \pi /2,\varphi=0)\right]$
with
$
{\bf \sigma}( \theta ,\varphi )=
\left(
\begin{array}{rr} \cos \theta  &e^{-i\varphi} \sin \theta   \\
  e^{i\varphi}\sin \theta  & -\cos \theta
  \end{array}
\right)
$
for the polar angle $\theta$ and the azimuthal angle $\varphi$,
the physical proposition  corresponding to
$\textsf{\textbf{H}}\vert 0\rangle$ and
$\textsf{\textbf{H}}\vert 1\rangle$ is
{\em ``along the polar angle $\pm \pi/2$ and azimuthal angle $\varphi=0$,
the particle is in a linear polarization (or positive spin) state.''}

\section{Identifying states among contexts}

A {\em context} can formally be defined \cite{svozil-2004-vax}
as a single (nondegenerate) ``maximal'' self-adjoint operator
$\textsf{\textbf{C}}$.
It has a spectral
decomposition into some complete set of orthogonal projectors $\textsf{\textbf{E}}_i$
which correspond to propositions in
the von Neumann-Birkhoff type sense \cite{birkhoff-36,v-neumann-49}.
That is, $\textsf{\textbf{C}}=\sum_{i=1}^d e_i \textsf{\textbf{E}}_i$
with mutually different real $e_i$ and some orthgonal projectors
$\{\textsf{\textbf{E}}_i{} \mid i=1,\ldots d\}$ of
$d$-dimensional Hilbert space.
In $d$ dimensions, contexts can be viewed as $d$-pods or orthogonal bases
spanned by the vectors associated with the $d$ mutually orthogonal projectors
$\textsf{\textbf{E}}_1,
\textsf{\textbf{E}}_2, \cdots, \textsf{\textbf{E}}_d$.

The general problem to (uniquely) identify orthogonal pure states
among contexts resulting from $k$ particles in $n=2$ or more dimensions per particle
has been solved in Ref.~\cite{DonSvo01,svozil-2002-statepart-prl,svozil-2003-garda}
{\em via} a system of $k$ co-measurable  filters $\textsf{\textbf{F}}_i$, $i=1,\ldots, k$
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 an
equi-$n$-partition of the $d$-dimensional state space into
$n$ slices (i.e., partition elements) containing $d/n=d^{1-1/k}=n^{k-1}$ states per slice.
(Note that $d=n^k$.)
A filter is said to separate two eigenstates if the eigenvalues are different.
\item[(F2)]
From each one of the $k$ partitions of (F1), take an arbitrary element.
The intersection of the elements of all different partitions
results in a {\it single} one of the $d=n^k$ 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}

For $n=2$, an explicit construction of all the systems of filters and their associated propositions
can be given in terms of projectors and their orthogonal projectors;
every one of them projecting onto a $d/2$-dimensional subspace,
such that the serial composition of any complete set of (orthogonal) projectors (one per filter)
yields the finest resolution; i.e., some of the $d$ one-dimensional projectors $\textsf{\textbf{E}}_i$
spanning the context $\textsf{\textbf{C}}$.

The system of filters resolving $\textsf{\textbf{C}}$
is not unique;
all such systems of filters can be obtained by permutating
the columns of the matrix whose rows are
the diagonal elements of all the filters in diagonalized form.
Different contexts
$\textsf{\textbf{C}}'$
are resolved by different systems of filters which are obtained by transforming
$\textsf{\textbf{F}}_i$, $i=1,\ldots, k$ through
the same basis transformation which transforms
$\textsf{\textbf{C}}$
into
$\textsf{\textbf{C}}'$.
Several examples and explicit constructions will be given below.

Take, for instance, three two-state quanta, i.e.,
the case $k=3$, $n=2$, and thus $d=2^3$.
The three projectors
$$
\begin{array}{ccc}
\textsf{\textbf{F}}_1&=&\textrm{diag}(1,1,1,1,0,0,0,0),\\
\textsf{\textbf{F}}_2&=&\textrm{diag}(1,1,0,0,1,1,0,0),\\
\textsf{\textbf{F}}_3&=&\textrm{diag}(1,0,1,0,1,0,1,0),\\
\end{array}
$$
 together with their orthogonal projectors
$$
\begin{array}{ccc}
\textsf{\textbf{F}}_1'&=&\textrm{diag}(0,0,0,0,1,1,1,1), \\
\textsf{\textbf{F}}_2'&=&\textrm{diag}(0,0,1,1,0,0,1,1), \\
\textsf{\textbf{F}}_3'&=&\textrm{diag}(0,1,0,1,0,1,0,1),   \\
\end{array}
$$
form the system of three filters
$
\{
\{ \textsf{\textbf{F}}_1,\textsf{\textbf{F}}_1' \},
\{ \textsf{\textbf{F}}_2,\textsf{\textbf{F}}_2' \},
\{ \textsf{\textbf{F}}_3,\textsf{\textbf{F}}_3' \}
\}
$
which have the desired properties (F1)--(F3).
Equivalent filters are obtained by permuting the columns of the diagonal rows of
\begin{equation}
\left(
\begin{array}{cccccccc}
1&1&1&1&0&0&0&0\\
0&0&0&0&1&1&1&1\\
\hline
1&1&0&0&1&1&0&0\\
0&0&1&1&0&0&1&1\\
\hline
1&0&1&0&1&0&1&0\\
0&1&0&1&0&1&0&1\\
\end{array}
\right).
\label{2005-ko-e78}
\end{equation}
Different systems of filters are obtained by permutating the columns
of the matrix in Eq.~\ref{2005-ko-e78}; e.g.,
\begin{equation}
\left(
\begin{array}{cccccccc}
1&1&1&0&0&0&0&1\\
0&0&0&1&1&1&1&0\\
\hline
1&0&0&1&1&0&0&1\\
0&1&1&0&0&1&1&0\\
\hline
0&1&0&1&0&1&0&1\\
1&0&1&0&1&0&1&0\\
\end{array}
\right),
\qquad
\left(
\begin{array}{cccccccc}
1&1&0&0&0&0&1&1\\
0&0&1&1&1&1&0&0\\
\hline
0&0&1&1&0&0&1&1\\
1&1&0&0&1&1&0&0\\
\hline
1&0&1&0&1&0&1&0\\
0&1&0&1&0&1&0&1\\
\end{array}
\right),
\qquad
\ldots
\label{2005-ko-e781}
\end{equation}
In the case of $k=2$, any permutation yields the original system of filters.

Different contexts are reached by transforming every single filter operator
through the same unitary transformation.
Note that the row permutations and unitary transformations are exhaustive;
i.e., there are no other methods available.
For $n>2$, the filter operators cannot correspond to projectors, because
they are not binary but $n$-ary.
In this case,  for instance, $n^k$ different
prime numbers can be used as eigenvalues.
A more detailed treatment of this case can be found
in Refs.~\cite{svozil-2002-statepart-prl,svozil-2003-garda}.

\section{Deutsch's problem and related algorithms}

In what follows, Deutsch's decision problem to find out whether or not an unknown
function $f$ that takes a single (classical) bit into a single (classical) bit
is constant or not, which is equal to finding the parity of $f:\{0,1\}\rightarrow \{0,1\}$, will
be interpreted as a state identification problem, which is solved by the methods
discussed in the previous section.
There are four possible bivalent functions of one bit:
the constant functions $f_0$ and $f_3$ take
any bit value and map it into either $0$ or $1$, respectively.
The two remaining functions $f_1$ and $f_2$
correspond to the identity $\textsf{\textbf{1}}$
and to the {\em not} operator $\textsf{\textbf{X}}$, and are thus not constant
(cf.~Table~\ref{2005-ko-t11dp}).
\begin{table}
\centerline{
\begin{tabular}{cccccccccccccc}
\hline
$f$& $ 0$ &$1$\\
\hline
$f_0$ &$0$ &$0$\\
$f_1$ &$0$ &$1$\\
$f_2$ &$1$ &$0$\\
$f_{3}$ &$1$ & $1$\\
\hline
\end{tabular}
}
\caption{The binary functions of one bit considered in Deutsch's problem. \label{2005-ko-t11dp}
}
\end{table}
Hence, with respect to constancy, the set of all functions
$\{f_0,f_1,f_2,f_3\}$
is equipartitioned into
\begin{equation}
F_D=\{\{f_0,f_3\},\{f_1,f_2\}\}.
\label{2005-ko-03}
\end{equation}
The first and second elements   $\{f_0,f_3\}$ and $\{f_1,f_2\}$ of this partition
can be interpreted as the proposition,
{\em ``the function is (not) constant.''}

When coding the Deutsch problem and the computation of $f$
into a state identification problem,
one task is to map the binary partition $F_D$ in Eq.~(\ref{2005-ko-03})
into a quantum state filter
$\textsf{\textbf{F}}$ with equivalent separation properties.
Presently, there does not exist any algorithmic way (only heuristic ones)
to obtain such a quantum encoding,
nore is any one likely to exist
(cf. the parity problem discussed below).

First note that, as the functions $f_0$ and $f_3$ are two-to-one (i.e., irreversible),
the input bit needs to be augmented by a second bit to maintain
reversibility, which is a necessary condition for the  unitarity of the state evolution.
Usually, this is accomplished by considering
$\textsf{\textbf{U}}_f(\vert x \rangle \vert y \rangle )=\vert x \rangle \vert y \oplus f(x)\rangle$, where $\oplus$ is the modulo-2 addition
(without carrying).


The encoding Ansatz enumerated in Table~\ref{2005-ko-t1} represents the evolution
of the single terms contributing to
$\textsf{\textbf{U}}_f(\textsf{\textbf{H}}\otimes\textsf{\textbf{H}})
(\textsf{\textbf{X}}\otimes\textsf{\textbf{X}})
(\vert 0\rangle \vert 0\rangle )$,
resulting in the two different states
\begin{equation}
\vert \psi_1 \rangle = \pm \frac{1}{2} (
\vert 0\rangle   -
\vert 1\rangle  )(
\vert 0\rangle   -
\vert 1\rangle  )\equiv \pm \frac{1}{2} ((1,-1)\otimes (1,-1))^T=\pm \frac{1}{2} (1,-1,-1,1)^T
\label{2005-ko-e111}
\end{equation}
for $f_0$ as well as $f_3$, and
\begin{equation}
\vert \psi_2 \rangle = \pm \frac{1}{2} (
\vert 0\rangle   +
\vert 1\rangle  )(
\vert 0\rangle   -
\vert 1\rangle  )\equiv \pm \frac{1}{2} ((1,1)\otimes (1,-1))^T=\pm \frac{1}{2} (1,-1,1,-1)^T
\label{2005-ko-e112}
\end{equation}
for $f_1$ as well as $f_2$.
\begin{table}
\centerline{
\begin{tabular}{cccccccccccccc}
\hline
 & $\frac{1}{2}\big[\vert 0\rangle \vert 0 \oplus f(0)\rangle $ &$-$& $\vert 0\rangle \vert 1 \oplus f(0)\rangle $ &$-$& $\vert 1\rangle \vert 0 \oplus f(1)\rangle $ &+& $\vert 1\rangle \vert 1 \oplus f(1)\rangle \big]$\\
\hline
$f_0$:  & $\frac{1}{2}\big(\vert 0\rangle \vert 0\rangle $ &$-$& $\vert 0\rangle \vert 1\rangle $ &$-$& $\vert 1\rangle \vert 0\rangle $ &+& $\vert 1\rangle \vert 1\rangle \big)$\\
$f_1$:  & $\frac{1}{2}\big(\vert 0\rangle \vert 0\rangle $ &$-$& $\vert 0\rangle \vert 1\rangle $ &$-$& $\vert 1\rangle \vert 1\rangle $ &+& $\vert 1\rangle \vert 0\rangle \big)$\\
$f_2$:  & $\frac{1}{2}\big(\vert 0\rangle \vert 1\rangle $ &$-$& $\vert 0\rangle \vert 0\rangle $ &$-$& $\vert 1\rangle \vert 0\rangle $ &+& $\vert 1\rangle \vert 1\rangle \big)$\\
$f_3$:  & $\frac{1}{2}\big(\vert 0\rangle \vert 1\rangle $ &$-$& $\vert 0\rangle \vert 0\rangle $ &$-$& $\vert 1\rangle \vert 1\rangle $ &+& $\vert 1\rangle \vert 0\rangle \big)$\\
\hline
\end{tabular}
}
\caption{State evolution of $\textsf{\textbf{U}}_f(\textsf{\textbf{H}}\otimes\textsf{\textbf{H}})
(\textsf{\textbf{X}}\otimes\textsf{\textbf{X}})
(\vert 0\rangle \vert 0\rangle )$
for the four functions $f_0,f_1,f_2,f_3$. \label{2005-ko-t1}
}
\end{table}
Together with
$\vert \psi_3 \rangle = (\textsf{\textbf{H}}\otimes\textsf{\textbf{H}})(\vert 0\rangle \vert 0\rangle )\equiv
(1/2)(1,1,1,1)^T$
and
$\vert \psi_4 \rangle = (\textsf{\textbf{H}}\otimes\textsf{\textbf{H}})(\textsf{\textbf{X}}\otimes\textsf{\textbf{1}})(\vert 0\rangle \vert 0\rangle )\equiv
(1/2)(1,1,-1,-1)^T$,
the four states in $\textbf{B}^D=\{\psi_1, \psi_2 ,\psi_3 ,\psi_4 \}$ form an orthonormal basis.

Application of two Hadamard-transformations for each one of the two bits finally yields a
representation in the sandard computational basis; i.e.,
\begin{equation}
(\textsf{\textbf{H}}\otimes\textsf{\textbf{H}})
\textsf{\textbf{U}}_f
(\textsf{\textbf{H}}\otimes\textsf{\textbf{H}})
(\textsf{\textbf{X}}\otimes\textsf{\textbf{X}})
(\vert 0\rangle \vert 0\rangle )
=
\left\{
\begin{array}{ccl}
\vert 1\rangle \vert 1\rangle \equiv (0,0,0,1)^T  &\textrm{ for } f(0)=f(1),\\
\vert 0\rangle \vert 1\rangle \equiv (0,1,0,0)^T   &\textrm{ for } f(0)\neq f(1).\\
\end{array}
\right.
\label{2005-ko-e113}
\end{equation}




We are now in the position to formulate the state identification problem corresponding to the Deutsch
algorithm.
This is achieved
by considering the projector
$\textsf{\textbf{F}}_1 =\textrm{diag}(1,1,0,0)$,
which, together with its orthogonal projector
$\textsf{\textbf{F}}_1' =\textrm{diag}(0,0,1,1)$,
constitutes a filter
corresponding to the binary partition $F_D$ in Eq.~(\ref{2005-ko-03}).
Note that a second filter $\textsf{\textbf{F}}_2$, based on the projections
$\textsf{\textbf{F}}_2 =\textrm{diag}(1,0,1,0)$
and
$\textsf{\textbf{F}}_2' =\textrm{diag}(0,1,0,1)$, completes the system of filters.
It is unable to separate
$\vert 1 1\rangle$
from
$\vert 0 1 \rangle$, but separates
$\vert 0 0 \rangle$
and
$\vert 1 0 \rangle$
from
$\vert 0 1\rangle$
and
$\vert 1 1\rangle$.


Alternatively, we may consider the state identification problem without the final Hadamard transformations
as, {\em ``find the observables which separate $\psi_1$ from $\psi_2$.''}
The complete state identification problem should also contain the observables separating $\psi_3$ from $\psi_4$,
but in Deutsch's problem one is not primarily interested
in uniquely identifying the function itself; rather in its (non)constancy.
Hence, it is not necessary to employ the entire system of two filters, but rather
a single filter constructed to separate $f_0$, $f_3$ from  $f_1$, $f_2$.
This is achieved
by transforming the two operators
$\textsf{\textbf{F}}_1 =\textrm{diag}(1,1,0,0)$
and
$\textsf{\textbf{F}}_2 =\textrm{diag}(1,0,1,0)$
associated with a binary search type state separation in the  basis
$\textbf{B}=\{
(1,0,0,0)^T,
(0,1,0,0)^T,
(0,0,1,0)^T,
(0,0,0,1)^T\}$
through
$\textsf{\textbf{U}}\textsf{\textbf{F}}_1\textsf{\textbf{U}}^{-1} =\textsf{\textbf{F}}^D_1$ and
$\textsf{\textbf{U}}\textsf{\textbf{F}}_2\textsf{\textbf{U}}^{-1} =\textsf{\textbf{F}}^D_2$,
where
\begin{equation}
\textsf{\textbf{U}}=\frac{1}{2}
\left(
\begin{array}{rrrr}
 1&  1& 1&  1\\
 1& -1& 1& -1\\
-1&  1& 1& -1\\
-1& -1& 1&  1
\end{array}
\right)
\end{equation}
is the unitary transformation which corresponds to a basis change
$\textbf{B} \rightarrow \textsf{\textbf{U}}\textbf{B}=\textbf{B}^D$.
It is straightforward to check that, by the eigenvalue spectrum,
$\textsf{\textbf{F}}^D_1$ separates between
$\psi_1$ and $\psi_3$ from
$\psi_2$ and $\psi_4$
(and at the same time,
$\textsf{\textbf{F}}^D_2$ separates between
$\psi_1$ and $\psi_2$ from
$\psi_3$ and $\psi_4$).
Hence, $\textsf{\textbf{F}}^D_1$ generates a partition
$\{\{\psi_1,\psi_3\},\{\psi_2,\psi_4\}\}$ of the set
$\{\psi_1,\psi_3,\psi_2,\psi_4\}$
of orthogonal states.
($\textsf{\textbf{F}}^D_2$ generates the partition
$\{\{\psi_1,\psi_2\},\{\psi_3,\psi_4\}\}$.)
The states $\psi_i$, however, do not directly correspond to the functions $f_j$ in the
Deutsch partition in Eq.~(\ref{2005-ko-03}); they rather represent
joint properties of these functions, such as constancy.

Another encoding strategy of the Deutsch problem
can be based upon a immediate identification of
$\{f_0,f_1,f_2,f_3\}$
with the four states of the computational basis $\textbf{B}$.
The nontrivial part in this case is the mapping of the functions $f_i$ on to $\textbf{B}$;
e.g., by constructing unitary transformations depending
on $f_i$ and acting on $\vert 0 0 \rangle$, such
as for instance $\textsf{\textbf{V}}_f\vert 0 0 \rangle=\vert f(0) f(1) \rangle$.
Once this has been achieved,
in order to express constancy, the filter would then have to
separate the orthogonal (Bell) states
$\varphi_{1,4}\equiv (1,0,0,\pm 1)^T$
from
$\varphi_{2,3}\equiv  (0,1,\pm 1,0)^T$;
a rather straightforward task.


Still another encoding strategy would be to invoke the phase oracle
$
\textsf{\textbf{U}}_f \left( \vert x\rangle  \otimes \textsf{\textbf{H}}
\vert 1\rangle \right)
=
(-1)^{f(x)}    \vert x\rangle   \otimes \textsf{\textbf{H}}
\vert 1\rangle $. The resulting states are enumerated in Table~\ref{2005-ko-t11}.
\begin{table}
\centerline{
\begin{tabular}{cccccccccccccc}
\hline
& \multicolumn{4}{c }{$(-1)^{f(x)}$}\\
$f$& $\vert 0\rangle$ &$\vert 1\rangle $\\
\hline
$f_0$ &$+$ &$+$\\
$f_1$ &$+$ &$-$\\
$f_2$ & $-$&$+$\\
$f_3$ &$-$ & $-$\\
\hline
\end{tabular}
}
\caption{The phase factors of $(-1)^{f(x)}\vert xy\rangle$. \label{2005-ko-t11}
}
\end{table}
The phases result in the orthogonality of the two linear
subspaces corresponding to $f_0$ and $f_3$, with respect to $f_1$ and $f_2$.

In a very similar manner, one could discuss the Bernstein-Vazirani algorithm,
 as well as
the Deutsch-Josza and  Simon's decision problems
(in the latter cases with the proviso discussed later,
since the algorithm is not deterministic).
Note that this method exhausts all possible decision problems based on equipartitioning
of state spaces, but does not give a direct hint
about the type of classical algorithmic problem which are solvable that way.

\section{Parity checking}

Deutsch's problem is just the simplest in a particular class of problems:
check the parity of an unknown binary function $f:\{0,1\}^k \rightarrow \{0,1\}$ of $k$ bits.
There are $2^{2^k}$ such functions.
The parity of a function $f$ of $k$ bits depends on whether
the number of functional values of $f(x_1,\ldots , x_k)=1$
on all $x_1,\ldots , x_k\in \{0,1\}$ is even or odd,
denoted by  ``$+$'' and ``$-$,'' respectively.

Consider, for the sake of an example,
two bits $x,y$ and an unknown function $f(x,y)$
of all the $2^{2^2}=16$ binary functions partly listed in Tab.~\ref{2005-ko-t2}.
\begin{table}
\centerline{
\begin{tabular}{cccccccccccccc}
\hline
 $\pm$&$f$&  00& 01& 10 &11\\
\hline
$+$&$f_0$ &0 &0& 0& 0\\
$-$&$f_1$ &0 &0& 0& 1\\
$-$&$f_2$ &0 &0& 1& 0\\
\multicolumn{6}{c}{$\cdots$}\\
$+$&$f_{15}$ &1 & 1& 1&1\\
\hline
\end{tabular}
}
\caption{Listing of the 16 binary functions of two variables $x,y$ with their parity bits
``$\pm$''. \label{2005-ko-t2}
}
\end{table}
The set of 16 functions can be equipartitioned
into two groups of 8 functions,  according to positive and negative parity; i.e.,
\begin{equation}
F_P=
\left\{
\left\{
     f_{  0} ,
     f_{  5} ,
     f_{  6} ,
     f_{  7} ,
     f_{  8} ,
     f_{  9} ,
     f_{ 10} ,
     f_{ 15}
\right\},
\left\{ f_{  1} ,
     f_{  2} ,
     f_{  3} ,
     f_{  4} ,
     f_{ 11} ,
     f_{ 12} ,
     f_{ 13} ,
     f_{ 14}
\right\}
\right\}
.
\label{2005-ko-e55-0}
\end{equation}
One might be tempted to speculate
that the corresponding proposition corresponds to some realizable
quantum filter which separates the two parity classes by some quantum implementation
$
\textsf{\textbf{U}}_f
$ in a single run.
Motivation for this comes from the direct and ``local,'' or ``isolated'' evaluation
of the functional values;
without any recursion, iteration, or additional functional and contextual relation
between the values.
Despite these indications, the parity of a function
has been proven quantum computationally hard
\cite{Farhi-98,bbcmw-01,Miao-2001,orus-04,stadelhofer-05}:
It is only possible to go from $2^k$ classical queries down to $2^k/2$
quantum queries, thereby gaining a factor of 2.


Classically, parity checking grows exponentially $2^k$ with the number $k$ of bits of the
functional arguments, as there is no other was than to compute the functional
values on the entire set of $2^k$ arguments.
Quantum mechanically,
one may interpret this problem as a particular instance
of a generalized Grover algorithm with an unknown number of special states,
which can be solved by applying the quantum Fourier transform.


By making use of the phase oracle
$
\textsf{\textbf{U}}_f \left( \vert x\rangle  \otimes \textsf{\textbf{H}}
\vert 1\rangle \right)
=
(-1)^{f(x)}    \vert x\rangle   \otimes \textsf{\textbf{H}}
\vert 1\rangle $,
one obtains, after a second application of a Hadamard transformation,
\begin{equation}
\left(
\textsf{\textbf{1}}
\otimes
\textsf{\textbf{1}}
\otimes
\textsf{\textbf{H}}
\right)
\textsf{\textbf{U}}_f
\left(
\textsf{\textbf{1}}
\otimes
\textsf{\textbf{1}}
\otimes
\textsf{\textbf{H}}
\right)
\vert x,y \rangle \vert 1\rangle
=
(-1)^{f(x,y)}\vert x,y \rangle \vert 1\rangle
.
\label{2005-ko-e55}
\end{equation}
Table \ref{2005-ko-t3} lists the results of this transformation.
\begin{table}
\centerline{
\begin{tabular}{ccccccccccccccc}
\hline
&& &\multicolumn{4}{c}{$(-1)^{f(x)} $}
\\
$\pm$&$f$& &
$\vert 00 \rangle$&
$\vert 01 \rangle$&
$\vert 10 \rangle$&
$\vert 11 \rangle$
\\
\hline
$+$&$f_{  0}      $ &        &$+$ &$+$ &$+$ &$+$                               \\
$-$&$f_{  1}      $ &        &$+$ &$+$ &$+$ &$-$                               \\
$-$&$f_{  2}      $ &        &$+$ &$+$ &$-$ &$+$                               \\
$-$&$f_{  3}      $ &        &$+$ &$-$ &$+$ &$+$                               \\
$-$&$f_{  4}      $ &        &$-$ &$+$ &$+$ &$+$                               \\
$+$&$f_{  5}      $ &        &$+$ &$+$ &$-$ &$-$                               \\
$+$&$f_{  6}      $ &        &$+$ &$-$ &$+$ &$-$                               \\
$+$&$f_{  7}      $ &        &$-$ &$+$ &$+$ &$-$                               \\
$+$&$f_{  8}      $ &        &$+$ &$-$ &$-$ &$+$                               \\
$+$&$f_{  9}      $ &        &$-$ &$+$ &$-$ &$+$                               \\
$+$&$f_{ 10}      $ &        &$-$ &$-$ &$+$ &$+$                               \\
$-$&$f_{ 11}      $ &        &$+$ &$-$ &$-$ &$-$                               \\
$-$&$f_{ 12}      $ &        &$-$ &$+$ &$-$ &$-$                               \\
$-$&$f_{ 13}      $ &        &$-$ &$-$ &$+$ &$-$                               \\
$-$&$f_{ 14}      $ &        &$-$ &$-$ &$-$ &$+$                               \\
$+$&$f_{ 15}      $ &        &$-$ &$-$ &$-$ &$-$                               \\
\hline
\end{tabular}
}
\caption{The phases from Eq.~(\ref{2005-ko-e55}).
\label{2005-ko-t3} }
\end{table}
As long as
the function is ``unbalanced,'' such that the
number of values of $f(x_1, \ldots ,x_k)=1$ is small compared to $2^k$,
a quadratic speedup is achievable.
However, this condition does in general not apply.

\section{Generalized Deutsch algorithms}


In what follows  we shall present a type of quantum algorithm
which is directly motivated by the state identification problem.
Consider the class of binary functions of two variables which are  the sums of
two (or more) binary functions of one variable; e.g.,
\begin{equation}
f_{ij}(x,y)=f_i(x)+f_j(y); \quad 0\le i,j\le 3.
\label{2005-ko-e31}
\end{equation}
The binary functions $f_i,f_j$ of one bit are the same as in Deutsch's problem
listed in Table~\ref{2005-ko-t11dp}.
The corresponding unitary transformations given by
$
\textsf{\textbf{U}}_{f_{ij}}=
\textsf{\textbf{U}}_{f_i}
\otimes
\textsf{\textbf{U}}_{f_j}$.
In this case,
the phase oracle  yields phases which are listed in Table~\ref{2005-ko-t31}.
\begin{table}
\centerline{
\begin{tabular}{ccccccccccccccc}
\hline
& &\multicolumn{4}{c}{$(-1)^{f_i(x)+f_j(y)} $}
\\
$f$& &
$\vert 00 \rangle$&
$\vert 01 \rangle$&
$\vert 10 \rangle$&
$\vert 11 \rangle$
\\
\hline
    $f_{  00}      $ &   &$+$&$+$&$+$&$+$                                     \\
    $f_{  01}      $ &   &$+$&$-$&$+$&$-$                                     \\
    $f_{  02}      $ &   &$-$&$+$&$-$&$+$                                     \\
    $f_{  03}      $ &   &$-$&$-$&$-$&$-$                                     \\
    $f_{  10}      $ &   &$+$&$+$&$-$&$-$                                     \\
    $f_{  11}      $ &   &$+$&$-$&$-$&$+$                                     \\
    $f_{  12}      $ &   &$-$&$+$&$+$&$-$                                     \\
    $f_{  13}      $ &   &$-$&$-$&$+$&$+$                                     \\
    $f_{  20}      $ &   &$-$&$-$&$+$&$+$                                     \\
    $f_{  21}      $ &   &$-$&$+$&$+$&$-$                                     \\
    $f_{  22}      $ &   &$+$&$-$&$-$&$+$                                     \\
    $f_{  23}      $ &   &$+$&$+$&$-$&$-$                                     \\
    $f_{  30}      $ &   &$-$&$-$&$-$&$-$                                     \\
    $f_{  31}      $ &   &$-$&$+$&$-$&$+$                                     \\
    $f_{  32}      $ &   &$+$&$-$&$+$&$-$                                     \\
    $f_{  33}      $ &   &$+$&$+$&$+$&$+$                                     \\
\hline
\end{tabular}
}
\caption{The phases from the phase oracle applied to Eq.~(\ref{2005-ko-e31}).
\label{2005-ko-t31} }
\end{table}

The four orthogonal vectors resulting from the phase enumeration in Table~\ref{2005-ko-t31}
form a basis
$
\textsf{\textbf{B}}'=\{
\varphi_1,
\varphi_2,
\varphi_3,
\varphi_4\}$, with
\begin{equation}
\begin{array}{lll}
\varphi_1&=&  (1,1,1,1)^T,\\
\varphi_2&=&  (1,1,-1,-1)^T,\\
\varphi_3&=&   (1,-1,1,-1)^T,\\
\varphi_4&=&   (1,-1,-1,1)^T.\\
\end{array}.
\label{2005-ko-e55-023}
\end{equation}

Consider the decision problems corresponding to the following propositions:
\begin{enumerate}
\item[(D1)]
{\em The function $f_{ij}(x,y)$  is  constant in the first argument.}


\item[(D2)]
{\em The function $f_{ij}(x,y)$  is  constant in the second argument.}


\item[(D3)]
{\em The function $f_{ij}(x,y)$  is  constant in the first argument and not constant in the second argument,
                           or it is  constant in the second argument and not constant in the first argument.}


\item[(D4)]
{\em The function $f_{ij}(x,y)$  is  constant in the first argument and constant in the second argument,
                           or it is  not constant in the second argument and not constant in the first argument.}
\end{enumerate}

The partitions corresponding to these decision problems are
\begin{eqnarray}
F_1&=&
\left\{
\left\{
     f_{ 00} ,
     f_{ 01} ,
     f_{ 02} ,
     f_{ 03} ,
     f_{ 30} ,
     f_{ 31} ,
     f_{ 32} ,
     f_{ 33}
\right\},
\left\{
    f_{  10} ,
     f_{ 11} ,
     f_{ 12} ,
     f_{ 13} ,
     f_{ 20} ,
     f_{ 21} ,
     f_{ 32} ,
     f_{ 33}
\right\}
\right\}
,
\label{2005-ko-e55-01a}   \\
F_2&=&
\left\{
\left\{
     f_{ 00} ,
     f_{ 10} ,
     f_{ 20} ,
     f_{ 30} ,
     f_{ 03} ,
     f_{ 13} ,
     f_{ 23} ,
     f_{ 33}
\right\},
\left\{
     f_{ 01} ,
     f_{ 11} ,
     f_{ 21} ,
     f_{ 31} ,
     f_{ 02} ,
     f_{ 12} ,
     f_{ 22} ,
     f_{ 32}
\right\}
\right\}
,
\label{2005-ko-e55-01b}   \\
F_3&=&
\left\{
\left\{
     f_{ 01} ,
     f_{ 02} ,
     f_{ 10} ,
     f_{ 13} ,
     f_{ 20} ,
     f_{ 23} ,
     f_{ 31} ,
     f_{ 32}
\right\},
\left\{
     f_{ 00} ,
     f_{ 03} ,
     f_{ 11} ,
     f_{ 12} ,
     f_{ 21} ,
     f_{ 22} ,
     f_{ 30} ,
     f_{ 33}
\right\}
\right\}
,
\label{2005-ko-e55-01c}   \\
F_4&=&
\left\{
\left\{
     f_{ 00} ,
     f_{ 03} ,
     f_{ 11} ,
     f_{ 12} ,
     f_{ 21} ,
     f_{ 22} ,
     f_{ 30} ,
     f_{ 33}
\right\},
\left\{
     f_{ 01} ,
     f_{ 02} ,
     f_{ 10} ,
     f_{ 13} ,
     f_{ 20} ,
     f_{ 23} ,
     f_{ 31} ,
     f_{ 32}
\right\}
\right\}
.
\label{2005-ko-e55-01d}
\end{eqnarray}

Thus any filter which resolves the associated decision problem at once has to
separate
(1)
$\varphi_1$ and $\varphi_3$ from $\varphi_2$ and $\varphi_4$,
(2)
$\varphi_1$ and $\varphi_2$ from $\varphi_3$ and $\varphi_4$,
(3)
$\varphi_2$ and $\varphi_3$ from $\varphi_1$ and $\varphi_4$,
(4)
$\varphi_1$ and $\varphi_4$ from $\varphi_2$ and $\varphi_3$, respectively.



Again, the strategy is to find the unitary transform
\begin{equation}
\textsf{\textbf{U}}'=\frac{1}{2}
\left(
\begin{array}{rrrr}
 1&  1& 1&  1\\
 1& 1& -1& -1\\
1&  -1& 1& -1\\
1& -1& -1&  1
\end{array}
\right) ,
\end{equation}
which yields a basis change
$\textbf{B} \rightarrow \textsf{\textbf{U}}'\textbf{B}=\textbf{B}'$.
Then, measurement of
$\textsf{\textbf{F}}' =
(\textsf{\textbf{U}}')^{-1}\textsf{\textbf{F}}_i\textsf{\textbf{U}}'$
with
\begin{eqnarray}
\textsf{\textbf{F}}_1&=&{\rm diag}(1,0,1,0), \\
\textsf{\textbf{F}}_2&=&{\rm diag}(1,1,0,0),   \\
\textsf{\textbf{F}}_3&=&{\rm diag}(0,1,1,0),   \\
\textsf{\textbf{F}}_4&=&{\rm diag}(1,0,0,1),
\end{eqnarray}
solves the decision problems (D1)--(D4), respectively.
This method can be generalized to more than two arguments in a straightforward manner.




\section{Information spread among quanta}

So why can the parity of a function not be efficiently coded quantum mechanically?
In Ref.~\cite{bbcmw-01}, Beals {\it et al.}
argue that exponential quantum speed-up can be obtained for
partial functions (e.g., problems involving a promise on input~\footnote{
A partial function is a function which is not defined for some of its domain.}),
whereas such speedups cannot be obtained
for any total function.
Another ansatz for an explanation,
put forward by Orus {\it et al.}
in Ref.~\cite{orus-04}, is majorization:
The
probability distribution associated with the quantum state is step-by-step majorized until
it is maximally ordered.
Then a measurement provides the solution with high probability.

We propose here that the lack of efficient quantum algorithms
is due to the nonexistence of
mappings of functions $f$ and decision problems into suitable unitary
transformations
$
\textsf{\textbf{U}}_f
$
which could be used for
a system of states and of filter(s) resolving those states corresponding to that particular
algorithmic problem and no other one.
To give an example, in order for a quantum computation to
resolve the equipartition in Eq.~(\ref{2005-ko-e55-0})
by some equivalent quantum state filter,
any such filter must be based upon an encoding of the functional parity
into some orthogonal set of states.
Thereby, in order for the encoding to be efficient, it should not require the
separate functional evaluation of all classical cases.
On the contrary, the mapping $f \mapsto U_f$, as well as
states and filters need to be conceptualized
in a way which leaves the single functional values {\em undefined},
but concentrates on the structural property of parity alone:
the even or odd number of occurrence of certain functional values (0 or 1)
on the entirety of outputs.
If the filters could resolve singular functional values
in the standard computational basis,
they would essentially model classical information.
Any such state preparation or measurement
would make impossible the encoding of information
``spread among'' multipartite states as mentioned above,
which seems to be one of the advantages of quantum computing.
In this paradigm, entanglement and the suitable superposition of multipartite states
become related concepts, as no multipartite state which can be factored
could be used to ``spread'' information among the quanta (or a group of quanta) corresponding to these factors.

In general, while all classical computable recursive functions
$f$ and decision problems can be coded quantum mechanically, there is no guarantee
that a problem can be coded efficiently by mapping it into the quantum domain.
By an efficient coding of a (binary or $n$-ary) decision
problem  we mean that some quantum circuit
$\textsf{\textbf{U}}_f$ exists
which outputs a state which is uniquely identifiable by a single filter
(or at least by a polynomial number of filters),
the outcome of which corresponds to the solution of this problem.
%Unfortunately, no constructive method can be derived from the above considerations which would indicate if such an encoding $f \mapsto U_f$ of a function $f$
%into an effective state identification procedure exists, and how to construct it.



While the parity of a binary function
of more than one observable has already been mentioned
as an example of quantum computationally ``hard'' problems,
it appears not totally unreasonable to speculate  that functional recursions
and iterations
represent an additional burden on efficiency.
Recursions may require
a space overhead to keep track of the computational path,
in particular if the recursion depth cannot be coded efficiently.
From this point of view,
quantum implementations of the Ackermann or the Busy Beaver functions,
to give just two examples,
may even be less efficient than classical implementations,
where an effective waste management can get rid of many bits;
in particular in the presence of a computable radius of convergence.


\section{State identification and dense coding}
Let us also briefly mention another issue related to state identification
if there is a mismatch between the context in which
information is prepared and a different context, in which this information
is retrieved.
Based on such a context mismatch,
a ``dense coding'' scheme has been proposed \cite{581773}
to probabilistically encode ``more'' than one
classical bits into one quantum bit (despite Holevo's bound).
%(The dense coding scheme of Bennett and Wiesner \cite{BeWi-dense_coding} using pairs of entangled particles is different.)
This method is based on the fact that the qubit states
$\vert 0\rangle$
and
$\vert 1\rangle$
span the computational basis
$\{ (1,0)^T,(0,1)^T\}$, as already mentioned before,
and that any coding of a qubit state which is neither orthogonal nor
collinear, such as $(\cos (\pi /8),\sin (\pi /8))^T$,
results in a probability of detecting it in the
original states governed by its projection onto them.
The argument is about efficiency of state identification in the classical
and quantum case for ``misaligned'' systems of states.

Alas, when speaking about coding and representation efficiency of statistical raw data,
it is mandatory to take an issue into account which changes the classical
framework rather dramatically.
As has been pointed out repeatedly by Summhammer
\cite{sum-1,summi:93},  the ``true'' probability of the
occurrence of a (classical) bit is unknown.
Frequency counts are just approximations to this value.
As it turns out, if a {\em finite} amount of information is used
to characterize the probability $p$ by the actually observed relative frequencies
$L/N$, where $N$ is the number of experiments and $L$ is the number of occurrences,
then the accuracy varies as a function of $p$.
Thus,
a representation of the data
has to be chosen which guarantees a constant rate of accuracy over
the entire probability range.
This results in a redefinition of the functional representation of the
relative frequency which is very similar to the quantum mechanical
representation by vectors and projectors in Hilbert space.
(Compare Mermin's
representation~\cite{mermin-02,mermin-04,mermin-qc}
of classical information theory and reversible operations on classical bits
in linear vector spaces in some analogy to the quantum formalism.)
From this point of view, taking the finite coding of probabilities by
relative frequencies into account, the classical and the quantum ``dense''
coding schemes become equivalent.

\section{Summary}

We have presented an analysis of quantum computations in terms of state identification
whose complexity grows linearly with the number of bits.
Thereby, we have characterized this domain by partitions of state space,
as well as by unitary transformations of the associated filter systems.
Such systems are not bound by the individual classical values,
as information about the (parallelized)
result of a computation may be ``spread among'' the quanta
in a way which makes it impossible to reconstruct the result
by measuring the quanta separately.
At the same time, such distributed information could be analyzed a single (or a few)
measurement(s) by proper filters resolving the computed proposition.


The method does not yield a constructive, operational method
for deciding
whether or not (and if so, how) functions or decision problems of practical interest
can be efficiently coded into quantum algorithms.
From a foundational point of view it is interesting
to realize that, while every suitable equipartitioning of state space
is equivalent to some proposition which can be interpreted as an outcome of some
quantum computation,
not all decision problems or functional evaluations which can be rephrased as
state partitions can be translated efficiently into the quantum domain.

\section*{Acknowledgments}
I am grateful to David Mermin for pointing out a generalization
of a two-bit problem to functional parity.

%\bibliography{svozil}
%\bibliographystyle{osa}
%\bibliographystyle{apsrev}
%\bibliographystyle{unsrt}
%\bibliographystyle{plain}
%\bibliographystyle{aipprocl}


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

\bibitem{ekerj96}
Ekert, A., and Jozsa, R., \emph{Reviews of Modern Physics}, \textbf{68},
  733--753 (1996).

\bibitem{pres-97}
Preskill, J., \emph{Proceedings of the Royal Society (London) A}, \textbf{454},
  469--486 (1998), \urlprefix\url{http://dx.doi.org/10.1098/rspa.1998.0171}.

\bibitem{pres-ln}
Preskill, J., Quantum computation,
  \urlprefix\url{http://www.theory.caltech.edu/~preskill/ph219/index.html},
  lecture notes.

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

\bibitem{galindo-02}
Galindo, A., and Martin-Delgado, M.~A., \emph{Reviews of Modern Physics},
  \textbf{74}, 347--432 (2002),
  \urlprefix\url{http://dx.doi.org/10.1103/RevModPhys.74.347}.

\bibitem{mermin-04}
Mermin, N.~D. (2002-2004),
  \urlprefix\url{http://people.ccmr.cornell.edu/~mermin/qcomp/CS483.html}.

\bibitem{eisert-wolf-04}
J.~Eisert, M.~W., \enquote{Quantum computing,} in \emph{Handbook Innovative
  Computing}, edited by A.~Zomaya, G.~Milburn, J.~Dongarra, D.~Bader, R.~Brent,
  M.~Eshaghian-Wilner, and F.~Seredynski, Springer, Berlin, Heidelberg, New
  York, 2004, pp. 281--283.

\bibitem{Gruska}
Gruska, J., \emph{Quantum Computing}, McGraw-Hill, London, 1999.

\bibitem{benn:97}
Bennett, C.~H., Bernstein, E., Brassard, G., and Vazirani, U., \emph{SIAM
  Journal on Computing}, \textbf{26}, 1510--1523 (1997),
  \urlprefix\url{http://dx.doi.org/10.1137/S0097539796300933}.

\bibitem{Ozhigov:1997}
Ozhigov, Y., Quantum computer can not speed up iterated applications of a black
  box.

\bibitem{bbcmw-01}
Beals, R., Buhrman, H., Cleve, R., Mosca, M., and de~Wolf, R., \emph{Journal of
  the ACM}, \textbf{48}, 778--797 (2001),
  \urlprefix\url{http://dx.doi.org/10.1145/502090.502097}.

\bibitem{cleve-99}
Cleve, R., \enquote{An Introduction to Quantum Complexity Theory,} in
  \emph{Collected Papers on Quantum Computation and Quantum Information
  Theory}, edited by C.~Macchiavello, G.~Palma, and A.~Zeilinger, World
  Scientific, Singapore.

\bibitem{fortnov-03}
Fortnow, L., \emph{Theoretical Computer Science}, \textbf{292}, 597--610
  (2003), \urlprefix\url{http://dx.doi.org/10.1016/S0304-3975(01)00377-2}.

\bibitem{rado}
Rado, T., \emph{The Bell System Technical Journal}, \textbf{XLI(41)}, 877--884
  (1962).

\bibitem{rogers1}
{Rogers, Jr.}, H., \emph{Theory of Recursive Functions and Effective
  Computability}, MacGraw-Hill, New York, 1967.

\bibitem{odi:89}
Odifreddi, P., \emph{Classical Recursion Theory}, North-Holland, Amsterdam,
  1989.

\bibitem{zeil-99}
Zeilinger, A., \emph{Foundations of Physics}, \textbf{29}, 631--643 (1999).

\bibitem{DonSvo01}
Donath, N., and Svozil, K., \emph{Physical Review A}, \textbf{65}, 044302
  (2002), \urlprefix\url{http://dx.doi.org/10.1103/PhysRevA.65.044302}.

\bibitem{svozil-2002-statepart-prl}
Svozil, K., \emph{Physical Review A}, \textbf{66}, 044306 (2002),
  \urlprefix\url{http://dx.doi.org/10.1103/PhysRevA.66.044306}.

\bibitem{svozil-2003-garda}
Svozil, K., \emph{Journal of Modern Optics}, \textbf{51}, 811--819 (2004).

\bibitem{mermin-02}
Mermin, N.~D., \emph{American Journal of Physics}, \textbf{71}, 23--30 (2003),
  \urlprefix\url{http://dx.doi.org/10.1119/1.1522741}.

\bibitem{mermin-qc}
Mermin, N.~D., \emph{IBM Journal of Research and Development}, \textbf{48},
  53--62 (2004), \urlprefix\url{http://dx.doi.org/10.1147/rd.481.0053}.

\bibitem{birkhoff-36}
Birkhoff, G., and von Neumann, J., \emph{Annals of Mathematics}, \textbf{37},
  823--843 (1936).

\bibitem{v-neumann-55}
von Neumann, J., \emph{Mathematical Foundations of Quantum Mechanics},
  Princeton University Press, Princeton, 1955.

\bibitem{svozil-ql}
Svozil, K., \emph{Quantum Logic}, Springer, Singapore, 1998.

\bibitem{svozil-2004-vax}
Svozil, K., \enquote{On Counterfactuals and Contextuality,} in \emph{AIP
  Conference Proceedings 750. {F}oundations of Probability and Physics-3},
  edited by A.~Khrennikov, American Institute of Physics, Melville, NY, 2005,
  pp. 351--360, \urlprefix\url{http://dx.doi.org/10.1063/1.1874586}.

\bibitem{v-neumann-49}
von Neumann, J., \emph{Mathematische Grundlagen der Quantenmechanik}, Springer,
  Berlin, 1932, {E}nglish translation in \cite{v-neumann-55}.

\bibitem{Farhi-98}
Farhi, E., Goldstone, J., Gutmann, S., and Sipser, M., \emph{Physical Review
  Letters}, \textbf{81}, 5442--5444 (1998),
  \urlprefix\url{http://dx.doi.org/10.1103/PhysRevLett.81.5442}.

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

\bibitem{orus-04}
Orus, R., Latorre, J.~I., and Martin-Delgado, M.~A., \emph{European Physical
  Journal D}, \textbf{29}, 119--132 (2004),
  \urlprefix\url{http://dx.doi.org/10.1140/epjd/e2004-00009-3}.

\bibitem{stadelhofer-05}
Stadelhofer, R., Suterand, D., and Banzhaf, W., \emph{Physical Review A},
  \textbf{71}, 032345 (2005).

\bibitem{581773}
Ambainis, A., Nayak, A., Ta-Shma, A., and Vazirani, U., \emph{J. ACM},
  \textbf{49}, 496--511 (2002), ISSN 0004-5411,
  \urlprefix\url{http://dx.doi.org/10.1145/581771.581773}.

\bibitem{sum-1}
Summhammer, J., \emph{Physics Letters A}, \textbf{136}, 183--187 (1989),
  \urlprefix\url{http://dx.doi.org/10.1016/0375-9601(89)90557-4}.

\bibitem{summi:93}
Summhammer, J., \enquote{Maximum predictive Power and the superposition
  principle,} in \emph{Proceedings of the Third International Workshop on
  Squeezed States and Uncertainty Relations, Maryland, August 10-13, 1993, NASA
  Conference publication Nr. 3270}, edited by D.~Han, Y.~S. Kim, N.~H. Rubin,
  Y.~Shih, and W.~W. Zachary, NASA, Greenbelt, Maryland 20771, 1993, pp.
  315--320.

\end{thebibliography}

\end{document}


Some general rules map certain irreversible functions
(e.g., associated with decision problems) into the quantum domain; for example,
\begin{itemize}
\item[(1)]
the (initial) application of Hadamard transformations
$\textsf{\textbf{H}}^{\otimes n}$
or
$\textsf{\textbf{H}}^{\otimes n}\textsf{\textbf{X}}^{\otimes n}$
to $n$ single qubits in the state $\vert 0\rangle$
``unfolds'' this states to  an (equibalanced) coherent
superposition of all possible classical states;

\item[(2)]
if $f(x)$ is many-to-one (on its arguments $x$),
the introduction of ancillary bits $y$ and the sum  $y\oplus f(x)$ modulo 2
to maintain the reversibility of the entire process;

\item[(3)]
certain useful rewriting rules, such as
$
\textsf{\textbf{H}} \vert x \rangle =\sum_{y=0}^1(-1)^{xy} \vert y \rangle
$,  or
$\textsf{\textbf{U}}_f \vert x\rangle \otimes \textsf{\textbf{H}}
\vert 1\rangle
=
(-1)^{f(x)}
\vert x\rangle \otimes \textsf{\textbf{H}}
\vert 1\rangle $,
or quantum fast Fourier transform;

\item[(4)]
the (final) use of Hadamard transformations to ``fold back'' coherent
superpositions of the processed states into ones which can be optimally identified.

\end{itemize}

\newpage

\begin{table}
\centerline{
\begin{tabular}{ccccccccccccccc}
\hline
$\pm$&$f$&
&\multicolumn{8}{c }{$\vert x\rangle \vert y\rangle \vert z\oplus f(x,y)\rangle$}
\\
\hline
$+$&$f_{ 1}       $:&        &000&010&100&110 &  001&011&101&111      \\
$-$&$f_{ 2}       $:&        &000&010&100&111 &  001&011&101&110      \\
$-$&$f_{ 3}       $:&        &000&010&101&110 &  001&011&100&111      \\
$-$&$f_{ 4}       $:&        &000&011&100&110 &  001&010&101&111      \\
$-$&$f_{ 5}       $:&        &001&010&100&110 &  000&011&101&111      \\
$+$&$f_{ 6}       $:&        &000&010&101&111 &  001&011&100&110      \\
$+$&$f_{ 7}       $:&        &000&011&100&111 &  001&010&101&110      \\
$+$&$f_{ 8}       $:&        &001&010&100&111 &  000&011&101&110      \\
$+$&$f_{ 9}       $:&        &000&011&101&110 &  001&010&100&111      \\
$+$&$f_{10}       $:&        &001&010&101&110 &  000&011&100&111      \\
$+$&$f_{11}       $:&        &001&011&100&110 &  000&010&101&111      \\
$-$&$f_{12}       $:&        &000&011&101&111 &  001&010&100&110      \\
$-$&$f_{13}       $:&        &001&010&101&111 &  000&011&100&110      \\
$-$&$f_{14}       $:&        &001&011&100&111 &  000&010&101&110      \\
$-$&$f_{15}       $:&        &001&011&101&110 &  000&010&100&111      \\
$+$&$f_{16}       $:&        &001&011&101&111 &  000&010&100&110      \\
\hline
\end{tabular}
}
\caption{123.... \label{2005-ko-t2} }
\end{table}


\newpage

\begin{table}
\centerline{
\begin{tabular}{ccccccccccccccc}
\hline
$\pm$&$f$&
&\multicolumn{8}{c }{$\left(
\textsf{\textbf{H}}^{\oplus 2} \oplus \textsf{\textbf{1}}
\right)
\textsf{\textbf{U}}_f
\left(
\textsf{\textbf{H}}^{\oplus 2} \oplus \textsf{\textbf{H}}
\right) \vert 00\rangle \vert 1\rangle  $}
\\
\hline
$+$&$f_{ 1}       $:&        &000&010&100&110&         001&011&101&111      \\
$-$&$f_{ 2}       $:&        &000&010&100&-111&        001&011&101&-110      \\
$-$&$f_{ 3}       $:&        &000&010&-101&110&        001&011&-100&111      \\
$-$&$f_{ 4}       $:&        &000&-011&100&110&        001&-010&101&111      \\
$-$&$f_{ 5}       $:&        &-001&010&100&110&        -000&011&101&111      \\
$+$&$f_{ 6}       $:&        &000&010&-101&-111&       001&011&-100&-110      \\
$+$&$f_{ 7}       $:&        &000&-011&100&-111&       001&-010&101&-110      \\
$+$&$f_{ 8}       $:&        &-001&010&100&-111&       -000&011&101&-110      \\
$+$&$f_{ 9}       $:&        &000&-011&-101&110&       001&-010&-100&111      \\
$+$&$f_{10}       $:&        &-001&010&-101&110&       -000&011&-100&111      \\
$+$&$f_{11}       $:&        &-001&-011&100&110&       -000&-010&101&111      \\
$-$&$f_{12}       $:&        &000&-011&-101&-111&      001&-010&-100&-110      \\
$-$&$f_{13}       $:&        &-001&010&-101&-111&      -000&011&-100&-110      \\
$-$&$f_{14}       $:&        &-001&-011&100&-111&      -000&-010&101&-110      \\
$-$&$f_{15}       $:&        &-001&-011&-101&110&      -000&-010&-100&111      \\
$+$&$f_{16}       $:&        &-001&-011&-101&-111&     -000&-010&-100&-110      \\
\hline
\end{tabular}
}
\caption{123.... \label{2005-ko-t3} }
\end{table}




%\section{Introduction}




GramSchmidt[{{1, -1, -1, 1}, {1, -1, 1, -1}, {1, 1, 1, 1}, {1, 1, -1, -1}},
  Normalized -> False]


U = {
{u11, u12, u13, u14},
{u21, u22, u23, u24},
{u31, u32, u33, u34},
{u41, u42, u43, u44}
};

Solve[{
U.{1,0,0,0}== (1/2)* {1, 1, -1, -1},
U.{0,1,0,0}== (1/2)* {1, -1, 1, -1},
U.{0,0,1,0}== (1/2)* {1, 1, 1, 1},
U.{0,0,0,1}== (1/2)* {1, -1, -1, 1}
},{u11, u12, u13, u14,u21, u22, u23, u24,u31, u32, u33, u34,u41, u42, u43, u44}]

U=(1/2)
{{ 1,  1, 1,  1},
 { 1, -1, 1, -1},
 {-1,  1, 1, -1},
 {-1, -1, 1, 1}}

U.DiagonalMatrix[{1,1,0,0}].Transpose[U]

U.DiagonalMatrix[{1,1,0,0}].Transpose[U]  //MatrixForm

(U.DiagonalMatrix[{1, 1, 0, 0}].Transpose[U]).{1, -1, -1, 1}(1/2)
(U.DiagonalMatrix[{1, 1, 0, 0}].Transpose[U]).{1, -1, 1, -1}(1/2)

(U.DiagonalMatrix[{1,  0,1, 0}].Transpose[U]).{1, -1, -1, 1}(1/2)
(U.DiagonalMatrix[{1,  0,1, 0}].Transpose[U]).{1, -1, 1, -1}(1/2)

{               Sort[{000,-010,-100,110 ,  -001,011,101,-111}],
                Sort[{000,-010,-100,-111 ,  -001,011,101,110}],
                Sort[{000,-010,101,110 ,  -001,011,-100,-111}],
                Sort[{000,011,-100,110 ,  -001,-010,101,-111}],
                Sort[{-001,-010,-100,110 ,  000,011,101,-111}],
                Sort[{000,-010,101,-111 ,  -001,011,-100,110}],
                Sort[{000,011,-100,-111 ,  -001,-010,101,110}],
                Sort[{-001,-010,-100,-111 ,  000,011,101,110}],
                Sort[{000,011,101,110 ,  -001,-010,-100,-111}],
                Sort[{-001,-010,101,110 ,  000,011,-100,-111}],
                Sort[{-001,011,-100,110 ,  000,-010,101,-111}],
                Sort[{000,011,101,-111 ,  -001,-010,-100,110}],
                Sort[{-001,-010,101,-111 ,  000,011,-100,110}],
                Sort[{-001,011,-100,-111 ,  000,-010,101,110}],
                Sort[{-001,011,101,110 ,  000,-010,-100,-111}],
                Sort[{-001,011,101,-111 ,  000,-010,-100,110}]}



A=               {{aaa,aba,baa,bbb,aab,abb,bab,bba},
                  {aaa,aba,bab,bba,aab,abb,baa,bbb},
                  {aaa,abb,baa,bba,aab,aba,bab,bbb},
                  {aab,aba,baa,bba,aaa,abb,bab,bbb},
                  {aaa,abb,bab,bbb,aab,aba,baa,bba},
                  {aab,aba,bab,bbb,aaa,abb,baa,bba},
                  {aab,abb,baa,bbb,aaa,aba,bab,bba},
                  {aab,abb,bab,bba,aaa,aba,baa,bbb}};




B=                {{aaa,aba,baa,bba,aab,abb,bab,bbb},
                  {aaa,aba,bab,bbb,aab,abb,baa,bba},
                  {aaa,abb,baa,bbb,aab,aba,bab,bba},
                  {aab,aba,baa,bbb,aaa,abb,bab,bba},
                  {aaa,abb,bab,bba,aab,aba,baa,bbb},
                  {aab,aba,bab,bba,aaa,abb,baa,bbb},
                  {aab,abb,baa,bba,aaa,aba,bab,bbb},
                  {aab,abb,bab,bbb,aaa,aba,baa,bba}};


(A.DiagonalMatrix[{t1,t2,t3,t4,t5,t6,t7,t8}])
(B.DiagonalMatrix[{s1,s2,s3,s4,s5,s6,s7,s8}])


Solve[ Table[
    Sort[(DiagonalMatrix[{t1, t2, t3, t4, t5, t6, t7,
                    t8}].A)[[i]]].Sort[(DiagonalMatrix[{s1, s2, s3, s4, s5,
                    s6, s7, s8}].B)[[i]]] == 0, {i, 1, 8}], {t1, t2, t3, t4,
    t5, t6, t7, t8, t1, t2, t3, t4, t5, t6, t7, t8}]



A=               {Sort[{aaa, aba,baa,-bbb,aab,    abb, bab,bba}],
                  Sort[{aaa, aba,bab,-bba,aab,    abb, baa,bbb}],
                  Sort[{aaa, abb,baa,-bba,aab,    aba, bab,bbb}],
                  Sort[{aab, aba,baa,-bba,aaa,    abb, bab,bbb}],
                  Sort[{aaa, abb,bab,-bbb,aab,    aba, baa,bba}],
                  Sort[{aab, aba,bab,-bbb,aaa,    abb, baa,bba}],
                  Sort[{aab, abb,baa,-bbb,aaa,    aba, bab,bba}],
                  Sort[{aab, abb,bab,-bba,aaa,    aba, baa,bbb}]};
B=               {Sort[{aaa, aba,baa,-bba,aab,    abb, bab,bbb}],
                  Sort[{aaa, aba,bab,-bbb,aab,    abb, baa,bba}],
                  Sort[{aaa, abb,baa,-bbb,aab,    aba, bab,bba}],
                  Sort[{aab, aba,baa,-bbb,aaa,    abb, bab,bba}],
                  Sort[{aaa, abb,bab,-bba,aab,    aba, baa,bbb}],
                  Sort[{aab, aba,bab,-bba,aaa,    abb, baa,bbb}],
                  Sort[{aab, abb,baa,-bba,aaa,    aba, bab,bbb}],
                  Sort[{aab, abb,bab,-bbb,aaa,    aba, baa,bba}]};
A // MatrixForm
B // MatrixForm


A={                  {aaa,aba,baa,-bbb, aab,abb,bab,-bba},
                     {aaa,aba,-bab,bba, aab,abb,-baa,bbb},
                     {aaa,-abb,baa,bba, aab,-aba,bab,bbb},
                     {-aab,aba,baa,bba, -aaa,abb,bab,bbb},
                     {aaa,-abb,-bab,-bbb,  aab,-aba,-baa,-bba},
                     {-aab,aba,-bab,-bbb,  -aaa,abb,-baa,-bba},
                     {-aab,-abb,baa,-bbb,  -aaa,-aba,bab,-bba},
                     {-aab,-abb,-bab,bba,  -aaa,-aba,-baa,bbb}}

B={                  {aaa,aba,baa,bba,  aab,abb,bab,bbb},
                     {aaa,aba,-bab,-bbb,aab,abb,-baa,-bba},
                     {aaa,-abb,baa,-bbb,aab,-aba,bab,-bba},
                     {-aab,aba,baa,-bbb,-aaa,abb,bab,-bba},
                     {aaa,-abb,-bab,bba,aab,-aba,-baa,bbb},
                     {-aab,aba,-bab,bba,-aaa,abb,-baa,bbb},
                     {-aab,-abb,baa,bba,-aaa,-aba,bab,bbb},
                     {-aab,-abb,-bab,-bbb, -aaa,-aba,-baa,-bba}}

AS={           Sort[{aaa,aba,baa,-bbb, aab,abb,bab,-bba}],
               Sort[{aaa,aba,-bab,bba, aab,abb,-baa,bbb}],
               Sort[{aaa,-abb,baa,bba, aab,-aba,bab,bbb}],
               Sort[{-aab,aba,baa,bba, -aaa,abb,bab,bbb}],
               Sort[{aaa,-abb,-bab,-bbb,  aab,-aba,-baa,-bba}],
               Sort[{-aab,aba,-bab,-bbb,  -aaa,abb,-baa,-bba}],
               Sort[{-aab,-abb,baa,-bbb,  -aaa,-aba,bab,-bba}],
               Sort[{-aab,-abb,-bab,bba,  -aaa,-aba,-baa,bbb}]}

BS={           Sort[{aaa,aba,baa,bba,  aab,abb,bab,bbb}],
               Sort[{aaa,aba,-bab,-bbb,aab,abb,-baa,-bba}],
               Sort[{aaa,-abb,baa,-bbb,aab,-aba,bab,-bba}],
               Sort[{-aab,aba,baa,-bbb,-aaa,abb,bab,-bba}],
               Sort[{aaa,-abb,-bab,bba,aab,-aba,-baa,bbb}],
               Sort[{-aab,aba,-bab,bba,-aaa,abb,-baa,bbb}],
               Sort[{-aab,-abb,baa,bba,-aaa,-aba,bab,bbb}],
               Sort[{-aab,-abb,-bab,-bbb, -aaa,-aba,-baa,-bba}]}

MatrixForm[AS]

MatrixForm[BS]



$+$&$f_{ 1}       $:&        &00&01&10&11                              \\
$+$&$f_{ 6}       $:&        &00&01&-10&-11                              \\
$+$&$f_{ 7}       $:&        &00&-01&10&-11                              \\
$+$&$f_{ 8}       $:&        &-00&01&10&-11                              \\
$+$&$f_{ 9}       $:&        &00&-01&-10&11                              \\
$+$&$f_{10}       $:&        &-00&01&-10&11                              \\
$+$&$f_{11}       $:&        &-00&-01&10&11                              \\
$+$&$f_{16}       $:&        &-00&-01&-10&-11                              \\

$-$&$f_{ 2}       $:&        &00&01&10&-11                              \\
$-$&$f_{ 3}       $:&        &00&01&-10&11                              \\
$-$&$f_{ 4}       $:&        &00&-01&10&11                              \\
$-$&$f_{ 5}       $:&        &-00&01&10&11                              \\
$-$&$f_{12}       $:&        &00&-01&-10&-11                              \\
$-$&$f_{13}       $:&        &-00&01&-10&-11                              \\
$-$&$f_{14}       $:&        &-00&-01&10&-11                              \\
$-$&$f_{15}       $:&        &-00&-01&-10&11                              \\



 a={                             {1,0,0,0}+{0,1,0,0}+{0,0,1,0}+{0,0,0,1}       ,
                              {1,0,0,0}+{0,1,0,0}-{0,0,1,0}-{0,0,0,1}       ,
                              {1,0,0,0}-{0,1,0,0}+{0,0,1,0}-{0,0,0,1}       ,
                              -{1,0,0,0}+{0,1,0,0}+{0,0,1,0}-{0,0,0,1}       ,
                              {1,0,0,0}-{0,1,0,0}-{0,0,1,0}+{0,0,0,1}       ,
                              -{1,0,0,0}+{0,1,0,0}-{0,0,1,0}+{0,0,0,1}       ,
                              -{1,0,0,0}-{0,1,0,0}+{0,0,1,0}+{0,0,0,1}       ,
                              -{1,0,0,0}-{0,1,0,0}-{0,0,1,0}-{0,0,0,1}       } //MatrixForm

b={                             {1,0,0,0}+{0,1,0,0}+{0,0,1,0}-{0,0,0,1}       ,
                              {1,0,0,0}+{0,1,0,0}-{0,0,1,0}+{0,0,0,1}       ,
                              {1,0,0,0}-{0,1,0,0}+{0,0,1,0}+{0,0,0,1}       ,
                              -{1,0,0,0}+{0,1,0,0}+{0,0,1,0}+{0,0,0,1}       ,
                              {1,0,0,0}-{0,1,0,0}-{0,0,1,0}-{0,0,0,1}       ,
                              -{1,0,0,0}+{0,1,0,0}-{0,0,1,0}-{0,0,0,1}       ,
                              -{1,0,0,0}-{0,1,0,0}+{0,0,1,0}-{0,0,0,1}       ,
                              -{1,0,0,0}-{0,1,0,0}-{0,0,1,0}+{0,0,0,1}     } //MatrixForm

<< LinearAlgebra`Orthogonalization`

GramSchmidt[{                             {1,0,0,0}+{0,1,0,0}+{0,0,1,0}+{0,0,0,1}       ,
                              {1,0,0,0}+{0,1,0,0}-{0,0,1,0}-{0,0,0,1}       ,
                              {1,0,0,0}-{0,1,0,0}+{0,0,1,0}-{0,0,0,1}       ,
                              -{1,0,0,0}+{0,1,0,0}+{0,0,1,0}-{0,0,0,1}       ,
                              {1,0,0,0}-{0,1,0,0}-{0,0,1,0}+{0,0,0,1}       ,
                              -{1,0,0,0}+{0,1,0,0}-{0,0,1,0}+{0,0,0,1}       ,
                              -{1,0,0,0}-{0,1,0,0}+{0,0,1,0}+{0,0,0,1}       ,
                              -{1,0,0,0}-{0,1,0,0}-{0,0,1,0}-{0,0,0,1}       ,
            {1,0,0,0}+{0,1,0,0}+{0,0,1,0}-{0,0,0,1}       ,
                              {1,0,0,0}+{0,1,0,0}-{0,0,1,0}+{0,0,0,1}       ,
                              {1,0,0,0}-{0,1,0,0}+{0,0,1,0}+{0,0,0,1}       ,
                              -{1,0,0,0}+{0,1,0,0}+{0,0,1,0}+{0,0,0,1}       ,
                              {1,0,0,0}-{0,1,0,0}-{0,0,1,0}-{0,0,0,1}       ,
                              -{1,0,0,0}+{0,1,0,0}-{0,0,1,0}-{0,0,0,1}       ,
                              -{1,0,0,0}-{0,1,0,0}+{0,0,1,0}-{0,0,0,1}       ,
                              -{1,0,0,0}-{0,1,0,0}-{0,0,1,0}+{0,0,0,1}     }]


<< LinearAlgebra`Orthogonalization`

GramSchmidt[{
{1,0,0,0,0,1,1,1,1,1,1,0,0,0,0,1} (1/Sqrt[8]),
{0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}
            }]


\section{Generalized $n$-ary decision problems}

\begin{table}
\centerline{
\begin{tabular}{ccccccccccccccc}
\hline
%& &\multicolumn{4}{c}{$(-1)^{f_i(x)+f_j(y)} $}\\
$f$& &
$+$&
$0$&
$-$
\\
\hline
    $f_{   0}      $ &  &  $+$  &  $+$  &  $+$      \\
    $f_{   1}      $ &  &  $+$  &  $+$  &  $0$      \\
    $f_{   2}      $ &  &  $+$  &  $+$  &  $-$      \\
    $f_{   3}      $ &  &  $+$  &  $0$  &  $+$      \\
    $f_{   4}      $ &  &  $+$  &  $0$  &  $0$      \\
    $f_{   5}      $ &  &  $+$  &  $0$  &  $-$      \\
    $f_{   6}      $ &  &  $+$  &  $-$  &  $+$      \\
    $f_{   7}      $ &  &  $+$  &  $-$  &  $0$      \\
    $f_{   8}      $ &  &  $+$  &  $-$  &  $-$      \\
    $f_{   9}      $ &  &  $0$  &  $+$  &  $+$      \\
    $f_{  10}      $ &  &  $0$  &  $+$  &  $0$      \\
    $f_{  11}      $ &  &  $0$  &  $+$  &  $-$      \\
    $f_{  12}      $ &  &  $0$  &  $0$  &  $+$      \\
    $f_{  13}      $ &  &  $0$  &  $0$  &  $0$      \\
    $f_{  14}      $ &  &  $0$  &  $0$  &  $-$      \\
    $f_{  15}      $ &  &  $0$  &  $-$  &  $+$      \\
    $f_{  16}      $ &  &  $0$  &  $-$  &  $0$      \\
    $f_{  17}      $ &  &  $0$  &  $-$  &  $-$      \\
    $f_{  18}      $ &  &  $-$  &  $+$  &  $+$      \\
    $f_{  19}      $ &  &  $-$  &  $+$  &  $0$      \\
    $f_{  20}      $ &  &  $-$  &  $+$  &  $-$      \\
    $f_{  21}      $ &  &  $-$  &  $0$  &  $+$      \\
    $f_{  22}      $ &  &  $-$  &  $0$  &  $0$      \\
    $f_{  23}      $ &  &  $-$  &  $0$  &  $-$      \\
    $f_{  24}      $ &  &  $-$  &  $-$  &  $+$      \\
    $f_{  25}      $ &  &  $-$  &  $-$  &  $0$      \\
    $f_{  26}      $ &  &  $-$  &  $-$  &  $-$      \\
\hline
\end{tabular}
}
\caption{All tri-valued functions of one trit in reverse lexicographic order
($+ > 0 > -$).
\label{2005-ko-t31tri} }
\end{table}