\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}