A Comparison of Quantum Oracles
Elham Kashefi$^{*\dagger}$
Adrian Kent$^{\S}$
Vlatko Vedral$^{*}$ and Konrad Banaszek$^{*\dagger}$
A standard quantum oracle $S_f$ for a general function $f: Z_N \rightarrow Z_N $ is defined to act on two input states and return two outputs, with inputs $\ket{i}$ and $\ket{j}$ ($i,j \in Z_N $) returning outputs $\ket{i}$ and $\ket{j \oplus f(i)}$. However, if $f$ is known to be a one-to-one function, a simpler oracle, $M_f$, which returns $\ket{f(i)}$ given $\ket{i}$, can also be defined. We consider the relative strengths of these oracles. We define a simple promise problem which minimal quantum oracles can solve exponentially faster than classical oracles, via an algorithm which cannot be naively adapted to standard quantum oracles. We show that $S_f$ can be constructed by invoking $M_f$ and $(M_f )^{-1}$ once each, while $\Theta(\sqrt{N})$ invocations of $S_f$ and/or $(S_f )^{-1}$ are required to construct $M_f$.
oracle-web.tex
\documentstyle[aps,pra,epsf,multicol,amssymb,pstricks,latexsym,graphicx]{revtex}

\newcommand{\swapbit}[1]{\rput#1{$\times$}}
\newcommand{\ctrbit}[1]{\rput#1{$\bullet$}}
\newcommand{\targetbit}[1]{\rput#1{$\oplus$}}
\newcommand{\Comment}[1]

\newtheorem{definition}{Definition}[section]
\newtheorem{theorem}[definition]{Theorem}
\newtheorem{proposition}[definition]{Proposition}
\newtheorem{corollary}[definition]{Corollary}
\def\eps{\epsilon}
\def\BRA#1{\left\langle #1\right|}
\def\KET#1{\left| #1\right\rangle}
\def\bra#1{\langle #1 |}
\def\ket#1{| #1\rangle}
\def\braket#1#2{\langle \, #1 \, | \, #2 \, \rangle}
\def\norm#1{\left\Vert \, #1 \, \right\Vert}
\def\inprod#1#2{\langle \, #1 \, , \, #2 \, \rangle}
\def\S{{\cal{S}}}
\def\half{{1\over 2}}
\def\H{{\cal{H}}}
\def\M{{{}^4\!M}}
\def\f{{{}^4\!f}}
\def\C{{\cal{C}}}
\def\B{{\cal{B}}}
\def\D{{\rm{D}}}
\def\qed{\qquad{\bf \rm QED.}}
\def\defn{\noindent{\bf Definition} \qquad}
\def\Prob{{\rm Prob}}
\def\x{{\rm{x}}}
\def\s{{\rm{s}}}
\def\v{{\rm{v}}}
\def\t{{\rm{t}}}
\def\R{\hbox{\rm I \kern-5pt R}}
\def\q{{\tilde q}}
\def\Q{{\widetilde Q}}
\def\Tr{{\rm{Tr}}}

\begin{document}

\title{A Comparison of Quantum Oracles} \author{Elham
Kashefi$^{*\dagger}$, Adrian Kent$^{\S}$, Vlatko Vedral$^{*}$ and
Konrad Banaszek$^{*\dagger}$} \address{$^{*}$Optics Section, The
Blackett Laboratory, Imperial College, London SW7 2BZ, England \\
$^{\dagger}$ Centre for Quantum Computation, Clarendon Laboratory,
University of Oxford, Parks Road, Oxford OX1 3PU, England \\ $^{\S}$
Hewlett-Packard Laboratories, Filton Road, Stoke Gifford, Bristol BS34
8QZ, England}
\date{\today}
\maketitle

\begin{abstract}
A standard quantum oracle $S_f$ for a general function $f: Z_N
 \rightarrow Z_N $ is defined to act on two input states and return
 two outputs, with inputs $\ket{i}$ and $\ket{j}$ ($i,j \in Z_N $)
 returning outputs $\ket{i}$ and $\ket{j \oplus f(i)}$. However, if
 $f$ is known to be a one-to-one function, a simpler oracle, $M_f$,
 which returns $\ket{f(i)}$ given $\ket{i}$, can also be defined. We
 consider the relative strengths of these oracles.  We define a
 simple promise problem which minimal quantum oracles can solve
 exponentially faster than classical oracles, via an algorithm which
 cannot be naively adapted to standard quantum oracles.  We show
 that $S_f$ can be constructed by invoking $M_f$ and $(M_f )^{-1}$
 once each, while $\Theta(\sqrt{N})$ invocations of $S_f$
 and/or $(S_f )^{-1}$ are required to construct $M_f$.
\end{abstract}

\draft

\begin{multicols}{2}
Recent years have witnessed an explosion of interest in quantum
computation, as it becomes clearer that quantum algorithms are more
efficient than any known classical algorithm for a variety of
tasks.\cite{Deutsch85,Shor94,Grover96,BBBV97}. One important way of
comparing the efficiencies is by analysing {\it query complexity},
which measures the number of invocations of an ``oracle'' --- which
may be a standard circuit implementing a useful sub-routine, a
physical device, or a purely theoretical construct --- needed to
complete a task. A number of general results show the limitations and
advantages of quantum computers using the query complexity models
\cite{BBCMW98,vanDam98,Cleve99}.

In this paper we compare the query complexity analysis of quantum
algorithms given two different ways of representing a permutation in
terms of a black box quantum oracle. We begin with a short discussion
of graph isomorphism problems, which motivates the rest of the paper.

Suppose we are given two graphs, $G_1 = (V_1 , E_1 )$ and $G_2 = (V_2
, E_2)$, represented as sets of vertices and edges in some standard
notation. The graph isomorphism (GI) problem is to determine whether
$G_1$ and $G_2$ are isomorphic: that is, whether there is a bijection
$f: V_1 \rightarrow V_2$ such that $( f(u) , f(v) ) \in E_2$ if and
only if $(u,v) \in E_1$. (We assume $| V_1| = | V_2 |$, else the
problem is trivial.)  GI is a problem which is NP but not known to be
NP-complete for classical computers, and for which no polynomial time
quantum algorithm is currently known.

We are interested in a restricted version (NAGI) of GI, in which it is
given that $G_1$ and $G_2$ are non-automorphic: i.e., they have no
non-trivial automorphisms. So far as we are aware, no polynomial time
classical or quantum algorithms are known for NAGI either. The
following observations suggest a possible line of attack in the
quantum case.

First, for any non-automorphic graph $G = (V,E)$, we can define a
unitary map $M_G$ that takes permutations $\rho$ of $V$ as inputs and
outputs the permuted graph $\rho(G) = (\rho(V), \rho(E))$, with some
standard ordering (e.g. alphabetical) of the vertices and edges, in
some standard computational basis representations. That is, writing $|
V | = N$, for any $\rho \in S_N$, $M_G$ maps $\ket{\rho}$ to
$\ket{\rho(G)}$. Consider a pair $(G_1 , G_2 )$ of non-automorphic
graphs. Given circuits implementing $M_{G_1}$, $M_{G_2}$, we could
input copies of the state $ \frac{1}{\sqrt{N!}} \sum_{\rho \in S_N}
\ket{\rho}$ to each circuit, and compare the outputs $\ket{\psi_i} =
\frac{1}{\sqrt{N!}}
\sum_{\rho \in S_N} \ket{ \rho (G_i ) }$. Now, if the graphs are
isomorphic, these outputs are equal; if not, they are
orthogonal. These two cases can be distinguished with arbitrarily high
confidence in polynomial time (see below), so this would solve the
problem.

Unfortunately, our algorithm for NAGI requires constructing circuits
for the $M_{G_i}$, which could be at least as hard as solving the
original problem. On the other hand, it is easy to devise a circuit,
$S_G$, which takes two inputs, $\ket{\rho}$ and a blank set of states
$\ket{0}$, and outputs $\ket{\rho}$ and $\ket{\rho (G) }$. Since $S_G$
and $M_G$ implement apparently similar tasks, one might hope to find a
way of constructing $M_G$ from a network involving a small number of
copies of $S_G$. Such a construction would solve NAGI. Alternatively,
one might hope to prove such a construction is impossible, and so
definitively close off this particular line of attack.

Thus motivated, we translate this into an abstract problem in query
complexity.

Consider the following oracles, defined for a general function $f: \{0,1\}^m
\rightarrow \{0,1\}^n$:
\begin{itemize}
\itemsep0pt \parsep0pt
\item  the {\it standard} oracle,  $ S_f : |x\rangle |b\rangle
\rightarrow |x\rangle |b \oplus f(x)\rangle$.
\item the {\it Fourier phase} oracle, $P_f : |x\rangle |b\rangle
\rightarrow e^{2\pi i f(x) b / 2^n }|x\rangle |b\rangle$.
\end{itemize}
Here $x$ and $b$ are strings of $m$ and $n$ bits respectively, represented
as numbers modulo $M=2^m$ and $N = 2^n$, $| x
\rangle$ and $| b \rangle$ are the corresponding computational basis
states, and $\oplus$ is addition modulo $2^n$.

Note that the oracles $P_f$ and
$S_f$ are equivalent, in the sense that each can be constructed by an
$f$-independent quantum
circuit containing just one copy of the other, and also
equivalent to their inverses.   To see this, define the quantum
Fourier transform operation $F$ and the parity reflection $R=F^2$ by
$$
F : \ket{j} \rightarrow \frac{1}{ \sqrt{N}}
\sum_{k=0}^{N - 1} \exp ( 2 \pi i j k / N )
\ket{k} \, , \qquad
R: \ket{j} \rightarrow \ket{-j} \, .
$$
Then we have
\begin{eqnarray*}
&(& I \otimes F ) \circ S_f \circ (I \otimes F^{-1} ) = P_f \, , \\
&(& I \otimes F^{-1} ) \circ P_f \circ (I \otimes F) = S_f \, , \\
&(& I \otimes R ) \circ S_f \circ (I \otimes R ) = (S_f )^{-1} \, , \\
& (& I \otimes R ) \circ P_f \circ (I \otimes R ) = (P_f )^{-1} \, .
\end{eqnarray*}

For the rest of the paper we take $m=n$ and suppose we know $f$ is a
permutation on the set $\{ 0,1 \}^n$. There is then a simpler
invertible quantum map associated to $f$:
\begin{itemize}
\itemsep0pt \parsep0pt
\item the {\it  minimal} oracle: $ M_f : |x\rangle \rightarrow |f(x)\rangle$.
\end{itemize}

We can model NAGI, and illustrate the different behaviour of
standard and minimal oracles, by a promise problem. Suppose we are
given two permutations, $\alpha$ and $\beta$, of $Z_N$, and a subset
$S$ of $Z_N$, and are promised that the images $\alpha(S)$ and
$\beta(S)$ are either identical or disjoint.  The problem is to
determine which. (This problem has been considered in a different
context by Buhrman et al \cite{BCWW01}.)

We represent
elements $x \in Z_N$ by computational basis states of $n$ qubits in
the standard way, and write $|S \rangle = \sum_{x \in S} \ket{x}$.

Figure $1$ gives a quantum network with minimal oracles that
identifies disjoint images with probability at least $1/2$.

\begin{figure}
\psset{unit=0.6cm}
\begin{pspicture}(0,8)(-1,0)
%\psgrid(10,10)
\psline(0.5,1)(10,1)
\psline(0.5,2)(9.5,2)
\rput(7,2.6){$\vdots$}
\rput(0.85,2.6){$\vdots$}
\psline(0.5,3)(9.5,3)
\psline(0.5,3.5)(9.5,3.5)
\psline(0.5,4)(9.5,4)
\rput(.2,3.05){$\displaystyle\left\{\rule{0pt}{0.8cm}\right.$}
\rput(-.6,2.9){$\displaystyle |S \rangle$}
\psline(.5,5)(9.5,5)
\rput(7,5.6){$\vdots$}
\rput(0.85,5.6){$\vdots$}
\psline(.5,6)(9.5,6)
\psline(.5,6.5)(9.5,6.5)
\psline(.5,7)(9.5,7)
\rput(.2,6.05){$\displaystyle\left\{\rule{0pt}{0.8cm}\right.$}
\rput(-.6,5.9){$\displaystyle |S \rangle$}
\rput(0,1){$\displaystyle |1 \rangle$}
\psline(4,1)(4,7)
\psline(5,1)(5,6.5)
\psline(6,1)(6,6)
\psline(8,1)(8,5)
\psframe[fillstyle=solid,fillcolor=white](1.2,1.8)(2.6,4.2)
\rput(1.9,3){$\scriptstyle O_{\beta}$}
\psframe[fillstyle=solid,fillcolor=white](1.2,4.8)(2.6,7.2)
\rput(1.9,6){$\scriptstyle O_{\alpha}$}
\psframe[fillstyle=solid,fillcolor=white](1.5,1.4)(2.3,0.6)
\rput(1.9,1){$\scriptstyle H$}
\pscircle(4,1){.1}
\pscircle(5,1){.1}
\pscircle(6,1){.1}
\pscircle(8,1){.1}
\psframe[fillstyle=solid,fillcolor=white](8.6,1.4)(9.4,0.6)
\rput(9,1){$\scriptstyle H$}
\swapbit{(4,7)}
\swapbit{(4,4)}
\swapbit{(5,6.5)}
\swapbit{(5,3.5)}
\swapbit{(6,6)}
\swapbit{(6,3)}
\swapbit{(8,5)}
\swapbit{(8,2)}
\pswedge(10,1){.4}{270}{90}
\end{pspicture}
\caption{A quantum circuit for the permutation promise
problem. $O_{\alpha}$ and $O_{\beta}$ are minimal oracles for
computing the permutations $\alpha$ and $\beta$ respectively,
$|S\rangle$ is the superposition of all the basis states, $H$ is the
Hadamard transformation, and all the other gates are conditional swap
gates, where circles signify control bits.}
\end{figure}

Let $A=\{
 \alpha(x)|x \in S \}$ and $B=\{ \beta(x)| x \in S \}$.  One query to
the oracles $M_{\alpha}$ and $M_{\beta}$ creates the (unnormalised) states
$| A \rangle$ and $| B \rangle$
respectively.  The state before applying the controlled gates is:
\begin{eqnarray*}
| A \rangle | B \rangle
\otimes (|0\rangle - |1\rangle )
\end{eqnarray*}
After controlled swap gates, the state becomes:
$$
| A \rangle | B \rangle |0\rangle -
| B \rangle | A \rangle |1\rangle  \, .
$$
The final Hadamard gate on the ancilla qubit gives:
$$
( | A \rangle | B \rangle  - | B \rangle | A \rangle ) |0\rangle
+ ( | A \rangle | B \rangle  + | B \rangle | A \rangle )  |1\rangle
$$

A $|0\rangle$ outcome shows unambiguously that the images are disjoint. A
$|1\rangle$ outcome is generated with probability $1$ if the images are
identical, and with probability $1/2$ if the images are disjoint.
Repeating the computation $K$ times allows one to exponentially improve
the confidence of the result. If after $K$ trials we get $|0\rangle$ at
least once, we know for certain that $\alpha(S) \neq \beta(S)$. When all
the $K$ outcomes were $|1\rangle$, the conclusion that
$\alpha(S)=\beta(S)$ has the conditional probability $p_K = \frac{1}{2^K}$
of having been erroneously generated by disjoint input images. Note that
$p_K$ is independent of the problem size and decreases exponentially with
the number of repetitions.

Clearly, a naive adaptation of the algorithm to standard oracles does
not work.  Replacing $M_{\alpha}$ and $M_{\beta}$ by $S_{\alpha}$ and
$S_{\beta}$, and replacing the inputs by $\ket{S} \otimes \ket{0}$,
results in output states which are orthogonal if the images are
disjoint, but also in general very nearly orthogonal if the images are
identical.  Applying a symmetric projection as above thus almost
always fails to distinguish the cases. To the best of our knowledge a
non-trivial lower bound for this problem using the $S_f$ is not known
(however, see \cite{Aaronson01}).

This example suggests that minimal oracles may be rather more powerful
than standard oracles. To establish a more precise version of this
hypothesis, we examine how good each oracle is at simulating the
other. One way round turns out to be simple.  We can construct $S_f$
from $M_f$ and $(M_f)^{-1} = M_{f^{-1}}$ as follows:
$$
S_f = ( M_{f^{-1}} \otimes I ) \circ A \circ ( M_f \otimes I ) \,
$$
where $\circ$ represents the composition of operations (or the concatenation of
networks) and the
modulo $N$ adder $A$ is defined by $A : \ket{a} \otimes \ket{b}
\rightarrow \ket{a} \otimes \ket{a \oplus b }$.

Suppose that we are given $M_f$ in the form of a specified
complicated quantum circuit.  We may be completely unable
to simplify the circuit or deduce a simpler form of $f$ from it.
However, by reversing the circuit gate by gate, we can construct
a circuit for $(M_f )^{-1}$.  Hence, by the above construction,
we can produce a circuit for $S_f$, using one copy and one
reversed copy of the circuit for $M_f$.

This way of looking at oracles can be formalised into
the {\it circuit model}, in which the query
complexity of an algorithm involving an
oracle $O_f$ associated to a function $f$ is the number of copies
of $O_f$ and/or $O^{-1}_f$ required to implement the algorithm in a
circuit that, apart from the oracles, is independent of $f$.
In the circuit model, a standard oracle can easily be simulated
given a minimal oracle.  Ignoring constant factors, we say that the minimal
oracle is at least as strong as the standard oracle.

It should be stressed that, while the circuit model has a natural
justification, there are
other interesting oracle models, to which our arguments will not
apply.  For example, if we think of the oracle $M_f$ as a black box supplied
by a third party, then we should not assume that $(M_f)^{-1}$ can easily be
constructed from $M_f$, as we know no way of efficiently reversing the
operation of an unknown physical evolution.

Remaining within the circuit model, we now show that
$M_f$ and $S_f$ are not (even up to constant factors) equivalent.
In fact, simulating $M_f$ requires exponentially many uses of $S_f$.

First, consider the standard oracle $S_{f^{-1}}$ which maps a basis
state $|y\rangle |b \rangle$ to $|y\rangle |b \oplus f^{-1}
(y)\rangle$.  Since $S_{f^{-1}} : |y\rangle |0 \rangle \rightarrow
|y\rangle | f^{-1}(y)\rangle$, simulating it allows us to solve the
search problem of identifying $|f^{-1}(y)\rangle$ from a database of
$N$ elements.  It is known that, using Grover's search algorithm, one
can simulate $S_{f^{-1}}$ with $O(\sqrt{N})$ invocations of $S_f$
\cite{BHT98,BHMT00}. In the following we explain one possible way of
doing that.

Prepare the state $|y\rangle|0\rangle|0\rangle|0\rangle$, where the
first three registers consist of $n$ qubits and the last register is a
single qubit. Apply Hadamard transformations on the second register to
get $|\phi_1 \rangle = |y\rangle\sum_{x \in
Z_N}|x\rangle|0\rangle|0\rangle \mbox{.}$ Invoking $S_f$ on the second
and third registers now gives $$ |y\rangle( \sum_{x \in
Z_N}|x\rangle|f(x)\rangle ) |0\rangle \mbox{.}$$ Using CNOT gates,
compare the first and third registers and put the result in the
fourth, obtaining
$$ \Big(|y\rangle\sum_{x \in Z_N , x \ne
f^{-1}(y)}|x\rangle|f(x)\rangle|0\rangle\Big)+
\Big(|y\rangle|f^{-1}(y)\rangle|y\rangle|1\rangle\Big) \mbox{.}$$
Now
apply $( S_f )^{-1}$ on the second and third registers, obtaining
$$
\Big(|y\rangle\sum_{x \in Z_N , x \ne
  f^{-1}(y)}|x\rangle|0\rangle|0\rangle \Big) +
\Big(|y\rangle|f^{-1}(y)\rangle|0\rangle|1\rangle \Big) \mbox{.}
$$
Taken together, these operations leave the first and third registers
unchanged, while their action on the second and fourth defines an
oracle for the search problem. Applying Grover's
algorithm\cite{Grover96} to this oracle, we obtain the state
$|y\rangle|f^{-1}(y)\rangle$ after $O(\sqrt{N})$ invocations.


{\bf Lemma 1} \qquad To simulate the inverse oracle $S_{f^{-1}}$ with
a quantum network using oracles $S_f$ and $(S_f )^{-1}$, a total
number of $\Theta(\sqrt{N})$ invocations of $S_f$ are necessary.

\textbf{Proof} The upper bound of $O(\sqrt{N})$ is implied by the
Grover-based algorithm just discussed. Ambainis \cite{Ambainis00} has
shown that $\Omega(\sqrt{N})$ invocations of the standard oracle $S_f$
are required to invert a general permutation $f$. \qed
\vskip5pt

Given $S_f$ and $S_{f^{-1}}$, Bennett has shown how to simulate $M_f$
within classical reversible computation \cite{Bennett73}. Using a
quantum version of this construction, we can establish our main
result: \vskip5pt {\bf Lemma 2} \qquad To simulate the minimal oracle
$M_f$ with a quantum network using oracles $S_f$ and $(S_f )^{-1}$, a
total number of $\Theta(\sqrt{N})$ invocations of $S_f$ are necessary.

\textbf{Proof} Given $S_f$ and $S_{f^{-1}}$, we can simulate $M_f$ as
follows:
$$
M_f  \otimes I = ( S_{f^{-1}} )^{-1} \circ X \circ S_f \, ,
$$
where the swap gate $X$ is defined by $ X: \ket{a} \otimes \ket{b}
\rightarrow \ket{b} \otimes \ket{a}$.  From Lemma $1$, $S_{f^{-1}}$
needs $\Theta(\sqrt{N})$ invocations of $S_f$ and $(S_f
)^{-1}$. Therefore we get the upper bound of $O(\sqrt{N})$ for
simulation of $M_f$.

However this is the optimal simulation.  For suppose there is a
network which simulates $M_f$ with less than $\Omega( \sqrt{N} )$
queries. The reversed network simulates $M_{f^{-1}}$. From these two,
by our earlier results, we can construct a network that simulates
$S_{f^{-1}}$ with fewer than $\Omega ( \sqrt{N} ) $ queries, which
contradicts Lemma $1$. \qed \vskip5pt

It is worth remarking that we could equally well have carried
through our discussion using variants of $S_f$ and $P_f$,
such as the bitwise acting versions:
\begin{itemize}
\item the {\it bit string standard} oracle,
$
S^{\rm bit}_f : |{\bf x}\rangle | \bf{b} \rangle \rightarrow
|\bf{x} \rangle |\bf{b} \oplus
\bf{f(x)} \rangle $.
\item   the {\it bit string phase} oracle,
$P^{\rm bit}_f : |{\bf x}\rangle |{\bf b}\rangle
\rightarrow e^{2\pi i {\bf f(x) \cdot b } / 2 }|{\bf x}\rangle |{\bf b}
\rangle$.
\end{itemize}
Here $\bf{b} \oplus \bf{x}$ denotes the bitwise sum mod $2$ of the strings
$\bf{b}$ and $\bf{x}$, and ${\bf b \cdot x}$ their inner product mod $2$.
Again, $S^{\rm bit}_f$ and $P^{\rm bit}_f$ are equivalent:
writing
$$ {\cal F} = H \otimes H \otimes \cdots \otimes H \, ,$$
for the tensor product of $n$ Hadamard operators acting on register qubits,
we have
\begin{eqnarray*}
&(& I \otimes {\cal F} ) \circ S^{\rm bit}_f \circ
 (I \otimes {\cal F}^{-1} ) = P^{\rm bit}_f \, ,
 \\
&(& I \otimes {\cal F}^{-1} ) \circ
 P^{\rm bit}_f \circ (I \otimes {\cal F})
 = S^{\rm bit}_f \, .
\end{eqnarray*}
Note also that
$S^{\rm bit}_f = (S^{\rm bit}_f )^{-1}$,
$P^{\rm bit}_f = (P^{\rm bit}_f )^{-1}$.
Our results still apply: $S^{\rm bit}_f$ has essentially
the same relation to $M_f$ that $S_f$ does.

In summary, constructing a minimal oracle requires exponentially many
invocations of a standard oracle.  We can thus indeed definitively
exclude the possibility of efficiently solving NAGI by simulating
$M_f$ using $S_f$, which motivated our discussion. We have not,
however, been able to exclude the possibility of directly constructing
a polynomial size network defining an $M_f$ oracle for any given $1-1$
function $f$, which would lead to a polynomial time solution of
NAGI.

\noindent {\em Acknowledgments}.  We thank Charles Bennett for helpful discussions and
for drawing our attention to Refs. \cite{Bennett73}, and Richard Jozsa for helpful
comments. E. K. thanks Mike Mosca for useful discussions and Waterloo University for
hospitality.  This work was supported by EPSRC and by the European projects EQUIP,
QAIP and QUIPROCONE.

%\bibliographystyle{plain}
%\bibliography{All}

\begin{thebibliography}{10}

\bibitem{Deutsch85}
D.~Deutsch, Proc. Royal Society of London A, {\bf 400}, 97 (1985).

\bibitem{Shor94}
P.W.~Shor, SIAM J. Comp., {\bf 26}, 1484 (1997).

\bibitem{Grover96}
L.K.~Grover, Proc. 28th ACM Symp. Theor. Comp., 212 (1996).

\bibitem{BBBV97} C.~Bennett, E.~Bernstein, G.~Brassard, and
U.~Vazirani, SIAM J. Comp., {\bf 26}, 1510 (1997).

\bibitem{BBCMW98} R.~Beals, H.~Buhrman, R.~Cleve, M.~Mosca, and
R.~de~Wolf, Proc. 39th Symp. Found.  Comp. Sci., 352 (1998).

\bibitem{vanDam98}
W.~van Dam, Proc. 39th Symp. Found. Comp. Sci., 362 (1998).

\bibitem{Cleve99} R.~Cleve, in C.~Macchiavello, G.M. Palma, and
A.~Zeilinger, editors, {\em Collected Papers on Quantum Computation
and Quantum Information Theory}, (World Scientific, 1999).

\bibitem{BCWW01}
H.~Buhrman, R.~Cleve, J.~Watrous, and R.~de~Wolf, quant-ph/0102001, 2001.

\bibitem{Aaronson01}
After this work was circulated, a non-trivial lower

bound was given by S. Aaronson quant-ph/0111102.

\bibitem{BHT98} G.~Brassard, P.~H{\o}yer, and A.~Tapp, 3rd Latin
American Theor. Info. Symp., {\bf 1380}, 163 (1998).

\bibitem{BHMT00} G.~Brassard, P.~H{\o}yer, M.~Mosca, and A.~Tapp, to
appear in Quantum Computation \& Quantum Information Science, AMS
Contemporary Math Series, quant-ph/0005055, 2001.

\bibitem{Ambainis00}
A.~Ambainis, Proc. 32th ACM Symp. Theor. Comp., 636 (2000).

\bibitem{Bennett73}
C. Bennett, IBM J. Res. Dev., {\bf 17}, 525 (1973).


\end{thebibliography}
\end{multicols}
\end{document}


pstricks.tex
%% BEGIN: pstricks.tex
%%
%% PostScript macros for Generic TeX: main input file for PSTricks 97.
%% See the PSTricks User's Guide for description.
%% This uses the header file `pstricks.pro'.
%%
\def\fileversion{97 patch 10}
\def\filedate{1999/03/24}
%%
%% COPYRIGHT 1993, 1994, 1999 by Timothy Van Zandt, tvz@nwu.edu.
%%
%% This program can be redistributed and/or modified under the terms
%% of the LaTeX Project Public License Distributed from CTAN
%% archives in directory macros/latex/base/lppl.txt.
%%
\csname PSTricksLoaded\endcsname
\let\PSTricksLoaded\endinput
\edef\PstAtCode{\the\catcode`\@}
\catcode`\@=11\relax
\expandafter\ifx\csname @latexerr\endcsname\relax
\long\def\@ifundefined#1#2#3{\expandafter\ifx\csname
#1\endcsname\relax#2\else#3\fi}
\def\@namedef#1{\expandafter\def\csname #1\endcsname}
\def\@nameuse#1{\csname #1\endcsname}
\def\@eha{%
Your command was ignored.^^J
Type \space I <command> <return> \space to replace
it with another command,^^J
or \space <return> \space to continue without it.}
\def\@spaces{\space\space\space\space}
\def\typeout#1{\immediate\write\@unused{#1}}
\alloc@7\write\chardef\sixt@@n\@unused
\def\@empty{}
\def\@gobble#1{}
\def\@nnil{\@nil}
\def\@ifnextchar#1#2#3{%
\let\@tempe#1\def\@tempa{#2}\def\@tempb{#3}\futurelet\@tempc\@ifnch}
\def\@ifnch{%
\ifx\@tempc\@sptoken
\let\@tempd\@xifnch
\else
\ifx\@tempc\@tempe \let\@tempd\@tempa \else \let\@tempd\@tempb \fi
\fi
\@tempd}
\begingroup
\def\:{\global\let\@sptoken= } \:
\def\:{\@xifnch} \expandafter\gdef\: {\futurelet\@tempc\@ifnch}
\endgroup
\fi
\typeout{`PSTricks' v\fileversion\space\space <\filedate> (tvz)}
\def\@pstrickserr#1#2{%
\begingroup
\newlinechar`\^^J
\edef\pst@tempc{#2}%
\expandafter\errhelp\expandafter{\pst@tempc}%
\typeout{%
PSTricks error. \space See User's Guide for further information.^^J
\@spaces\@spaces\@spaces\@spaces
Type \space H <return> \space for immediate help.}%
\errmessage{#1}%
\endgroup}
\def\@ehpa{%
Your command was ignored. Default value substituted.^^J
Type \space <return> \space to procede.}
\def\@ehpb{%
Your command was ignored. Will recover best I can.^^J
Type \space <return> \space to procede.}
\def\@ehpc{%
You better fix this before proceding.^^J
See the PSTricks User's Guide or ask your system administrator for help.^^J
Type \space X <return> \space to quit.}
\def\pst@misplaced#1{\@pstrickserr{Misplaced \string#1 command}\@ehpb}
\newdimen\pst@dima
\newdimen\pst@dimb
\newdimen\pst@dimc
\newdimen\pst@dimd
\newdimen\pst@dimg
\newdimen\pst@dimh
\newbox\pst@hbox
\newbox\pst@boxg
\newcount\pst@cnta
\newcount\pst@cntb
\newcount\pst@cntc
\newcount\pst@cntd
\newcount\pst@cntg
\newcount\pst@cnth
\newif\if@pst
\newtoks\pst@toks
\newif\if@star
\def\pst@ifstar#1{%
\@ifnextchar*{\@startrue\def\next*{#1}\next}{\@starfalse#1}}
\def\pst@expandafter#1#2{%
\def\next{#1}%
\edef\@tempa{#2}%
\ifx\@tempa\@empty
\@pstrickserr{Unexpected empty argument!}\@ehpb
\def\@tempa{\@empty}%
\fi
\expandafter\next\@tempa}
\def\pst@dimtonum#1#2{\edef#2{\pst@@dimtonum#1}}
\def\pst@@dimtonum#1{\expandafter\pst@@@dimtonum\the#1}
{\catcode`\p=12 \catcode`\t=12 \global\@namedef{pst@@@dimtonum}#1pt{#1}}
\def\pst@pyth#1#2#3{%
\ifdim#1>#2\pst@@pyth#1#2#3\else\pst@@pyth#2#1#3\fi}
\def\pst@@pyth#1#2#3{%
\ifdim4#1>9#2%
#3=#1\advance#3 .2122#2%
\else
#3=.8384#1\advance#3 .5758#2%
\fi}
\def\pst@divide#1#2#3{%
\pst@@divide{#1}{#2}%
\pst@dimtonum\pst@dimg{#3}}
\def\pst@@divide#1#2{%
\pst@dimg=#1\relax
\pst@dimh=#2\relax
\pst@cntg=\pst@dimh
\pst@cnth=67108863
\pst@@@divide\pst@@@divide\pst@@@divide\pst@@@divide
\divide\pst@dimg\pst@cntg}
\def\pst@@@divide{%
\ifnum
\ifnum\pst@dimg<\z@-\fi\pst@dimg<\pst@cnth
\multiply\pst@dimg\sixt@@n
\else
\divide\pst@cntg\sixt@@n
\fi}
\def\pst@configerr#1{%
\@pstrickserr{\string#1 not defined in pstricks.con}\@ehpc}
% % \begin{macrocode}
\def\pstVerb#1{\pst@configerr\pstVerb}
\def\pstverb#1{\pst@configerr\pstverb}
\def\pstverbscale{\pst@configerr\pstverbscale}
\def\pstrotate{\pst@configerr\pstrotate}
\def\pstheader#1{\pst@configerr\pstheader}
\def\pstdriver{\pst@configerr\pstdriver}
\@ifundefined{pstcustomize}%
{\def\pstcustomize{\endinput\let\pstcustomize\relax}}{}
\input pstricks.con
\newif\ifPSTricks
\PSTrickstrue
\def\PSTricksOff{%
\def\pstheader##1{}%
\def\pstverb##1{}%
\def\pstVerb##1{}%
\PSTricksfalse}
\@ifundefined{pst@def}{\def\pst@def#1<#2>{\@namedef{tx@#1}{#2 }}}{}
\@ifundefined{pst@ATH}{\def\pst@ATH<#1>{}}{}
\pstheader{pstricks.pro}
\def\pst@dict{tx@Dict begin }
\def\pst@theheaders{pstricks.pro}
\def\pst@Verb#1{\pstVerb{\pst@dict #1 end}}
\def\tx@Atan{Atan }
\def\tx@Div{Div }
\def\tx@NET{NET }
\def\tx@Pyth{Pyth }
\def\tx@PtoC{PtoC }
\def\tx@PathLength@{PathLength@ }
\def\tx@PathLength{PathLength }
\pst@dimg=\pstunit\relax
\ifdim\pst@dimg=1bp
\def\pst@stp{.996264 dup scale}
\else
\edef\pst@stp{1 \pst@@dimtonum\pst@dimg\space div dup scale}
\fi
\def\tx@STP{STP }
\def\tx@STV{STV }
\def\pst@number#1{\pst@@dimtonum#1\space}
\def\pst@checknum#1#2{%
\edef\next{#1}%
\ifx\next\@empty
\let\pst@num\z@
\else
\expandafter\pst@@checknum\next..\@nil
\fi
\ifnum\pst@num=\z@
\@pstrickserr{Bad number: `#1'. 0 substituted.}\@ehpa
\def#2{0 }%
\else
\edef#2{\ifnum\pst@num=\tw@-\fi\the\pst@cntg.%
\expandafter\@gobble\the\pst@cnth\space}%
\fi}
\def\pst@@checknum{%
\@ifnextchar-%
{\let\pst@num\tw@\expandafter\pst@@@checknum\@gobble}%
{\let\pst@num\@ne\pst@@@checknum}}
\def\pst@@@checknum#1.#2.#3\@nil{%
\afterassignment\pst@@@@checknum\pst@cntg=0#1\relax\@nil
\afterassignment\pst@@@@checknum\pst@cnth=1#2\relax\@nil}
\def\pst@@@@checknum#1\relax\@nil{%
\ifx\@nil#1\@nil\else\let\pst@num\z@\fi}
\def\pst@getnumii#1 #2 #3\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph}
\def\pst@getnumiii#1 #2 #3 #4\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph
\pst@checknum{#3}\pst@tempi}
\def\pst@getnumiv#1 #2 #3 #4 #5\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph
\pst@checknum{#3}\pst@tempi
\pst@checknum{#4}\pst@tempj}
\def\pst@getdimnum#1 #2 #3\@nil{%
\pssetlength\pst@dimg{#1}%
\pst@checknum{#2}\pst@tempg}
% DG/SR modification begin - Jan. 7, 1998 - Patch 9
% Missing from pstricks.bug 0.93
%\def\pst@getscale#1#2{%
%\pst@expandafter\pst@getnumii{#1 #1} {} {} {}\@nil
%\@psttrue
%\ifdim\pst@tempg\p@=\z@
%\@pstrickserr{Bad scaling argument `#1'}\@ehpa
%\def\pst@tempg{1 }%
%\@pstfalse
%\fi
%\ifdim\pst@temph\p@=\z@
%\if@pst\@pstrickserr{Bad scaling argument `#1'}\@ehpa\fi
%\def\pst@temph{1 }%
%\fi
%\edef#2{\pst@tempg\space \pst@temph\space scale }%
%\ifdim\pst@tempg\p@=\p@ \ifdim\pst@temph\p@=\p@
%\def#2{}%
%\fi\fi}
\def\pst@getscale#1#2{%
\edef\pst@tempg{#1}%
\ifx\pst@tempg\@none
\def#2{}%
\else
\pst@expandafter\pst@getnumii{#1 #1} {} {} {}\@nil
\ifdim\pst@tempg\p@=\z@
\@pstrickserr{Bad scaling argument `#1'}\@ehpa
\def#2{}%
\else
\ifdim\pst@temph\p@=\z@
\@pstrickserr{Bad scaling argument `#1'}\@ehpa
\def#2{}%
\else
\edef#2{\pst@tempg\space \pst@temph\space scale }%
\fi
\fi
\fi}
% DG/SR modification end
\def\pst@getint#1#2{%
\pst@cntg=#1\relax
\edef#2{\the\pst@cntg\space}}
\begingroup
\catcode`\{=12
\catcode`\}=12
\catcode`\[=1
\catcode`\]=2
\gdef\pslbrace[{ ]
\gdef\psrbrace[} ]
\endgroup
\def\@newcolor#1#2{%
\expandafter\edef\csname #1\endcsname{\noexpand\pst@color{#2}}%
\expandafter\edef\csname color@#1\endcsname{#2}%
\ignorespaces}
\def\pst@color#1{%
\def\pst@currentcolor{#1}\pstVerb{#1}\aftergroup\pst@endcolor}
\def\pst@endcolor{\pstVerb{\pst@currentcolor}}
\def\pst@currentcolor{0 setgray}
\def\altcolormode{%
\def\pst@color##1{%
\pstVerb{gsave ##1}\aftergroup\pst@endcolor}%
\def\pst@endcolor{\pstVerb{\pst@grestore}}}
\def\pst@grestore{%
currentpoint
matrix currentmatrix
currentfont
grestore
setfont
setmatrix
moveto}
\def\pst@usecolor#1{\csname color@#1\endcsname\space}
\def\newgray#1#2{%
\pst@checknum{#2}\pst@tempg
\@newcolor{#1}{\pst@tempg setgray}}
\def\newrgbcolor#1#2{%
\pst@expandafter\pst@getnumiii{#2} {} {} {} {}\@nil
\@newcolor{#1}{\pst@tempg \pst@temph \pst@tempi setrgbcolor}}
\def\newhsbcolor#1#2{%
\pst@expandafter\pst@getnumiii{#2} {} {} {} {}\@nil
\@newcolor{#1}{\pst@tempg \pst@temph \pst@tempi sethsbcolor}}
\def\newcmykcolor#1#2{%
\pst@expandafter\pst@getnumiv{#2} {} {} {} {} {}\@nil
\@newcolor{#1}{\pst@tempg \pst@temph \pst@tempi \pst@tempj setcmykcolor}}
\newgray{black}{0}
\newgray{darkgray}{.25}
\newgray{gray}{.5}
\newgray{lightgray}{.75}
\newgray{white}{1}
\newrgbcolor{red}{1 0 0}
\newrgbcolor{green}{0 1 0}
\newrgbcolor{blue}{0 0 1}
\newrgbcolor{yellow}{1 1 0}
\newrgbcolor{cyan}{0 1 1}
\newrgbcolor{magenta}{1 0 1}
\def\psset#1{\@psset#1,\@nil\ignorespaces}
\def\@psset#1,{%
\@@psset#1==\@nil
\@ifnextchar\@nil{\@gobble}{\@psset}}
\def\@@psset#1=#2=#3\@nil{%
\@ifundefined{psset@#1}%
{\@pstrickserr{Graphics parameter `#1' not defined.}\@ehpa}%
{\@nameuse{psset@#1}{#2}}}%
\def\psset@style#1{%
\@ifundefined{pscs@#1}%
{\@pstrickserr{Custom style `#1' undefined}\@ehpa}%
{\@nameuse{pscs@#1}}}
\def\newpsstyle#1#2{\@namedef{pscs@#1}{\psset{#2}}}
\def\@none{none}
\def\pst@getcolor#1#2{%
\@ifundefined{color@#1}%
{\@pstrickserr{Color `#1' not defined}\@eha}%
{\edef#2{#1}}}
\newdimen\psunit \psunit 1cm
\newdimen\psxunit \psxunit 1cm
\newdimen\psyunit \psyunit 1cm
\let\psrunit\psunit
\def\pstunit@off{\let\@psunit\ignorespaces\ignorespaces}
\def\pssetlength#1#2{%
\let\@psunit\psunit
\afterassignment\pstunit@off
#1 #2\@psunit}
\def\psaddtolength#1#2{%
\let\@psunit\psunit
\afterassignment\pstunit@off
\advance#1 #2\@psunit}
\def\pssetxlength#1#2{%
\let\@psunit\psxunit
\afterassignment\pstunit@off
#1 #2\@psunit}
\def\pssetylength#1#2{%
\let\@psunit\psyunit
\afterassignment\pstunit@off
#1 #2\@psunit}
\def\psset@unit#1{%
\pssetlength\psunit{#1}%
\psxunit=\psunit
\psyunit=\psunit}
\def\psset@runit#1{\pssetlength\psrunit{#1}}
\def\psset@xunit#1{\pssetxlength\psxunit{#1}}
\def\psset@yunit#1{\pssetylength\psyunit{#1}}
\def\pst@getlength#1#2{%
\pssetlength\pst@dimg{#1}%
\edef#2{\pst@number\pst@dimg}}
\def\pst@@getlength#1#2{%
\pssetlength\pst@dimg{#1}%
\edef#2{\number\pst@dimg sp}}
\def\pst@getcoor#1#2{\pst@@getcoor{#1}\let#2\pst@coor}
\def\pst@coor{0 0 }
\def\pst@getcoors#1#2{%
\def\pst@aftercoors{\addto@pscode{#1 \pst@coors }#2}%
\def\pst@coors{}%
\pst@@getcoors}
\def\pst@@getcoors(#1){%
\pst@@getcoor{#1}%
\edef\pst@coors{\pst@coor\pst@coors}%
\@ifnextchar({\pst@@getcoors}{\pst@aftercoors}}
\def\pst@getangle#1#2{\pst@@getangle{#1}\let#2\pst@angle}
\def\pst@angle{0 }
\def\cartesian@coor#1,#2,#3\@nil{%
\pssetxlength\pst@dimg{#1}%
\pssetylength\pst@dimh{#2}%
\edef\pst@coor{\pst@number\pst@dimg \pst@number\pst@dimh}}
\def\NormalCoor{%
\def\pst@@getcoor##1{\pst@expandafter\cartesian@coor{##1},\relax,\@nil}%
\def\pst@@getangle##1{%
\pst@checknum{##1}\pst@angle
\edef\pst@angle{\pst@angle \pst@angleunit}}%
\def\psput@##1{\pst@@getcoor{##1}\leavevmode\psput@cartesian}}
\NormalCoor
\def\degrees{\@ifnextchar[{\@degrees}{\def\pst@angleunit{}}}
\def\@degrees[#1]{%
\pst@checknum{#1}\pst@tempg
\edef\pst@angleunit{360 \pst@tempg div mul }%
\ignorespaces}
\def\radians{\def\pst@angleunit{57.2956 mul }}
\def\pst@angleunit{}
\def\SpecialCoor{%
\def\pst@@getcoor##1{%
\begingroup
\pst@activecoor
\xdef\pst@tempg{##1}%
\endgroup
\expandafter\special@coor\pst@tempg||\@nil}%
\def\pst@@getangle##1{%
\begingroup
\pst@activecoor
\xdef\pst@tempg{##1}%
\endgroup
\expandafter\special@angle\pst@tempg\@empty)\@nil}%
\def\psput@##1{\pst@@getcoor{##1}\leavevmode\psput@special}}
\begingroup
\catcode`\|=13
\catcode`\;=13
\catcode`\!=13
\gdef\pst@activecoor{%
\def|{\string|}%
\def;{\string;}%
\def!{\string!}}
\endgroup
\def\special@coor#1|#2|#3\@nil{%
\ifx#3|\relax
\mixed@coor{#1}{#2}%
\else
\special@@coor#1;;\@nil
\fi}
\def\special@@coor#1{%
\ifcat#1a\relax
\def\next{\node@coor#1}%
\else
\ifx#1[\relax
\def\next{\Node@coor[}%
\else
\ifx#1!\relax
\def\next{\raw@coor}%
\else
\def\next{\special@@@coor#1}%
\fi
\fi
\fi
\next}
\def\special@@@coor#1;#2;#3\@nil{%
\ifx#3;\relax
\polar@coor{#1}{#2}%
\else
\cartesian@coor#1,\relax,\@nil
\fi}
\def\mixed@coor#1#2{%
\begingroup
% DG/SR modification begin - Oct. 27, 1997 - Patch 6
%\specialcoor@ii#1;;\@nil
%\let\pst@tempa\pst@coor
%\specialcoor@ii#2;;\@nil
\special@@coor#1;;\@nil
\let\pst@tempa\pst@coor
\special@@coor#2;;\@nil
% DG/SR modification end
\xdef\pst@tempg{\pst@tempa pop \pst@coor exch pop }%
\endgroup
\let\pst@coor\pst@tempg}
\def\polar@coor#1#2{%
\pssetlength\pst@dimg{#1}%
\pst@@getangle{#2}%
\edef\pst@coor{\pst@number\pst@dimg \pst@angle \tx@PtoC}}
\def\raw@coor#1;#2\@nil{%
\edef\pst@coor{%
#1 \pst@number\psyunit mul exch \pst@number\psxunit mul exch }}
\def\node@coor#1\@nil{%
\@pstrickserr{You must load `pst-node.tex' to use node coordinates.}\@ehps
\def\pst@coor{0 0 }}
\def\Node@coor{\node@coor}
\def\special@angle#1#2)#3\@nil{%
\ifx!#1\relax
\edef\pst@angle{#2 \pst@angleunit}%
\else
\ifx(#1\relax
\pst@@getcoor{#2}%
\edef\pst@angle{\pst@coor exch \tx@Atan}%
\else
\pst@checknum{#1#2}\pst@angle
\edef\pst@angle{\pst@angle \pst@angleunit}%
\fi
\fi}
\def\Cartesian{%
\def\cartesian@coor##1,##2,##3\@nil{%
\pssetxlength\pst@dimg{##1}%
\pssetylength\pst@dimh{##2}%
\edef\pst@coor{\pst@number\pst@dimg \pst@number\pst@dimh}}%
\@ifnextchar({\Cartesian@}{}}
\def\Cartesian@(#1,#2){%
\pssetxlength\psxunit{#1}%
\pssetylength\psyunit{#2}%
\ignorespaces}
\def\Polar{%
\def\psput@cartesian{\psput@special}%
\def\cartesian@coor##1,##2,##3\@nil{\polar@coor{##1}{##2}}}%
\def\psset@origin#1{%
\pst@@getcoor{#1}%
\edef\psk@origin{\pst@coor \tx@NET }}
\def\psk@origin{}
\newif\ifswapaxes
\def\psset@swapaxes#1{%
\@nameuse{@pst#1}%
\if@pst
\def\psk@swapaxes{-90 rotate -1 1 scale }%
\else
\def\psk@swapaxes{}%
\fi}
\psset@swapaxes{false}
\newif\ifshowpoints
\def\psset@showpoints#1{\@nameuse{showpoints#1}}
\psset@showpoints{false}
\let\pst@setrepeatarrowsflag\relax
\def\psset@border#1{%
\pst@getlength{#1}\psk@border
\pst@setrepeatarrowsflag}
\psset@border{0pt}
\def\psset@bordercolor#1{\pst@getcolor{#1}\psbordercolor}
\psset@bordercolor{white}
\newif\ifpsdoubleline
\def\psset@doubleline#1{%
\@nameuse{psdoubleline#1}%
\pst@setrepeatarrowsflag}
\psset@doubleline{false}
\def\psset@doublesep#1{\def\psdoublesep{#1}}
\psset@doublesep{1.25\pslinewidth}
\def\psset@doublecolor#1{\pst@getcolor{#1}\psdoublecolor}
\psset@doublecolor{white}
\newif\ifpsshadow
\def\psset@shadow#1{%
\@nameuse{psshadow#1}%
\pst@setrepeatarrowsflag}
\psset@shadow{false}
\def\psset@shadowsize#1{\pst@getlength{#1}\psk@shadowsize}
\psset@shadowsize{3pt}
\def\psset@shadowangle#1{\pst@getangle{#1}\psk@shadowangle}
\psset@shadowangle{-45}
\def\psset@shadowcolor#1{\pst@getcolor{#1}\psshadowcolor}
\psset@shadowcolor{darkgray}
\def\pst@repeatarrowsflag{\z@}
\def\pst@setrepeatarrowsflag{%
\edef\pst@repeatarrowsflag{%
\ifdim\psk@border\p@>\z@ 1\else\ifpsdoubleline 1\else
\ifpsshadow 1\else \z@\fi\fi\fi}}
\def\psls@none{}
\newdimen\pslinewidth
\def\psset@linewidth#1{\pssetlength\pslinewidth{#1}}
\psset@linewidth{.8pt}
\def\psset@linecolor#1{\pst@getcolor{#1}\pslinecolor}
\psset@linecolor{black}
\def\psls@solid{0 setlinecap stroke }
\def\pst@missing{%
\z@
\@pstrickserr{Missing number or dimension. 0 substituted}\@ehpa}
\def\psset@dash#1{%
\pst@expandafter\psset@@dash{#1} {\pst@missing} {\pst@missing} {}\@nil
\edef\psk@dash{\pst@number\pst@dimg \pst@number\pst@dimh}}
\def\psset@@dash#1 #2 #3\@nil{%
\pssetlength\pst@dimg{#1}%
\pssetlength\pst@dimh{#2}}
\psset@dash{5pt 3pt}
\newif\ifpsdashadjust
\def\psset@dashadjust#1{\@nameuse{psdashadjust#1}}
\psset@dashadjust{true}
\def\psls@dashed{%
\ifpsdashadjust
\psk@dash \pst@linetype\space \tx@DashLine
\else
[ \psk@dash ] 0 setdash stroke
\fi}
\def\tx@DashLine{DashLine }
\def\psset@dotsep#1{\pst@getlength{#1}\psk@dotsep}
\psset@dotsep{3pt}
\def\psls@dotted{%
\ifpsdashadjust
\psk@dotsep \pst@linetype\space \tx@DotLine
\else
[ 0 \psk@dotsep CLW add ] 0 setdash 1 setlinecap stroke
\fi}
\def\tx@DotLine{DotLine }
\def\psset@linestyle#1{%
\@ifundefined{psls@#1}%
{\@pstrickserr{Line style `#1' not defined}\@eha}%
{\edef\pslinestyle{#1}}}
\psset@linestyle{solid}
\def\psfs@none{}
\def\psset@fillcolor#1{\pst@getcolor{#1}\psfillcolor}
\psset@fillcolor{white}
\def\psfs@solid{\pst@fill{\pst@usecolor\psfillcolor fill}}
\def\psset@hatchwidth#1{\pst@getlength{#1}\psk@hatchwidth}
\psset@hatchwidth{.8pt}
\def\psset@hatchsep#1{\pst@getlength{#1}\psk@hatchsep}
\psset@hatchsep{4pt}
\def\psset@hatchcolor#1{\pst@getcolor{#1}\pshatchcolor}
\psset@hatchcolor{black}
\def\psset@hatchangle#1{\pst@getangle{#1}\psk@hatchangle}
\psset@hatchangle{45}
\def\pst@linefill{%
\psk@hatchangle rotate
\psk@hatchwidth SLW
\pst@usecolor\pshatchcolor
\psk@hatchsep \tx@LineFill}
\def\psfs@vlines{\pst@fill\pst@linefill}
\@namedef{psfs@vlines*}{\psfs@solid \psfs@vlines}
\def\psfs@hlines{\pst@fill{90 rotate \pst@linefill}}
\@namedef{psfs@hlines*}{\psfs@solid \psfs@hlines}
\def\psfs@crosshatch{\psfs@vlines \psfs@hlines}
\@namedef{psfs@crosshatch*}{\psfs@solid \psfs@vlines \psfs@hlines}
\def\tx@LineFill{LineFill }
\def\psset@fillstyle#1{%
\edef\pst@tempg{#1}\def\pst@temph{none}%
\ifx\pst@tempg\pst@temph
\let\psk@fillstyle\relax
\else
\@ifundefined{psfs@#1}%
{\@pstrickserr{Undefined fill style: `#1'}\@eha}%
{\edef\psk@fillstyle{\expandafter\noexpand\csname psfs@#1\endcsname}}%
\fi}
\def\psset@addfillstyle#1{%
\@ifundefined{psfs@#1}%
{\@pstrickserr{Undefined fill style: `#1'}\@eha}%
{\edef\psk@fillstyle{%
\expandafter\noexpand\psk@fillstyle
\expandafter\noexpand\csname psfs@#1\endcsname}}}
\psset@fillstyle{none}
\def\psset@arrows#1{%
\begingroup
\pst@activearrows
\xdef\pst@tempg{#1}%
\endgroup
\expandafter\psset@@arrows\pst@tempg\@empty-\@empty\@nil
\if@pst\else
\@pstrickserr{Bad arrows specification: #1}\@ehpa
\fi}
\def\psset@@arrows#1-#2\@empty#3\@nil{%
\@psttrue
\def\next##1,#1-##2,##3\@nil{\def\pst@tempg{##2}}%
\expandafter\next\pst@arrowtable,#1-#1,\@nil
\@ifundefined{psas@\pst@tempg}%
{\@pstfalse\def\psk@arrowA{}}%
{\let\psk@arrowA\pst@tempg}%
\@ifundefined{psas@#2}%
{\@pstfalse\def\psk@arrowB{}}%
{\def\psk@arrowB{#2}}}
\def\psk@arrowA{}
\def\psk@arrowB{}
\def\pst@arrowtable{,<->,<<->>,>-<,>>-<<,(-),[-]}
\begingroup
\catcode`\<=13
\catcode`\>=13
\catcode`\|=13
\gdef\pst@activearrows{\def<{\string<}\def>{\string>}\def|{\string|}}
\endgroup
\def\tx@BeginArrow{BeginArrow }
\def\tx@EndArrow{EndArrow }
\def\psset@arrowscale#1{\pst@getscale{#1}\psk@arrowscale}
\psset@arrowscale{1}
\def\psset@arrowsize#1{%
\pst@expandafter\pst@getdimnum{#1} 0 {} {}\@nil
\edef\psk@arrowsize{\pst@number\pst@dimg \pst@tempg}}
\psset@arrowsize{1.5pt 2}
\def\psset@arrowlength#1{\pst@checknum{#1}\psk@arrowlength}
\psset@arrowlength{1.4}
\def\psset@arrowinset#1{\pst@checknum{#1}\psk@arrowinset}%
\psset@arrowinset{.4}
\def\tx@Arrow{Arrow }
\@namedef{psas@>}{%
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\@namedef{psas@>>}{%
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow
0 h T
gsave
newpath
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow
CP
grestore
CP newpath moveto
2 copy
L
stroke
moveto}
\@namedef{psas@<}{%
true \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\@namedef{psas@<<}{%
true \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow
CP newpath moveto 0 a neg L stroke 0 h neg T
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\def\psset@tbarsize#1{%
\pst@expandafter\pst@getdimnum{#1} 0 {} {}\@nil
\edef\psk@tbarsize{\pst@number\pst@dimg \pst@tempg}}
\psset@tbarsize{2pt 5}
\def\tx@Tbar{Tbar }
\@namedef{psas@|}{\psk@tbarsize \tx@Tbar}
\@namedef{psas@|*}{0 CLW -2 div T \psk@tbarsize \tx@Tbar}
\@namedef{psas@>|}{%
\psk@tbarsize \tx@Tbar
0 CLW 2 div T
newpath
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\@namedef{psas@>|*}{%
0 CLW -2 div T
\psk@tbarsize \tx@Tbar
0 CLW 2 div T
newpath
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\edef\pst@arrowtable{\pst@arrowtable,|<*->|*,|<->|}
\def\psset@bracketlength#1{\pst@checknum{#1}\psk@bracketlength}
\psset@bracketlength{.15}
\def\tx@Bracket{Bracket }
\@namedef{psas@]}{\psk@bracketlength \psk@tbarsize \tx@Bracket}
\def\psset@rbracketlength#1{\pst@checknum{#1}\psk@rbracketlength}
\psset@rbracketlength{.15}
\def\tx@RoundBracket{RoundBracket }
\@namedef{psas@)}{\psk@rbracketlength \psk@tbarsize \tx@RoundBracket}
\def\psas@c{1 \psas@@c}
\def\psas@cc{0 CLW 2 div T 1 \psas@@c}
\def\psas@C{2 \psas@@c}
\def\psas@@c{%
setlinecap
0 0 moveto
0 CLW 2 div L
stroke
0 0 moveto}
\def\psas@{}
\psset@arrows{-}
\def\tx@SD{SD }
\def\tx@EndDot{EndDot }
\def\psas@oo{{\pst@usecolor\psfillcolor true} true \psk@dotsize \tx@EndDot}
\def\psas@o{{\pst@usecolor\psfillcolor true} false \psk@dotsize \tx@EndDot}
\@namedef{psas@**}{{false} true \psk@dotsize \tx@EndDot}
\@namedef{psas@*}{{false} false \psk@dotsize \tx@EndDot}
\def\pst@par{}
\def\addto@par#1{%
\ifx\pst@par\@empty
\def\pst@par{#1}%
\else
\expandafter\def\expandafter\pst@par\expandafter{\pst@par,#1}%
\fi}
\def\addbefore@par#1{%
\ifx\pst@par\@empty
\def\pst@par{#1}%
\else
\toks@{#1}%
\pst@toks\expandafter{\pst@par}%
\edef\pst@par{\the\toks@,\the\pst@toks}%
\fi}
\def\use@par{%
\ifx\pst@par\@empty\else
\expandafter\@psset\pst@par,\@nil
\def\pst@par{}%
\fi}
\def\pst@object#1{%
\pst@ifstar{%
\@ifnextchar[%
{\pst@@object{#1}}%
{\def\pst@par{}\@nameuse{#1@i}}}}
\def\pst@@object#1[#2]{%
\def\pst@par{#2}%
\@ifnextchar+{\@nameuse{#1@i}}{\@nameuse{#1@i}}}
\def\newpsobject#1#2#3{%
\@ifundefined{#2@i}%
{\@pstrickserr{Graphics object `#2' not defined}\@eha}{%
\@namedef{#1}{\pst@object{#1}}%
\@namedef{#1@i}{\addbefore@par{#3}\@nameuse{#2@i}}}%
\ignorespaces}
\def\pst@getarrows#1{\@ifnextchar({#1}{\pst@@getarrows{#1}}}
\def\pst@@getarrows#1#2{\addto@par{arrows=#2}#1}
\def\begin@ClosedObj{%
\leavevmode
\pst@killglue
\begingroup
\use@par
\solid@star
\ifpsdoubleline \pst@setdoublesep \fi
\init@pscode}
\def\end@ClosedObj{%
\ifpsshadow \pst@closedshadow \fi
\ifdim\psk@border\p@>\z@ \pst@addborder \fi
\psk@fillstyle
\pst@stroke
\ifpsdoubleline \pst@doublestroke \fi
\ifshowpoints
% DG modification begin - Mar. 4, 1995
%\addto@pscode{Points aload length 2 div cvi /N ED \psdots@iii}%
\pst@OpenShowPoints
% DG modification end
\fi
\use@pscode
\endgroup
\ignorespaces}
\def\begin@OpenObj{%
\begin@ClosedObj
\let\pst@linetype\pst@arrowtype
\pst@addarrowdef}
\def\begin@AltOpenObj{%
\begin@ClosedObj
\def\pst@repeatarrowsflag{\z@}%
\def\pst@linetype{0}}
\def\end@OpenObj{%
\ifpsshadow \pst@openshadow \fi
\ifdim\psk@border\p@>\z@ \pst@addborder \fi
\psk@fillstyle
\pst@stroke
\ifpsdoubleline \pst@doublestroke \fi
\ifnum\pst@repeatarrowsflag>\z@ \pst@repeatarrows \fi
\ifshowpoints \pst@OpenShowPoints \fi
\use@pscode
\endgroup
\ignorespaces}
\def\begin@SpecialObj{%
\leavevmode
\pst@killglue
\begingroup
\use@par
\init@pscode}
\def\end@SpecialObj{%
\use@pscode
\endgroup
\ignorespaces}
\def\pst@code{}%
\def\init@pscode{%
\addto@pscode{%
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor}}
\def\addto@pscode#1{\xdef\pst@code{\pst@code#1\space}}
\def\use@pscode{%
\pstverb{%
\pst@dict
\tx@STP
\pst@newpath
\psk@origin
\psk@swapaxes
\pst@code
end}%
\gdef\pst@code{}}
\def\pst@newpath{newpath }
\def\pst@@killglue{\unskip\ifdim\lastskip>\z@\expandafter\pst@@killglue\fi}
\def\KillGlue{\let\pst@killglue\pst@@killglue}
\def\DontKillGlue{\let\pst@killglue\relax}
\DontKillGlue
\def\solid@star{%
\if@star
\pslinewidth=\z@
\psdoublelinefalse
\def\pslinestyle{none}%
\def\psk@fillstyle{\psfs@solid}%
\let\psfillcolor\pslinecolor
\fi}
\def\pst@setdoublesep{%
\pst@getlength\psdoublesep\psdoublesep
\pslinewidth=2\pslinewidth
\advance\pslinewidth\psdoublesep\p@
\let\pst@setdoublesep\relax}
\def\tx@Shadow{Shadow }
\def\pst@closedshadow{%
\addto@pscode{%
gsave
\psk@shadowsize \psk@shadowangle \tx@PtoC
\tx@Shadow
\pst@usecolor\psshadowcolor
gsave fill grestore
stroke
grestore
gsave
\pst@usecolor\psfillcolor
gsave fill grestore
stroke
grestore}}
\def\pst@openshadow{%
\addto@pscode{%
gsave
\psk@shadowsize \psk@shadowangle \tx@PtoC
\tx@Shadow
\pst@usecolor\psshadowcolor
\ifx\psk@fillstyle\relax\else
gsave fill grestore
\fi
stroke}%
\pst@repeatarrows
\addto@pscode{grestore}
\ifx\psk@fillstyle\relax\else
\addto@pscode{%
gsave
\pst@usecolor\psfillcolor
gsave fill grestore
stroke
grestore}
\fi}
\def\pst@addborder{%
\addto@pscode{%
gsave
\psk@border 2 mul
CLW add SLW
\pst@usecolor\psbordercolor
stroke
grestore}}
\def\pst@stroke{%
\ifx\pslinestyle\@none\else
\addto@pscode{%
gsave
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor
\@nameuse{psls@\pslinestyle}
grestore}%
\fi}
\def\pst@fill#1{\addto@pscode{gsave #1 grestore}}%
\def\pst@doublestroke{%
\addto@pscode{%
gsave
\psdoublesep SLW
\pst@usecolor\psdoublecolor
stroke
grestore}}
\def\pst@arrowtype{%
\ifx\psk@arrowB\@empty 0 \else -2 \fi
\ifx\psk@arrowA\@empty 0 \else -1 \fi
add}
\def\pst@addarrowdef{%
\addto@pscode{%
/ArrowA {
\ifx\psk@arrowA\@empty
\pst@oplineto
\else
\pst@arrowdef{A}
moveto
\fi
} def
/ArrowB {
\ifx\psk@arrowB\@empty \else \pst@arrowdef{B} \fi
} def}}
\def\pst@arrowdef#1{%
\ifnum\pst@repeatarrowsflag>\z@
/Arrow#1c [ 6 2 roll ] cvx def Arrow#1c
\fi
\tx@BeginArrow
\psk@arrowscale
\@nameuse{psas@\@nameuse{psk@arrow#1}}
\tx@EndArrow}
\def\pst@repeatarrows{%
\addto@pscode{%
gsave
\ifx\psk@arrowA\@empty\else
ArrowAc ArrowA pop pop
\fi
\ifx\psk@arrowB\@empty\else
ArrowBc ArrowB pop pop pop pop
\fi
grestore}}
\def\pst@OpenShowPoints{%
\addto@pscode{%
gsave
\psk@dotsize
\@nameuse{psds@\psk@dotstyle}
newpath
Points aload length 2 div 2 sub cvi /N ED
N 0 ge
{ \ifx\psk@arrowA\@empty
Dot
\else
pop pop
\fi
N { Dot } repeat
\ifx\psk@arrowB\@empty
Dot
\else
pop pop
\fi }
{ N 2 mul { pop } repeat }
ifelse
grestore}}
\def\pscustom{\pst@object{pscustom}}
\long\def\pscustom@i#1{%
\begin@SpecialObj
\solid@star
\let\pst@ifcustom\iftrue
\let\begin@ClosedObj\begin@CustomObj
\let\end@ClosedObj\endgroup
\def\begin@OpenObj{\begin@CustomObj\pst@addarrowdef}%
\let\end@OpenObj\endgroup
\let\begin@AltOpenObj\begin@CustomObj
\def\begin@SpecialObj{%
\begingroup
\pst@misplaced{special graphics object}%
\def\addto@pscode####1{}
\let\end@SpecialObj\endgroup}%
\def\@multips(##1)(##2)##3##4{\pst@misplaced\multips}%
\def\psclip##1{\pst@misplaced\psclip}%
\def\pst@repeatarrowsflag{\z@}%
\let\pst@setrepeatarrowsflag\relax
\showpointsfalse
\let\showpointstrue\relax
\def\pst@linetype{\pslinetype}%
\let\psset@liftpen\psset@@liftpen
\psset@liftpen{\z@}%
\def\pst@cp{/currentpoint load stopped pop }%
\def\pst@oplineto{/lineto load stopped { moveto } if }%
\def\pst@optcp##1##2{%
\ifnum##1=\z@\def##2{/currentpoint load stopped { 0 0 } if }\fi}%
\let\caddto@pscode\addto@pscode
\def\cuse@par##1{{\use@par##1}}%
\the\pst@customdefs
\setbox\pst@hbox=\hbox{#1}%
\psk@fillstyle
\pst@stroke
\end@SpecialObj}
\def\begin@CustomObj{%
\begingroup
\use@par
\addto@pscode{%
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor}}
\def\pst@oplineto{moveto }
\def\pst@cp{}
\def\pst@optcp#1#2{}
\def\psset@liftpen#1{}
\def\psset@@liftpen#1{%
\ifcase#1\relax
\def\psk@liftpen{\z@}%
\def\pst@cp{/currentpoint load stopped pop }%
\def\pst@oplineto{/lineto load stopped { moveto } if }%
\or
\def\psk@liftpen{1}%
\def\pst@cp{}%
\def\pst@oplineto{/lineto load stopped { moveto } if }%
\or
\def\psk@liftpen{2}%
\def\pst@cp{}%
\def\pst@oplineto{moveto }%
\fi}
\psset@liftpen{0}
\def\psk@liftpen{-1}
\def\psset@linetype#1{%
\pst@getint{#1}\pslinetype
\ifnum\pst@dimg<-3
\@pstrickserr{linetype must be greater than -3}\@ehpa
\def\pslinetype{0}%
\fi}
\psset@linetype{0}
\def\caddto@pscode#1{%
\@pstrickserr{Command can only be used in \string\pscustom}\@ehpa}
\let\cuse@par\caddto@pscode
\def\tx@MSave{%
/msavemtrx
[ tx@Dict /msavemtrx known { msavemtrx aload pop } if CM ]
def }
\def\tx@MRestore{%
tx@Dict /msavemtrx known { length 0 gt } { false } ifelse
{ /msavematrx [ msavematrx aload pop setmatrix ] def }
if }
\newtoks\pst@customdefs
\pst@customdefs{%
\def\newpath{\addto@pscode{newpath}}%
\def\moveto(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor moveto}}%
\def\closepath{\addto@pscode{closepath}}%
\def\gsave{\begingroup\addto@pscode{gsave}}%
\def\grestore{\endgroup\addto@pscode{grestore}}%
% DG/SR modification begin - May 12, 1997 - Patch 2
%\def\translate(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor moveto}}%
\def\translate(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor translate}}%
% DG/SR modification end
\def\rotate#1{\pst@@getangle{#1}\addto@pscode{\pst@angle rotate}}%
\def\scale#1{\pst@getscale{#1}\pst@tempg\addto@pscode{\pst@tempg}}%
\def\msave{\addto@pscode{\tx@MSave}}%
\def\mrestore{\addto@pscode{\tx@MRestore}}%
\def\swapaxes{\addto@pscode{-90 rotate -1 1 scale}}%
\def\stroke{\pst@object{stroke}}%
\def\fill{\pst@object{fill}}%
\def\openshadow{\pst@object{openshadow}}%
\def\closedshadow{\pst@object{closedshadow}}%
% DG/SR modification begin - Jan. 7, 1998 - Patch 8
%\def\movepath(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor tx@Shadow}}%
\def\movepath(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor \tx@Shadow}}%
% DG/SR modification end
\def\lineto{\pst@onecoor{lineto}}%
\def\rlineto{\pst@onecoor{rlineto}}%
\def\curveto{\pst@threecoor{curveto}}%
\def\rcurveto{\pst@threecoor{rcurveto}}%
\def\code#1{\addto@pscode{#1}}%
\def\coor(#1){\pst@@getcoor{#1}\addto@pscode\pst@coor\@ifnextchar({\coor}{}}%
\def\rcoor{\pst@getcoors{}{}}%
\def\dim#1{\pssetlength\pst@dimg{#1}\addto@pscode{\pst@number\pst@dimg}}%
\def\setcolor#1{%
\@ifundefined{color@#1}{}{\addto@pscode{\use@color{#1}}}}%
\def\arrows#1{{\psset@arrows{#1}\pst@addarrowdef}}%
\let\file\pst@rawfile
} % END \pst@customdefs
\def\closedshadow@i{\cuse@par\pst@closedshadow}
\def\openshadow@i{\cuse@par\pst@openshadow}
\def\stroke@i{\cuse@par\pst@stroke}%
\def\fill@i{\cuse@par\psk@fillstyle}%
\def\pst@onecoor#1(#2){%
\pst@@getcoor{#2}%
\addto@pscode{\pst@coor #1}}
\def\pst@threecoor#1(#2)#3(#4)#5(#6){%
\begingroup
\pst@getcoor{#2}\pst@tempa
\pst@getcoor{#4}\pst@tempb
\pst@getcoor{#6}\pst@tembc
\addto@pscode{\pst@tempa \pst@tempb \pst@tempc #1}%
\endgroup}
\def\pst@rawfile#1{%
\begingroup
\def\do##1{\catcode`##1=12\relax}"
\dospecials
\catcode`\%=14
\pst@@rawfile{#1}%
\endgroup}
\def\pst@@rawfile#1{%
\immediate\openin1 #1
\ifeof1
\@pstrickserr{File `#1' not found}\@ehpa
\else
\immediate\read1 to \pst@tempg
\loop
\ifeof1 \@pstfalse\else\@psttrue\fi
\if@pst
\addto@pscode\pst@tempg
\immediate\read1 to \pst@tempg
\repeat
\fi
\immediate\closein1\relax}
\def\tx@NArray{NArray }
\def\tx@NArray{NArray }
\def\tx@Line{Line }
\def\tx@Arcto{Arcto }
\def\tx@CheckClosed{CheckClosed }
\def\tx@Polygon{Polygon }
\def\psset@gangle#1{\pst@getangle{#1}\psk@gangle}
\psset@gangle{0}
\def\tx@Diamond{Diamond }
\def\psdiamond{\pst@object{psdiamond}}
\def\psdiamond@i(#1){%
\@ifnextchar({\psdiamond@ii(#1)}{\psdiamond@ii(0,0)(#1)}}
\def\psdiamond@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@getcoor{#2}\pst@tempb
\addto@pscode{%
\psline@iii
pop
\psk@dimen
\pst@tempb
\psk@gangle
\pst@tempa
\tx@Diamond}%
\def\pst@linetype{4}%
\end@ClosedObj}
\def\tx@Triangle{Triangle }
\def\pstriangle{\pst@object{pstriangle}}
\def\pstriangle@i(#1){%
\@ifnextchar({\pstriangle@ii(#1)}{\pstriangle@ii(0,0)(#1)}}
\def\pstriangle@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@getcoor{#2}\pst@tempb
\addto@pscode{%
\psline@iii
pop
\psk@dimen
\pst@tempb
\psk@gangle
\pst@tempa
\tx@Triangle}%
\def\pst@linetype{2}%
\end@ClosedObj}
\def\tx@CCA{CCA }
\def\tx@CCA{CCA }
\def\tx@CC{CC }
\def\tx@IC{IC }
\def\tx@BOC{BOC }
\def\tx@NC{NC }
\def\tx@EOC{EOC }
\def\tx@BAC{BAC }
\def\tx@NAC{NAC }
\def\tx@EAC{EAC }
\def\tx@OpenCurve{OpenCurve }
\def\tx@AltCurve{AltCurve }
\def\tx@ClosedCurve{ClosedCurve }
\def\psset@curvature#1{%
\edef\pst@tempg{#1 }%
\expandafter\psset@@curvature\pst@tempg * * * \@nil}
\def\psset@@curvature#1 #2 #3 #4\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph
\pst@checknum{#3}\pst@tempi
\edef\psk@curvature{\pst@tempg \pst@temph \pst@tempi}}
\psset@curvature{1 .1 0}
\def\pscurve{\pst@object{pscurve}}
\def\pscurve@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\pscurve@ii}}
\def\pscurve@ii{%
\addto@pscode{%
\pst@cp
\psk@curvature\space /c ED /b ED /a ED
\ifshowpoints true \else false \fi
\tx@OpenCurve}%
\end@OpenObj}
\def\psecurve{\pst@object{psecurve}}
\def\psecurve@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\psecurve@ii}}
\def\psecurve@ii{%
\addto@pscode{%
\psk@curvature\space /c ED /b ED /a ED
\ifshowpoints true \else false \fi
\tx@AltCurve}%
\end@OpenObj}
\def\psccurve{\pst@object{psccurve}}
\def\psccurve@i{%
\begin@ClosedObj
\pst@getcoors[\psccurve@ii}
\def\psccurve@ii{%
\addto@pscode{%
\psk@curvature\space /c ED /b ED /a ED
\ifshowpoints true \else false \fi
\tx@ClosedCurve}%
\def\pst@linetype{1}%
\end@ClosedObj}
\def\psset@dotsize#1{%
\pst@expandafter\pst@getdimnum{#1} 0 {} {}\@nil
\edef\psk@@dotsize{\pst@number\pst@dimg}%
\let\psk@@@dotsize\pst@tempg
\edef\psk@dotsize{%
/DS \psk@@dotsize \psk@@@dotsize CLW mul add 2 div def }}
\psset@dotsize{2pt 2}
\def\psset@dotscale#1{%
\pst@getscale{#1}\psk@dotscale
\ifx\psk@dotscale\@empty
\def\psk@xdotscale{1 }%
\def\psk@ydotscale{1 }%
\else
\let\psk@xdotscale\pst@tempg
\let\psk@ydotscale\pst@temph
% DG/SR modification begin - Oct. 17, 1997 - Patch 5
%\fi}
\fi
\pst@getdotsize%
\psset@dotsize{\pst@dimg\space\pst@@dimtonum\pst@dimh}}
%\psset@dotscale{1}
% DG/SR modification end
\def\pst@Getangle#1#2{%
\pst@getangle{#1}\pst@tempg
\def\pst@temph{0. }%
\ifx\pst@tempg\pst@temph
\def#2{}%
\else
\edef#2{\pst@tempg\space rotate }%
\fi}
\def\psset@dotangle#1{%
\pst@getangle{#1}\psk@@dotangle
\ifdim\psk@@dotangle\p@=\z@
\let\psk@dotangle\@empty
\else
% DG/SR modification begin - Aug. 8, 1997 - Patch 4
%\edef\psk@dotangle{\psk@@dotangle rotate }
\edef\psk@dotangle{\psk@@dotangle rotate }%
% DG/SR modification end
\fi}
\psset@dotangle{0}
\def\pst@getdotsize{%
\pst@dimg=\psk@@@dotsize\pslinewidth
\advance\pst@dimg\psk@@dotsize\p@
\pst@dimh=\psk@ydotscale\pst@dimg
\pst@dimg=\psk@xdotscale\pst@dimg
\divide\pst@dimh 2
\divide\pst@dimg 2\relax}
% DG/SR modification begin - Oct. 17, 1997 - Patch 5
\psset@dotscale{1}
% DG/SR modification end
\def\psdot{\pst@object{psdot}}
\def\psdot@i{\@ifnextchar({\psdot@ii}{\psdot@ii(\z@,\z@)}}
\def\psdot@ii(#1){%
\begin@SpecialObj
\pst@@getcoor{#1}%
\addto@pscode{%
\psk@dotsize
\@nameuse{psds@\psk@dotstyle}%
\pst@coor Dot}%
\end@SpecialObj}
\def\psdots{\pst@object{psdots}}
\def\psdots@i{%
\begin@SpecialObj
\pst@getcoors[\psdots@ii}
\def\psdots@ii{%
\addto@pscode{false \tx@NArray \psdots@iii}%
\end@SpecialObj}
\def\psdots@iii{%
\psk@dotsize
\@nameuse{psds@\psk@dotstyle}
newpath
n { transform floor .5 add exch floor .5 add exch itransform Dot } repeat}
% DG: dead code (to suppress until \psset@dotstyle) ? - Aug. 4, 1997
\def\tx@SQ{SQ }
\def\tx@ST{ST }
\def\tx@SP{SP }
\def\pst@gdot#1{/Dot { gsave T \psk@dotangle \psk@dotscale #1 grestore } def }
\@namedef{psds@*}{\pst@gdot{0 0 DS \tx@SD}}
\@namedef{psds@o}{%
/r2 DS CLW sub def
\pst@gdot{0 0 DS \tx@SD \pst@usecolor\psfillcolor 0 0 r2 \tx@SD}}
\@namedef{psds@square*}{%
/r1 DS .886 mul def
\pst@gdot{r1 \tx@SQ}}
\@namedef{psds@square}{%
/r1 DS .886 mul def /r2 r1 CLW sub def
\pst@gdot{r1 \tx@SQ \pst@usecolor\psfillcolor r2 \tx@SQ}}
\@namedef{psds@triangle*}{%
/y1 DS .778 mul neg def /x1 y1 1.732 mul neg def
\pst@gdot{x1 y1 \tx@ST}}
\@namedef{psds@triangle}{%
/y1 DS .778 mul neg def /x1 y1 1.732 mul neg def
/y2 y1 CLW add def /x2 y2 1.732 mul neg def
\pst@gdot{x1 y1 \tx@ST \pst@usecolor\psfillcolor x2 y2 \tx@ST}}
\@namedef{psds@pentagon*}{%
/r1 DS 1.149 mul def
\pst@gdot{r1 \tx@SP}}
\@namedef{psds@pentagon}{%
DS .93 mul dup 1.236 mul /r1 ED CLW sub 1.236 mul /r2 ED
\pst@gdot{r1 \tx@SP \pst@usecolor\psfillcolor r2 \tx@SP}}
\@namedef{psds@+}{%
/DS DS 1.253 mul def
\pst@gdot{DS 0 moveto DS neg 0 L stroke 0 DS moveto 0 DS neg L stroke}}
\@namedef{psds@|}{%
\psk@tbarsize CLW mul add 2 div /DS ED
\pst@gdot{0 DS moveto 0 DS neg L stroke}}
% DG: end dead code?
\def\psset@dotstyle#1{%
\@ifundefined{psds@#1}%
{\@pstrickserr{Dot style `#1' not defined}\@eha}%
{\edef\psk@dotstyle{#1}}}
\psset@dotstyle{*}
\def\tx@FontDot{FontDot }
\def\newpsfontdot#1[#2]#3#4{%
\@namedef{psds@#1}{%
/#3 \psk@@dotangle [#2] \tx@FontDot
/Dot { moveto #4 show } bind def }}
\def\newpsfontdotH#1[#2]#3#4#5{%
\@namedef{psds@#1}{%
/#3 \psk@@dotangle [#2] \tx@FontDot
/Dot {
moveto
\iftrue
gsave \pst@usecolor\psfillcolor #5 show grestore
\fi
#4 show
} bind def }}
\pstheader{pst-dots.pro}
\newpsfontdot{*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(b)}
\newpsfontdotH{o}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(c)}{(b)}
\newpsfontdotH{Bo}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(C)}{(b)}
\newpsfontdotH{triangle}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(t)}{(u)}
\newpsfontdotH{Btriangle}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(T)}{(u)}
\newpsfontdot{triangle*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(u)}
\newpsfontdotH{square}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(s)}{(r)}
\newpsfontdotH{Bsquare}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(S)}{(r)}
\newpsfontdot{square*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(r)}
\newpsfontdotH{pentagon}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(p)}{(q)}
\newpsfontdotH{Bpentagon}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(P)}{(q)}
\newpsfontdot{pentagon*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(q)}
% DG/SR modification begin - Mar. 18, 1997
%\newpsfontdot{diamond*}%
%[1.9 0.0 0.0 1.9 -0.4598 -0.70775]{Symbol}{<E0>}
%\newpsfontdot{diamond}%
%[2.3 0.0 0.0 2.3 -0.8533 -0.5336]{Symbol}{<A8>}
\newpsfontdot{diamond}%
[1.9 0.0 0.0 1.9 -0.4598 -0.70775]{Symbol}{<E0>}
\newpsfontdot{diamond*}%
[2.3 0.0 0.0 2.3 -0.8533 -0.5336]{Symbol}{<A8>}
% DG/SR modification end
\newpsfontdot{oplus}%
[1.44928 0.0 0.0 1.44928 -0.562319 -0.478261]{Symbol}{<C5>}
\newpsfontdot{otimes}%
[1.44928 0.0 0.0 1.44928 -0.562319 -0.475362]{Symbol}{<C4>}
\newpsfontdot{x}%
[1.8 0.0 0.0 1.8 -0.495 -0.4788]{Symbol}{<B4>}
\newpsfontdot{+}%
[2.3 0.0 0.0 2.3 -0.6486 -0.5819]{Times-Roman}{<2B>}
\newpsfontdot{asterisk}%
[2.43309 0.0 0.0 2.43309 -0.609489 -1.14477]{Times-Roman}{<2A>}
\newpsfontdot{B+}%
[2.3 0.0 0.0 2.3 -0.6555 -0.5819]{Times-Bold}{<2B>}
\newpsfontdot{Basterisk}%
[2.29358 0.0 0.0 2.29358 -0.576835 -1.08486]{Times-Bold}{<2A>}
\newpsfontdot{|}%
% DG/SR modification begin - Oct. 27, 1997 - Patch 7
%[1.98413 0.0 0.0 1.98413 -0.258929 -0.712302]{Helvetica}{(|)}
[1.98413 0.0 0.0 1.38 -0.258929 -0.5]{Helvetica}{(|)}
% DG/SR modification end
\newpsfontdot{B|}%
% DG/SR modification begin - Oct. 27, 1997 - Patch 7
%[1.98413 0.0 0.0 1.98413 -0.277778 -0.78302]{Helvetica-Bold}{(|)}
[1.98413 0.0 0.0 1.38 -0.277778 -0.5]{Helvetica-Bold}{(|)}
% DG/SR modification end
\iffalse
\newpsfontdot{*}%
[2.77778 0.0 0.0 2.77778 -0.638889 -0.813889]{Symbol}{<B7>}
\newpsfontdot{o}%
[3.33333 0.0 0.0 3.33333 -0.666667 -1.78167]{Symbol}{<B0>}
\newpsfontdot{Bo}%
[4.69484 0.0 0.0 4.69484 -0.78169 -2.97418]{Times-Bold}{<CA>}
\fi
\newdimen\pslinearc
\def\psset@linearc#1{\pssetlength\pslinearc{#1}}
\psset@linearc{0pt}
\def\psline{\pst@object{psline}}
\def\psline@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\psline@ii}}
\def\psline@ii{%
\addto@pscode{\pst@cp \psline@iii \tx@Line}%
\end@OpenObj}
\def\psline@iii{%
\ifdim\pslinearc>\z@
/r \pst@number\pslinearc def
/Lineto { \tx@Arcto } def
\else
/Lineto /lineto load def
\fi
\ifshowpoints true \else false \fi}
\def\qline(#1)(#2){%
\def\pst@par{}%
\begin@SpecialObj
\def\pst@linetype{0}%
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\addto@pscode{%
\pst@tempa moveto \pst@coor L
\@nameuse{psls@\pslinestyle}}%
\end@SpecialObj}
\def\pspolygon{\pst@object{pspolygon}}
\def\pspolygon@i{%
\begin@ClosedObj
\def\pst@cp{}%
\pst@getcoors[\pspolygon@ii}
\def\pspolygon@ii{%
\addto@pscode{\psline@iii \tx@Polygon}%
\def\pst@linetype{1}%
\end@ClosedObj}
\def\psset@framearc#1{\pst@checknum{#1}\psk@framearc}
\psset@framearc{0}
\def\psset@cornersize#1{%
\pst@expandafter\psset@@cornersize{#1}\@nil}
\def\psset@@cornersize#1#2\@nil{%
\if #1a\relax
\def\psk@cornersize{\pst@number\pslinearc false }%
\else
\def\psk@cornersize{\psk@framearc true }%
\fi}
\psset@cornersize{relative}
\def\tx@Rect{Rect }
\def\tx@OvalFrame{OvalFrame }
\def\tx@Frame{Frame }
\def\psset@dimen#1{%
\pst@expandafter\psset@@dimen{#1}\@nil}
\def\psset@@dimen#1#2\@nil{%
\if #1o\relax
\def\psk@dimen{.5 }%
\else
\if #1m\relax
\def\psk@dimen{0 }%
\else
\if #1i\relax
\def\psk@dimen{-.5 }%
\fi
\fi
\fi}
\psset@dimen{outer}
\def\psframe{\pst@object{psframe}}
\def\psframe@i(#1){%
\@ifnextchar({\psframe@ii(#1)}{\psframe@ii(0,0)(#1)}}
\def\psframe@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\addto@pscode{\psk@cornersize \pst@tempa \pst@coor \psk@dimen \tx@Frame}%
\def\pst@linetype{2}%
\showpointsfalse
\end@ClosedObj}
\def\tx@BezierNArray{BezierNArray }
\def\tx@OpenBezier{OpenBezier }
\def\tx@ClosedBezier{ClosedBezier }
\def\tx@BezierShowPoints{BezierShowPoints }
\def\psbezier{\pst@object{psbezier}}
\def\psbezier@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\psbezier@ii}}
\def\psbezier@ii{%
\addto@pscode{%
% DG/SR modification begin - Apr. 28, 1997 - Patch 1
% \psbezier doesn't work inside \pscustom
%\pst@cp
% DG/SR modification end
\ifshowpoints true \else false \fi
\tx@OpenBezier
\ifshowpoints \tx@BezierShowPoints \fi}%
\end@OpenObj}
\def\pscbezier{\pst@object{pscbezier}}
\def\pscbezier@i{%
\begin@ClosedObj
\pst@getcoors[\pscbezier@ii}
\def\pscbezier@ii{%
\addto@pscode{%
\ifshowpoints true \else false \fi
\tx@ClosedBezier
\ifshowpoints \tx@BezierShowPoints \fi}%
\chardef\pst@linetype=1
\end@ClosedObj}
\def\tx@Parab{Parab }
\def\parabola{\pst@object{parabola}}
\def\parabola@i{\pst@getarrows\parabola@ii}
\def\parabola@ii#1(#2)#3(#4){%
\begin@OpenObj
\pst@getcoor{#2}\pst@tempa
\pst@@getcoor{#4}%
\addto@pscode{\pst@tempa \pst@coor \tx@Parab}%
\end@OpenObj}
\def\psset@gridwidth#1{\pst@getlength{#1}\psk@gridwidth}
\psset@gridwidth{.8pt}
\def\psset@griddots#1{%
\pst@cntg=#1\relax
\edef\psk@griddots{\the\pst@cntg}}
\psset@griddots{0}
\def\psset@gridcolor#1{\pst@getcolor{#1}\psgridcolor}
\psset@gridcolor{black}
\def\psset@subgridwidth#1{\pst@getlength{#1}\psk@subgridwidth}
\psset@subgridwidth{.4pt}
\def\psset@subgridcolor#1{\pst@getcolor{#1}\pssubgridcolor}
\psset@subgridcolor{gray}
\def\psset@subgriddots#1{%
\pst@cntg=#1\relax\edef\psk@subgriddots{\the\pst@cntg}}
\psset@subgriddots{0}
\def\psset@subgriddiv#1{%
\pst@cntg=#1\relax\edef\psk@subgriddiv{\the\pst@cntg}}
\psset@subgriddiv{5}
\def\psset@gridlabels#1{\pst@getlength{#1}\psk@gridlabels}
\psset@gridlabels{10pt}
\def\psset@gridlabelcolor#1{\pst@getcolor{#1}\psgridlabelcolor}
\psset@gridlabelcolor{black}
\def\tx@Grid{Grid }
\def\psgrid{\pst@object{psgrid}}
\def\psgrid@i{\@ifnextchar(%
{\psgrid@ii}{\expandafter\psgrid@iv\pic@coor}}
\def\psgrid@ii(#1){\@ifnextchar(%
{\psgrid@iii(#1)}{\psgrid@iv(0,0)(0,0)(#1)}}
\def\psgrid@iii(#1)(#2){\@ifnextchar(%
{\psgrid@iv(#1)(#2)}{\psgrid@iv(#1)(#1)(#2)}}
\def\psgrid@iv(#1)(#2)(#3){%
\begin@SpecialObj
\pst@getcoor{#1}\pst@tempa
\pst@getcoor{#2}\pst@tempb
\pst@@getcoor{#3}%
\ifnum\psk@subgriddiv>1
\addto@pscode{gsave
\psk@subgridwidth SLW \pst@usecolor\pssubgridcolor
\pst@tempb \pst@coor \pst@tempa
\pst@number\psxunit \pst@number\psyunit
\psk@subgriddiv\space \psk@subgriddots\space
{} 0 \tx@Grid grestore}%
\fi
\addto@pscode{gsave
\psk@gridwidth SLW \pst@usecolor\psgridcolor
\pst@tempb \pst@coor \pst@tempa
\pst@number\psxunit \pst@number\psyunit
1 \psk@griddots\space { \pst@usecolor\psgridlabelcolor }
\psk@gridlabels \tx@Grid grestore}%
\end@SpecialObj}
\newif\ifpsmathbox
\psmathboxtrue
\def\pst@mathflag{\z@}
\newtoks\everypsbox
\let\pst@thisbox\relax
\long\def\pst@makenotverbbox#1#2{%
\edef\pst@mathflag{%
\ifpsmathbox\ifmmode\ifinner 1\else 2\fi\else \z@\fi\else \z@\fi}%
\setbox\pst@hbox=\hbox{%
\ifcase\pst@mathflag\or$\m@th\textstyle\or$\m@th\displaystyle\fi
{\pst@thisbox\the\everypsbox#2}%
\ifnum\pst@mathflag>\z@$\fi}%
#1}
\def\pst@makeverbbox#1{%
\def\pst@afterbox{#1}%
\edef\pst@mathflag{%
\ifpsmathbox\ifmmode\ifinner 1\else 2\fi\else \z@\fi\else \z@\fi}%
\afterassignment\pst@beginbox
\setbox\pst@hbox\hbox}
\def\pst@beginbox{%
\ifcase\pst@mathflag\or$\m@th\or$\m@th\displaystyle\fi
\bgroup\aftergroup\pst@endbox
\pst@thisbox
\the\everypsbox}
\def\pst@endbox{%
\ifnum\pst@mathflag>\z@$\fi
\egroup
\pst@afterbox}
\def\pst@makebox{\pst@@makebox}
\def\psverbboxtrue{\def\pst@@makebox{\pst@makeverbbox}}
\def\psverbboxfalse{\def\pst@@makebox{\pst@makenotverbbox}}
\psverbboxfalse
\def\pst@longbox{%
\def\pst@makebox{%
\gdef\pst@makebox{\pst@@makebox}%
\pst@makelongbox}}
\def\pst@makelongbox#1{%
\def\pst@afterbox{#1}%
\edef\pst@mathflag{%
\ifpsmathbox\ifmmode\ifinner 1\else 2\fi\else \z@\fi\else \z@\fi}%
\setbox\pst@hbox\hbox\bgroup
\aftergroup\pst@afterbox
\ifcase\pst@mathflag\or$\m@th\or$\m@th\displaystyle\fi
\begingroup
\pst@thisbox
\the\everypsbox}
\def\pst@endlongbox{%
\endgroup
\ifnum\pst@mathflag>\z@$\fi
\egroup}
\def\pslongbox#1#2{%
\@namedef{#1}{\pst@longbox#2}%
\@namedef{end#1}{\pst@endlongbox}}
\newdimen\psframesep
\def\psset@framesep#1{\pssetlength\psframesep{#1}}
\psset@framesep{3pt}
\newif\ifpsboxsep
\def\psset@boxsep#1{\@nameuse{psboxsep#1}}
\psset@boxsep{true}
\def\pst@useboxpar{%
\use@par
\if@star
\let\pslinecolor\psfillcolor
\solid@star
\let\solid@star\relax
\fi
\ifpsdoubleline \pst@setdoublesep \fi}
\def\psframebox{\pst@object{psframebox}}
\def\psframebox@i{\pst@makebox\psframebox@ii}
\def\psframebox@ii{%
\begingroup
\pst@useboxpar
\pst@dima=\pslinewidth
\advance\pst@dima by \psframesep
\pst@dimc=\wd\pst@hbox\advance\pst@dimc by \pst@dima
\pst@dimb=\dp\pst@hbox\advance\pst@dimb by \pst@dima
\pst@dimd=\ht\pst@hbox\advance\pst@dimd by \pst@dima
\setbox\pst@hbox=\hbox{%
\ifpsboxsep\kern\pst@dima\fi
\begin@ClosedObj
\addto@pscode{%
\psk@cornersize
\pst@number\pst@dima neg
\pst@number\pst@dimb neg
\pst@number\pst@dimc
\pst@number\pst@dimd
.5
\tx@Frame}%
\def\pst@linetype{2}%
\showpointsfalse
\end@ClosedObj
\box\pst@hbox
\ifpsboxsep\kern\pst@dima\fi}%
\ifpsboxsep\dp\pst@hbox=\pst@dimb\ht\pst@hbox=\pst@dimd\fi
\leavevmode\box\pst@hbox
\endgroup}
\def\psdblframebox{\pst@object{psdblframebox}}
\def\psdblframebox@i{\addto@par{doubleline=true}\psframebox@i}
\def\psclip#1{%
\leavevmode
\begingroup
\begin@psclip
\begingroup
\def\use@pscode{%
\pstVerb{%
\pst@dict
/mtrxc CM def
CP CP T
\tx@STV
\psk@origin
\psk@swapaxes
newpath
\pst@code
clip
newpath
mtrxc setmatrix
moveto
0 setgray
end}%
\gdef\pst@code{}}%
\def\@multips(##1)(##2)##3##4{\pst@misplaced\multips}%
\def\nc@object##1##2##3##4{\pst@misplaced{node connection}}%
\hbox to\z@{#1}%
\endgroup
\def\endpsclip{%
\end@psclip
\endgroup}%
\ignorespaces}
\def\endpsclip{\pst@misplaced\endpsclip}
\let\begin@psclip\relax
\def\end@psclip{\pstVerb{currentpoint initclip moveto}}
\def\AltClipMode{%
\def\end@psclip{\pstVerb{\pst@grestore}}%
\def\begin@psclip{\pstVerb{gsave}}}
\def\clipbox{\@ifnextchar[{\clipbox@}{\clipbox@[\z@]}}
% DG modification begin - Apr. 3, 1997
% From paulus@immd5.informatik.uni-erlangen.de (Dietrich Paulus)
%\def\clipbox@[#1]{\pst@makebox\clipbox@@{#1}}
\def\clipbox@[#1]{\pst@makebox{\clipbox@@{#1}}}
% DG modification end
\def\clipbox@@#1{%
\pssetlength\pst@dimg{#1}%
\leavevmode\hbox{%
\begin@psclip
\pst@Verb{%
CM \tx@STV CP T newpath
/a \pst@number\pst@dimg def
/w \pst@number{\wd\pst@hbox}a add def
/d \pst@number{\dp\pst@hbox}a add neg def
/h \pst@number{\ht\pst@hbox}a add def
a neg d moveto
a neg h L
w h L
w d L
closepath
clip
newpath
0 0 moveto
setmatrix}%
\unhbox\pst@hbox
\end@psclip}}
\def\psshadowbox{\pst@object{psshadowbox}}
\def\psshadowbox@i{\pst@makebox\psshadowbox@ii}
\def\psshadowbox@ii{%
\begingroup
\pst@useboxpar
\psshadowtrue
\psboxseptrue
\def\psk@shadowangle{-45 }%
\setbox\pst@hbox=\hbox{\psframebox@ii}%
\pst@dimh=\psk@shadowsize\p@
\pst@dimh=.7071\pst@dimh
\pst@dimg=\dp\pst@hbox
\advance\pst@dimg\pst@dimh
\dp\pst@hbox=\pst@dimg
\pst@dimg=\wd\pst@hbox
\advance\pst@dimg\pst@dimh
\wd\pst@hbox=\pst@dimg
\leavevmode
\box\pst@hbox
\endgroup}
\def\pscirclebox{\pst@object{pscirclebox}}
\def\pscirclebox@i{\pst@makebox\pscirclebox@ii}
\def\pscirclebox@ii{%
\begingroup
\pst@useboxpar
\setbox\pst@hbox=\hbox{%
\pst@nodehook
\pscirclebox@iii
\box\pst@hbox}%
\ifpsboxsep \pscirclebox@sep \fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\pscirclebox@iii{%
\if@star
\pslinewidth\z@
\pstverb{\pst@dict \tx@STP \pst@usecolor\psfillcolor
newpath \pscirclebox@iv \tx@SD end}%
\else
\begin@ClosedObj
\def\pst@linetype{4}\showpointsfalse
\addto@pscode{%
\pscirclebox@iv CLW 2 div add 0 360 arc closepath}%
\end@ClosedObj
\fi}
\def\pscirclebox@iv{%
\pst@number{\wd\pst@hbox}2 div
\pst@number{\ht\pst@hbox}\pst@number{\dp\pst@hbox}add 2 div
2 copy \pst@number{\dp\pst@hbox}sub 4 2 roll
\tx@Pyth \pst@number\psframesep add }
\def\pscirclebox@sep{%
\pst@dimb=\ht\pst@hbox
\advance\pst@dimb\dp\pst@hbox
\divide\pst@dimb 2
\pst@dima=.5\wd\pst@hbox
\pst@pyth\pst@dima\pst@dimb\pst@dimc
\advance\pst@dimc\pslinewidth
\advance\pst@dimc\psframesep
\advance\pst@dimb-\pst@dimc
\setbox\pst@hbox=\hbox to2\pst@dimc{%
\hss
\vbox{\kern-\pst@dimb\box\pst@hbox}%
\hss}%
\advance\pst@dimb-\dp\pst@hbox
\dp\pst@hbox=-\pst@dimb}
\let\pst@nodehook\relax
\def\psCirclebox{\pst@object{psCirclebox}}
\def\psCirclebox@i{\pst@makebox\psCirclebox@ii}
\def\psCirclebox@ii{%
\begingroup
\pst@useboxpar
\pst@dima=\ht\pst@hbox
\advance\pst@dima\dp\pst@hbox
\divide\pst@dima\tw@
\pssetlength\pst@dimb\psk@radius
\setbox\pst@hbox=\hbox{%
\pst@nodehook
\pscircle(.5\wd\pst@hbox,\pst@dima){\pst@dimb}%
\box\pst@hbox}%
\ifpsboxsep \psCirclebox@sep \fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\psCirclebox@sep{%
\pst@dimc=\pst@dimb
\advance\pst@dimb-\pst@dima
\advance\pst@dima\pst@dimc
\setbox\pst@hbox=\hbox to\tw@\pst@dimc{%
\hss
\vrule width \z@ depth \pst@dimb height \pst@dima
\box\pst@hbox
\hss}}%
\def\psovalbox{\pst@object{psovalbox}}
\def\psovalbox@i{\pst@makebox{\psovalbox@ii}}
\def\psovalbox@ii{%
\begingroup
\pst@useboxpar
\psovalbox@iii
\ifpsboxsep\psovalbox@sep\fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\psovalbox@iii{%
\psovalbox@iv
\setbox\pst@hbox=\hbox{%
\begin@ClosedObj
\addto@pscode{%
0 360
\pst@number\pst@dimc CLW 2 div sub
\pst@number\pst@dimd CLW 2 div sub
\pst@number\pst@dima
\pst@number\pst@dimb
\tx@Ellipse
closepath}%
\def\pst@linetype{2}%
\end@ClosedObj
\unhbox\pst@hbox}}
\def\psovalbox@iv{%
\pst@dimc=\pslinewidth\advance\pst@dimc\psframesep
\pst@dimd=\ht\pst@hbox\advance\pst@dimd\dp\pst@hbox
\pst@dima=.5\wd\pst@hbox
\pst@dimb=.5\pst@dimd\advance\pst@dimb-\dp\pst@hbox
\pst@dimd=.707\pst@dimd
\advance\pst@dimd\pst@dimc
\advance\pst@dimc.707\wd\pst@hbox}
\def\psovalbox@sep{%
\setbox\pst@hbox\hbox to 2\pst@dimc{\hss\unhbox\pst@hbox\hss}%
\pst@dimg=\pst@dimd
\advance\pst@dimg-\pst@dimb
\dp\pst@hbox=\pst@dimg
\advance\pst@dimd\pst@dimb
\ht\pst@hbox=\pst@dimd}
\def\psdiabox{\pst@object{psdiabox}}
\def\psdiabox@i{\pst@makebox{\psdiabox@ii}}
\def\psdiabox@ii{%
\begingroup
\pst@useboxpar
\psdiabox@iii
\ifpsboxsep\psdiabox@sep\fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\psdiabox@iv{%
\pst@dimg=.707\pslinewidth
\advance\pst@dimg.707\psframesep
\pst@dima=\wd\pst@hbox
\divide\pst@dima 2
\pst@dimc=\pst@dima
\advance\pst@dimc\pst@dimg
\pst@dimd=\ht\pst@hbox
\advance\pst@dimd\dp\pst@hbox
\divide\pst@dimd 2
\pst@dimb=\pst@dimd
\advance\pst@dimb-\dp\pst@hbox
\advance\pst@dimd\pst@dimg}
\def\psdiabox@iii{%
\psdiabox@iv
\setbox\pst@hbox=\hbox{%
\begin@ClosedObj
\addto@pscode{%
\psline@iii
pop
.5
\pst@number\pst@dimc 2 mul \pst@number\pst@dimd 2 mul
0
\pst@number\pst@dima \pst@number\pst@dimb
\tx@Diamond}%
\def\pst@linetype{4}%
\end@ClosedObj
\box\pst@hbox}}
\def\psdiabox@sep{%
\setbox\pst@hbox\hbox to 4\pst@dimc{\hss\unhbox\pst@hbox\hss}%
\multiply\pst@dimd 2
\advance\pst@dimd\pst@dimb
\ht\pst@hbox\pst@dimd
\advance\pst@dimd-2\pst@dimb
\dp\pst@hbox\pst@dimd}
\def\psset@trimode#1{\pst@expandafter\psset@@trimode{#1}\@empty\@empty\@nil}
\def\psset@@trimode#1#2#3\@nil{%
\let\pst@tempg#1\relax
\ifx\pst@tempg*%
\let\psk@@trimode\@empty
\let\pst@tempg#2\relax
\else
\let\psk@@trimode\relax
\fi
\edef\psk@trimode{%
\ifx R\pst@tempg 1 \else\ifx D\pst@tempg 2
\else\ifx L\pst@tempg 3 \else 0 \fi\fi\fi}}
\psset@trimode{U}
\def\pstribox{\pst@object{pstribox}}
\def\pstribox@i{\pst@makebox{\pstribox@ii}}
\def\pstribox@ii{%
\begingroup
\pst@useboxpar
\pstribox@iii
\ifpsboxsep\pstribox@sep\fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\pstribox@iii{%
\pstribox@iv
\setbox\pst@hbox=\hbox{%
\begin@ClosedObj
\addto@pscode{%
\psline@iii
pop
.5
\pst@number\pst@dimc \pst@number\pst@dimd
\ifodd\psk@trimode exch \fi
\psk@trimode -90 mul
\pst@number\pst@dima \pst@number\pst@dimb
\tx@Triangle}%
\def\pst@linetype{2}%
\end@ClosedObj
\box\pst@hbox}}
\def\pstribox@iv{%
\pst@dimh=\pslinewidth
\advance\pst@dimh\psframesep
\pst@dimg=\ht\pst@hbox
\advance\pst@dimg-\dp\pst@hbox
\divide\pst@dimg 2
\edef\pst@tempa{\number\pst@dimg sp}% For use by nodes.
\ifodd\psk@trimode
\pst@dimb\pst@dimg
\else
\pst@dima=\wd\pst@hbox
\divide\pst@dima 2
\fi
\ifcase\psk@trimode
\pst@dimb=-\dp\pst@hbox
\advance\pst@dimb-\pst@dimh
\or
\pst@dima=-\pst@dimh
\or
\pst@dimb=\ht\pst@hbox
\advance\pst@dimb\pst@dimh
\or
\pst@dima=\wd\pst@hbox
\advance\pst@dima\pst@dimh
\fi
\pst@dimd=\dp\pst@hbox
\advance\pst@dimd\ht\pst@hbox
\ifx\psk@@trimode\relax
\pst@dimc=\wd\pst@hbox
\advance\pst@dimc\ifodd\psk@trimode 1.447\else 1.789\fi\pst@dimh
\multiply\pst@dimc 2
\advance\pst@dimd\ifodd\psk@trimode 1.789\else 1.447\fi\pst@dimh
\multiply\pst@dimd 2
\else
\ifodd\psk@trimode
\advance\pst@dimd 1.1547\wd\pst@hbox
\advance\pst@dimd 3.4641\pst@dimh
\pst@dimc=.866\pst@dimd
\else
\advance\pst@dimd .866\wd\pst@hbox %.866=(sqrt(3)/2)
\advance\pst@dimd 3\pst@dimh
\pst@dimc=1.1547\pst@dimd % 1.1547=(2/sqrt(3))
\fi
\fi}
\def\pstribox@sep{%
\ifodd\psk@trimode
\advance\pst@dimb.5\pst@dimd
\ht\pst@hbox=\pst@dimb
\advance\pst@dimd-\pst@dimb
\dp\pst@hbox=\pst@dimd
\else
\setbox\pst@hbox\hbox to \pst@dimc{\hss\unhbox\pst@hbox\hss}%
\global\pst@dimg=.5\pst@dimc
\fi
\ifcase\psk@trimode
\dp\pst@hbox-\pst@dimb
\advance\pst@dimd\pst@dimb
\ht\pst@hbox\pst@dimd
\or
\pst@dimg=.5\wd\pst@hbox
\global\advance\pst@dimg-\pst@dima
\setbox\pst@hbox\hbox to \pst@dimc{\kern-\pst@dima\box\pst@hbox\hss}%
\or
\ht\pst@hbox\pst@dimb
\advance\pst@dimd-\pst@dimb
\dp\pst@hbox\pst@dimd
\or
\pst@dimg=\pst@dimc
\advance\pst@dimg-\pst@dima
\global\advance\pst@dimg.5\wd\pst@hbox
\setbox\pst@hbox\hbox to \pst@dimc{%
\hss\box\pst@hbox\kern\psframesep\kern\pslinewidth}%
\fi}
\def\psset@arcsepA#1{\pst@getlength{#1}\psk@arcsepA}
\def\psset@arcsepB#1{\pst@getlength{#1}\psk@arcsepB}
\def\psset@arcsep#1{%
\psset@arcsepA{#1}\let\psk@arcsepB\psk@arcsepA}
\psset@arcsep{0}
\def\tx@ArcArrow{ArcArrow }
\def\psarc{\pst@object{psarc}}
\def\psarc@i{%
\@ifnextchar({\psarc@iii}{\psarc@ii}}
\def\psarc@ii#1{\addto@par{arrows=#1}%
\@ifnextchar({\psarc@iii}{\psarc@iii(0,0)}}
\def\psarc@iii(#1)#2#3#4{%
\begin@OpenObj
\pst@getangle{#3}\pst@tempa
\pst@getangle{#4}\pst@tempb
\pst@@getcoor{#1}%
\pssetlength\pst@dima{#2}%
\addto@pscode{\psarc@iv \psarc@v}%
\gdef\psarc@type{0}%
\showpointsfalse
\end@OpenObj}
\def\psarc@iv{%
\pst@coor /y ED /x ED
/r \pst@number\pst@dima def
/c 57.2957 r \tx@Div def
/angleA
\pst@tempa
\psk@arcsepA c mul 2 div
\ifcase \psarc@type add \or sub \fi
def
/angleB
\pst@tempb
\psk@arcsepB c mul 2 div
\ifcase \psarc@type sub \or add \fi
def
\ifshowpoints\psarc@showpoints\fi
\ifx\psk@arrowA\@empty
\ifnum\psk@liftpen=2
r angleA \tx@PtoC
y add exch x add exch
moveto
\fi
\fi}
\def\psarc@v{%
x y r
angleA
\ifx\psk@arrowA\@empty\else
{ ArrowA CP }
{ \ifcase\psarc@type add \or sub \fi }
\tx@ArcArrow
\fi
angleB
\ifx\psk@arrowB\@empty\else
{ ArrowB }
{ \ifcase\psarc@type sub \or add \fi }
\tx@ArcArrow
\fi
\ifcase\psarc@type arc \or arcn \fi}
\def\psarc@type{0}
\def\psarc@showpoints{%
gsave
newpath
x y moveto
x y r \pst@tempa \pst@tempb
\ifcase\psarc@type arc \or arcn \fi
closepath
CLW 2 div SLW
[ \psk@dash\space ] 0 setdash stroke
grestore }
\def\psarcn{\pst@object{psarcn}}
\def\psarcn@i{\def\psarc@type{1}\psarc@i}
\def\pscircle{\pst@object{pscircle}}
\def\pscircle@i{\@ifnextchar({\pscircle@do}{\pscircle@do(0,0)}}
\def\pscircle@do(#1)#2{%
\if@star
{\use@par\qdisk(#1){#2}}%
\else
\begin@ClosedObj
\pst@@getcoor{#1}%
\pssetlength\pst@dimc{#2}%
\def\pst@linetype{4}%
\addto@pscode{%
\pst@coor
\pst@number\pst@dimc
\psk@dimen CLW mul sub
0 360 arc
closepath}%
\showpointsfalse
\end@ClosedObj
\fi
\ignorespaces}
\def\qdisk(#1)#2{%
\def\pst@par{}%
\begin@SpecialObj
\pst@@getcoor{#1}%
\pssetlength\pst@dimg{#2}%
\addto@pscode{\pst@coor \pst@number\pst@dimg \tx@SD}%
\end@SpecialObj}
\def\psset@radius#1{\pst@@getlength{#1}\psk@radius}
\psset@radius{.25cm}
\def\psCircle{\pst@object{psCircle}}
\def\psCircle@i{\@ifnextchar({\psCircle@ii}{\psCircle@ii(0,0)}}
\def\psCircle@ii(#1){\pscircle@do(#1){\psk@radius}}
\def\pswedge{\pst@object{pswedge}}
\def\pswedge@i{\@ifnextchar({\pswedge@ii}{\pswedge@ii(0,0)}}
\def\pswedge@ii(#1)#2#3#4{%
\begin@ClosedObj
\pssetlength\pst@dimc{#2}
\pst@getangle{#3}\pst@tempa
\pst@getangle{#4}\pst@tempb
\pst@@getcoor{#1}%
\def\pst@linetype{1}%
\addto@pscode{%
\pst@coor
2 copy
moveto
\pst@number\pst@dimc \psk@dimen CLW mul sub % Adjusted radius
\pst@tempa \pst@tempb
arc
closepath}%
\showpointsfalse
\end@ClosedObj}
\def\tx@Ellipse{Ellipse }
\def\psellipse{\pst@object{psellipse}}
\def\psellipse@i(#1){\@ifnextchar(%
{\psellipse@ii(#1)}{\psellipse@ii(0,0)(#1)}}
\def\psellipse@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\addto@pscode{%
0 360
\pst@coor
\ifdim\psk@dimen\p@=\z@\else
\psk@dimen CLW mul
dup 4 -1 roll sub neg 3 1 roll sub
\fi
\pst@tempa
\tx@Ellipse
closepath}%
\def\pst@linetype{2}%
\end@ClosedObj}
\def\multips{\@ifnextchar({\def\pst@par{}\multips@ii}{\multips@i}}
\def\multips@i#1{\def\pst@par{rot=#1}\multips@ii}
\def\multips@ii(#1){\@ifnextchar({\multips@iii(#1)}{\multips@iii(\z@,\z@)(#1)}}
\long\def\multips@iii(#1)(#2)#3#4{%
\begingroup
\use@par
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\pst@cnta=#3\relax
\init@pscode
\addto@pscode{%
\pst@tempa T \the\pst@cnta\space \pslbrace
gsave \ifx\psk@rot\@empty\else\psk@rot rotate \fi}%
\hbox to\z@{%
\def\init@pscode{%
\addto@pscode{%
gsave
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor}}%
\def\use@pscode{\addto@pscode{grestore}}%
\def\psclip##1{\pst@misplaced\psclip}%
\def\nc@object##1##2##3##4{\pst@misplaced{node connection}}%
#4}%
\addto@pscode{grestore \pst@coor T \psrbrace repeat}%
\leavevmode
\use@pscode
\endgroup
\ignorespaces}
\def\scalebox#1{\pst@makebox{\@scalebox{#1}}}
\def\@scalebox#1{%
\begingroup
\pst@getscale{#1}\pst@tempa
\let\pst@tempc\pst@tempg
\let\pst@tempd\pst@temph
\@@scalebox
\endgroup}
\def\@@scalebox{%
\leavevmode
\hbox{%
\ifdim\pst@tempd\p@<\z@
\pst@dimg=\pst@tempd\ht\pst@hbox
\pst@dimh=\pst@tempd\dp\pst@hbox
\dp\pst@hbox=-\pst@dimg
\ht\pst@hbox=-\pst@dimh
\else
\ht\pst@hbox=\pst@tempd\ht\pst@hbox
\dp\pst@hbox=\pst@tempd\dp\pst@hbox
\fi
\pst@dima=\pst@tempc\wd\pst@hbox
\ifdim\pst@dima<\z@\kern-\pst@dima\fi
\pst@Verb{CP CP translate \pst@tempa \tx@NET}%
\hbox to \z@{\box\pst@hbox\hss}%
\pst@Verb{%
CP CP translate
1 \pst@tempc div 1 \pst@tempd div scale
\tx@NET}%
\ifdim\pst@dima>\z@\kern\pst@dima\fi}}
\pslongbox{Scalebox}{\scalebox}
\def\scaleboxto(#1,#2){\pst@makebox{\@scaleboxto(#1,#2)}}
\def\@scaleboxto(#1,#2){%
\begingroup
\pssetlength\pst@dima{#1}%
\pssetlength\pst@dimb{#2}%
\ifdim\pst@dima=\z@\else
\pst@divide{\pst@dima}{\wd\pst@hbox}\pst@tempc
\edef\pst@tempc{\pst@tempc\space}%
\fi
\ifdim\pst@dimb=\z@
\ifdim\pst@dima=\z@
\@pstrickserr{%
\string\scaleboxto\space dimensions cannot both be zero}\@ehpa
\def\pst@tempa{}%
\def\pst@tempc{1 }%
\def\pst@tempd{1 }%
\else
\let\pst@tempd\pst@tempc
\fi
\else
\pst@dimc=\ht\pst@hbox
\advance\pst@dimc\dp\pst@hbox
\pst@divide{\pst@dimb}{\pst@dimc}\pst@tempd
\edef\pst@tempd{\pst@tempd\space}%
\ifdim\pst@dima=\z@ \let\pst@tempc\pst@tempd \fi
\fi
\edef\pst@tempa{\pst@tempc \pst@tempd scale }%
\@@scalebox
\endgroup}
\pslongbox{Scaleboxto}{\scaleboxto}
\def\tx@Rot{Rot }
\def\rotateleft{\pst@makebox{\@rotateleft\pst@hbox}}
\def\@rotateleft#1{%
\leavevmode\hbox{\hskip\ht#1\hskip\dp#1\vbox{\vskip\wd#1%
\pst@Verb{90 \tx@Rot}
\vbox to \z@{\vss\hbox to \z@{\box#1\hss}\vskip\z@}%
\pst@Verb{-90 \tx@Rot}}}}
\def\rotateright{\pst@makebox{\@rotateright\pst@hbox}}
\def\@rotateright#1{%
\hbox{\hskip\ht#1\hskip\dp#1\vbox{\vskip\wd#1%
\pst@Verb{-90 \tx@Rot}
\vbox to \z@{\hbox to \z@{\hss\box#1}\vss}%
\pst@Verb{90 \tx@Rot}}}}
\def\rotatedown{\pst@makebox{\@rotatedown\pst@hbox}}
\def\@rotatedown#1{%
\hbox{\hskip\wd#1\vbox{\vskip\ht#1\vskip\dp#1%
\pst@Verb{180 \tx@Rot}%
\vbox to \z@{\hbox to \z@{\box#1\hss}\vss}%
\pst@Verb{-180 \tx@Rot}}}}
\pslongbox{Rotateleft}{\rotateleft}
\pslongbox{Rotateright}{\rotateright}
\pslongbox{Rotatedown}{\rotatedown}
\def\pst@starbox{%
\setbox\pst@hbox\hbox{\psframebox*[boxsep=false]{\unhbox\pst@hbox}}}
\def\pst@@makesmall#1{%
\setbox#1=\hbox to\z@{\hss\vbox to \z@{\vss\box#1\vss}\hss}}
\def\pst@@@makesmall#1{%
\pst@dimh=\psk@xref\wd#1%
\ifx\psk@yref\relax
\pst@dimg=\dp#1%
\else
\pst@dimg=\psk@yref\ht#1%
\advance\pst@dimg\psk@yref\dp#1%
\fi
\setbox#1=\hbox to\z@{%
\kern-\pst@dimh\vbox to\z@{\vss\box#1\kern-\pst@dimg}\hss}}
\def\psset@ref#1{\pst@expandafter\psset@@ref{#1}\@empty,,\@nil}
\def\psset@@ref#1#2,#3,#4\@nil{%
\def\psk@xref{.5}%
\def\psk@yref{.5}%
\let\pst@makesmall\pst@@@makesmall
\ifx\@empty#3\@empty
\@nameuse{getref@#1}%
\@nameuse{getref@#2}%
\else
\pst@checknum{#1#2}\psk@xref
\pst@checknum{#3}\psk@yref
\fi}
\def\getref@c{\let\pst@makesmall\pst@@makesmall}
\def\getref@t{\def\psk@yref{1}}
\def\getref@b{\def\psk@yref{0}}
\def\getref@B{\let\psk@yref\relax}
\def\getref@l{\def\psk@xref{0}}
\def\getref@r{\def\psk@xref{1}}
\psset@ref{c}
\def\psset@rot#1{%
\pst@expandafter{\@ifnextchar*{\psset@@@rot}{\psset@@rot}}{#1}\@nil}
\def\psset@@rot#1\@nil{%
\def\next##1@#1=##2@##3\@nil{%
\ifx\relax##2%
\pst@getangle{#1}\psk@rot
\else
\def\psk@rot{##2}%
\fi}%
\expandafter\next\pst@rottable @#1=\relax @\@nil}
\def\psset@@@rot#1#2\@nil{%
\psset@@rot#2\@nil
\edef\psk@rot{\pst@rotlist \ifx\psk@rot\@empty\else\psk@rot add \fi}}
\def\pst@rotlist{mark RAngle /a ED cleartomark a neg }
\def\pst@rottable{%
@0=%
@U=%
@L=90 %
@D=180 %
@R=-90 %
@N=\pst@rotlist
@W=\pst@rotlist 90 add %
@S=\pst@rotlist 180 add %
@E=\pst@rotlist 90 sub }
\psset@rot{0}
\def\tx@RotBegin{RotBegin }
\def\tx@RotEnd{RotEnd }
\def\pst@rotate#1#2{%
\ifx#1\@empty\else
\setbox#2=\hbox{\pst@Verb{#1 \tx@RotBegin}\box#2\pst@Verb{\tx@RotEnd}}%
\fi}
\def\psput@cartesian#1{%
\hbox to \z@{\kern\pst@dimg{\vbox to \z@{\vss\box#1\vskip\pst@dimh}\hss}}}
\def\psput@special#1{%
\hbox{%
\pst@Verb{{ \pst@coor } \tx@PutCoor \tx@PutBegin}%
\box#1%
\pst@Verb{\tx@PutEnd}}}
\def\tx@PutCoor{PutCoor }
\def\tx@PutBegin{PutBegin }
\def\tx@PutEnd{PutEnd }
\def\rput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\rput@i}{\rput@ii}}}
\def\rput@i[#1]{\addto@par{ref={#1}}\rput@ii}
\def\rput@ii{\@ifnextchar({\rput@iv}{\rput@iii}}
\def\rput@iii#1{\addto@par{rot={#1}}\@ifnextchar({\rput@iv}{\rput@iv(\z@,\z@)}}
\def\rput@iv(#1){\pst@killglue\pst@makebox{\rput@v{#1}}}
\def\rput@v#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\pst@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\multirput{%
\def\pst@par{}%
\pst@ifstar{\@ifnextchar[{\multirput@i}{\multirput@ii}}}
\def\multirput@i[#1]{\addto@par{ref={#1}}\multirput@ii}
\def\multirput@ii{\@ifnextchar({\multirput@iv}{\multirput@iii}}
\def\multirput@iii#1{\addto@par{rot={#1}}\multirput@iv}
\def\multirput@iv(#1){%
\@ifnextchar({\multirput@v(#1)}{\multirput@v(\z@,\z@)(#1)}}
\def\multirput@v(#1,#2)(#3,#4)#5{%
\pst@makebox{\multirput@vi(#1,#2)(#3,#4){#5}}}
\def\multirput@vi(#1,#2)(#3,#4)#5{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\pst@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\pssetxlength\pst@dima{#1}%
\pssetylength\pst@dimb{#2}%
\pssetxlength\pst@dimc{#3}%
\pssetylength\pst@dimd{#4}%
\pst@cntg=#5\relax
\pst@cnth=\@ne
\leavevmode
\loop
\vbox to \z@{%
\vss
\hbox to \z@{\kern\pst@dima\copy\pst@hbox\hss}%
\vskip\pst@dimb}%
\ifnum\pst@cntg>\pst@cnth
\advance\pst@dima\pst@dimc
\advance\pst@dimb\pst@dimd
\advance\pst@cnth\@ne
\repeat
\endgroup
\ignorespaces}
\newif\if@fixedradius
\def\cput{\pst@object{cput}}
\def\cput@i{\@fixedradiusfalse\cput@ii}
\def\cput@ii{\pst@killglue\@ifnextchar({\cput@iv}{\cput@iii}}
\def\cput@iii#1{%
\addto@par{rot={#1}}%
\@ifnextchar({\cput@iv}{\cput@iv(\z@,\z@)}}
\def\cput@iv(#1){\pst@makebox{\cput@v{#1}}}
\def\cput@v#1{%
\begingroup
\use@par
\setbox\pst@hbox=\hbox{%
\psboxsepfalse
\if@fixedradius\psCirclebox@ii\else\pscirclebox@ii\fi}%
\pst@@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\Cput{\pst@object{Cput}}
\def\Cput@i{\@fixedradiustrue\cput@ii}
\newdimen\pslabelsep
\def\psset@labelsep#1{\pssetlength\pslabelsep{#1}}
\psset@labelsep{5pt}
\def\psset@refangle#1{\pst@expandafter\psset@@refangle{#1}\@nil}
\def\psset@@refangle#1\@nil{%
\def\next##1@#1=##2"##3@##4\@nil{%
\ifx\relax##2%
\pst@getangle{#1}\psk@refangle
\def\psk@uputref{}%
\else
\def\psk@refangle{##2 }%
\def\psk@uputref{##3}%
\fi}%
\expandafter\next\pst@refangletable @#1=\relax"@\@nil}
\def\pst@refangletable{%
@r=0"20%
@u=90"02%
@l=180"10%
@d=-90"01%
@ur=45"22%
@ul=135"12%
@dr=-135"21%
@dl=-45"11}
\psset@refangle{0}
% DG/SR modification begin - Mar. 24, 1999 - Patch 10
%\def\uput{\def\pst@par{}\@ifnextchar[{\uput@ii}{\uput@i}}
\def\uput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\uput@ii}{\uput@i}}} 
% DG/SR modification end
\def\uput@i#1{\addto@par{labelsep=#1}\uput@ii}
\def\uput@ii[#1]{%
\addto@par{refangle={#1}}%
\@ifnextchar({\uput@iv}{\uput@iii}}
\def\uput@iii#1{%
\addto@par{rot={#1}}%
\@ifnextchar({\uput@iv}{\uput@iv(\z@,\z@)}}
\def\uput@iv(#1){\pst@killglue\pst@makebox{\uput@v{#1}}}
\def\uput@v#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\uput@vi
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\uput@vi{%
\ifx\psk@uputref\@empty
\uput@vii\tx@UUput{}%
\else
\ifx\psk@rot\@empty
\expandafter\uput@viii\psk@uputref
\else
\uput@vii\tx@UUput{}%
\fi
\fi}
\def\uput@vii#1#2{%
\edef\pst@coor{%
\pst@number\pslabelsep
#2%
\pst@number{\wd\pst@hbox}%
\pst@number{\ht\pst@hbox}%
\pst@number{\dp\pst@hbox}%
\psk@refangle\space \ifx\psk@rot\@empty\else\psk@rot\space sub \fi
\tx@Uput #1}%
\setbox\pst@hbox=\hbox to\z@{\hss\vbox to\z@{\vss\box\pst@hbox\vss}\hss}%
\setbox\pst@hbox=\psput@special\pst@hbox
\ifx\psk@rot\@empty\else\pst@rotate\psk@rot\pst@hbox\fi}
\def\uput@viii#1#2{%
\ifnum#1>\z@\ifnum#2>\z@\pslabelsep=.707\pslabelsep\fi\fi
\setbox\pst@hbox=\vbox to\z@{%
\ifnum#2=1 \vskip\pslabelsep\else\vss\fi
\hbox to\z@{%
\ifnum#1=2 \hskip\pslabelsep\else\hss\fi
\box\pst@hbox
\ifnum#1=1 \hskip\pslabelsep\else\hss\fi}%
\ifnum#2=2 \vskip\pslabelsep\else\vss\fi}}
\def\tx@Uput{Uput }
\def\tx@UUput{UUput }
\def\Rput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Rput@ii}{\Rput@i}}}
\def\Rput@i#1{\addto@par{labelsep=#1}\Rput@ii}
\def\Rput@ii[#1]{\addto@par{ref={#1}}\@ifnextchar({\Rput@iv}{\Rput@iii}}
\def\Rput@iii#1{\addto@par{rot={#1}}\@ifnextchar({\Rput@iv}{\Rput@iv(\z@,\z@)}}
\def\Rput@iv(#1){\pst@killglue\pst@makebox{\Rput@v{#1}}}
\def\Rput@v#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\Rput@vi
\pst@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\Rput@vi{%
\pst@dimg=\dp\pst@hbox
\advance\pst@dimg\pslabelsep
\dp\pst@hbox=\pst@dimg
\pst@dimg=\ht\pst@hbox
\advance\pst@dimg\pslabelsep
\ht\pst@hbox=\pst@dimg
\setbox\pst@hbox\hbox{\kern\pslabelsep\box\pst@hbox\kern\pslabelsep}}%
\def\oldpsput{%
\def\pst@par{}\pst@ifstar{\@ifnextchar[{\oldpsput@i}{\oldpsput@ii}}}
\def\oldpsput@i[#1]{\addto@par{ref={#1}}\oldpsput@ii}
\def\oldpsput@ii{\@ifnextchar<{\oldpsput@iii}{\oldpsput@iv}}
\def\oldpsput@iii<#1>{\rput@iii{#1}}
\def\OldPsput{\let\psput\oldpsput}
\def\NewPsput{\let\psput\rput}
\def\pspicture{\begingroup\pst@ifstar\pst@picture}
\def\pst@picture{%
\@ifnextchar[{\pst@@picture}{\pst@@picture[0]}}
\def\pst@@picture[#1]#2(#3,#4){%
\@ifnextchar({\pst@@@picture[#1](#3,#4)}%
{\pst@@@picture[#1](0,0)(#3,#4)}}
\def\pst@@@picture[#1](#2,#3)(#4,#5){%
\pssetxlength\pst@dima{#2}%
\pssetylength\pst@dimb{#3}%
\pssetxlength\pst@dimc{#4}%
\pssetylength\pst@dimd{#5}%
\ifdim\pst@dima>\pst@dimc
\pst@dimg=\pst@dima
\pst@dima=\pst@dimc
\pst@dimc=\pst@dimg
\fi
\ifdim\pst@dimb>\pst@dimd
\pst@dimg=\pst@dimb
\pst@dimb=\pst@dimd
\pst@dimd=\pst@dimg
\fi
\def\pst@tempa{#1}%
\setbox\pst@hbox=\hbox\bgroup
\begingroup\KillGlue
\@ifundefined{@latexerr}{}{\let\unitlength\psunit}%
\edef\pic@coor{(#2,#3)(#2,#3)(#4,#5)}\ignorespaces}
\def\pic@coor{(0,0)(0,0)(10,10)}
\def\endpspicture{%
\pst@killglue
\endgroup
\egroup
\ifdim\wd\pst@hbox=\z@\else
%\@pstrickserr{Extraneous space in the pspicture environment}%
%{Type \space <return> \space to procede.}%
\fi
\ht\pst@hbox=\pst@dimd
\dp\pst@hbox=-\pst@dimb
\setbox\pst@hbox=\hbox{%
\kern-\pst@dima
\ifx\pst@tempa\@empty\else
\advance\pst@dimd-\pst@dimb
\pst@dimd=\pst@tempa\pst@dimd
\advance\pst@dimd\pst@dimb
\lower\pst@dimd
\fi
\box\pst@hbox
\kern\pst@dimc}%
\if@star\setbox\pst@hbox=\hbox{\clipbox@@\z@}\fi
\leavevmode\box\pst@hbox
\endgroup}
\@namedef{pspicture*}{\pspicture*}
\@namedef{endpspicture*}{\endpspicture}
\def\tx@BeginOL{BeginOL }
\def\tx@InitOL{InitOL }
\def\pst@initoverlay#1{\pst@Verb{\tx@InitOL /TheOL (#1) def}}
\def\AltOverlayMode{%
\def\pst@initoverlay##1{%
\pst@Verb{%
\tx@InitOL
/Visible { initclip } def
/Invisible {
CP newpath OLUnit itransform moveto clip newpath moveto
} def
/TheOL (##1) def}}}
\def\pst@overlay#1{%
\edef\curr@overlay{#1}%
\pst@Verb{(#1) BOL}%
\aftergroup\pst@endoverlay}
\def\pst@endoverlay{%
\pst@Verb{(\curr@overlay) BOL}}
\def\curr@overlay{all}
\newbox\theoverlaybox
\def\overlaybox{%
\global\setbox\theoverlaybox=\hbox\bgroup
\begingroup
\let\psoverlay\pst@overlay
\def\overlaybox{%
\@pstrickserr{Overlays cannot be nested}\@eha}%
\def\putoverlaybox{%
\@pstrickserr{You must end the overlay box
before using \string\putoverlaybox}}%
\psoverlay{main}%
\ignorespaces}
\def\endoverlaybox{\endgroup\egroup}
\def\putoverlaybox#1{%
\hbox{\pst@initoverlay{#1}\copy\theoverlaybox}}
\def\psoverlay{\@pstrickserr{\string\psoverlay\space
can only be used after \string\overlaybox}}
\ifx\pstcustomize\relax \input pstricks.con \fi
\catcode`\@=\PstAtCode\relax
%
\endinput
%%
%% END: pstricks.tex

quant-ph0109104.extracted_bib
\begin{thebibliography}{10}

\bibitem{Deutsch85}
D.~Deutsch, Proc. Royal Society of London A, {\bf 400}, 97 (1985).

\bibitem{Shor94}
P.W.~Shor, SIAM J. Comp., {\bf 26}, 1484 (1997).

\bibitem{Grover96}
L.K.~Grover, Proc. 28th ACM Symp. Theor. Comp., 212 (1996).

\bibitem{BBBV97} C.~Bennett, E.~Bernstein, G.~Brassard, and
U.~Vazirani, SIAM J. Comp., {\bf 26}, 1510 (1997).

\bibitem{BBCMW98} R.~Beals, H.~Buhrman, R.~Cleve, M.~Mosca, and
R.~de~Wolf, Proc. 39th Symp. Found.  Comp. Sci., 352 (1998).

\bibitem{vanDam98}
W.~van Dam, Proc. 39th Symp. Found. Comp. Sci., 362 (1998).

\bibitem{Cleve99} R.~Cleve, in C.~Macchiavello, G.M. Palma, and
A.~Zeilinger, editors, {\em Collected Papers on Quantum Computation
and Quantum Information Theory}, (World Scientific, 1999).

\bibitem{BCWW01}
H.~Buhrman, R.~Cleve, J.~Watrous, and R.~de~Wolf, quant-ph/0102001, 2001.

\bibitem{Aaronson01}
After this work was circulated, a non-trivial lower

bound was given by S. Aaronson quant-ph/0111102.

\bibitem{BHT98} G.~Brassard, P.~H{\o}yer, and A.~Tapp, 3rd Latin
American Theor. Info. Symp., {\bf 1380}, 163 (1998).

\bibitem{BHMT00} G.~Brassard, P.~H{\o}yer, M.~Mosca, and A.~Tapp, to
appear in Quantum Computation \& Quantum Information Science, AMS
Contemporary Math Series, quant-ph/0005055, 2001.

\bibitem{Ambainis00}
A.~Ambainis, Proc. 32th ACM Symp. Theor. Comp., 636 (2000).

\bibitem{Bennett73}
C. Bennett, IBM J. Res. Dev., {\bf 17}, 525 (1973).


\end{thebibliography}