text:
\section{Introduction}\label{sec:intro}

We consider quantum speedup for solving
computational problems of size $L$ bits, such as
the factoring problem (for which $L$ is the size of the number to be factored)
and the search problem ($L$ is the size of the solution space).
In the well-known quantum algorithms of
Shor \cite{Shor,EJ} and Grover \cite{Grover},
such problems are solved using quantum computers
whose number of qubits ${\cal L} \geq L$
\cite{Shor,EJ,Grover,NC}.
Since quantum speedup becomes relevant for large $L$,
such quantum computers are many-body quantum systems
with a large number of qubits ${\cal L}$.
Since there are many types
(and corresponding measures or indices)
of entanglement for many-body systems
\cite{Bennett,miyake,SM02,Meyer_Wallach,Stockton,Syljuasen,Verstraete,
MSS05,SS05},
it is interesting to explore which types
of entanglement
are relevant to large quantum speedup
over classical computations \cite{PP,JL,Vidal,US04,OL,SSB04,SSB05,conjecture}.

This issue has been studied extensively, particularly on
Shor's factoring algorithm \cite{Shor,EJ}
and Grover's quantum search algorithm \cite{Grover}.
For example, Parker and Plenio demonstrated that the bipartite
entanglement as measured by the logarithmic negativity
is an intrinsic part of Shor's algorithm \cite{PP}.
Shimoni, Shapiro and Biham showed that
highly entangled states are generated in both algorithms \cite{SSB04,SSB05}.
Or\'us and Latorre
studied scaling of entanglement in three algorithms including
Shor's and Grover's \cite{OL}.

For general algorithms,
a few necessary conditions were derived for computational speedup
over classical computations.
Jozsa and Linden showed that
for exponential speedup
a state
is necessary which cannot be factored into a direct
product of states of at most a constant number of qubits \cite{JL}.
Vidal showed that a necessary condition for exponential
speedup is that
the amount of the bipartite entanglement
between one part and the rest of the qubits
increases with $L$ \cite{Vidal}.

We note that one can get a stricter condition by taking the product of
these and other necessary conditions,
which may be obtained by studying other types
of entanglement.
Such a stricter condition would lead to
deeper understanding of quantum computations.
Hence, it is important to seek for more conditions which are
necessary for quantum computational speedup.

As a possible necessary condition,
one of the authors conjectured that
superposition of macroscopically distinct states would be necessary for
quantum computational speedup (Ref.~\cite{conjecture} and Sec.~\ref{sec:conj}).
Although `superposition of macroscopically distinct states'
was only ambiguously defined until
recently, clear definition and
the corresponding index $p$ ($1 \leq p \leq 2$) for pure states
were proposed in Refs.~\cite{SM02,MSS05}, according to which
a pure state has superposition of macroscopically distinct states
if and only if $p=2$.
The generalization to mixed states was made in Ref.~\cite{SM05},
in which $p$ is generalized to an index $q$ ($1 \leq q \leq 2$) ;
a mixed state has superposition of macroscopically distinct states
if and only if $q=2$.
For pure states, $p=2$ implies $q=2$ and vice versa \cite{SM05}.
[For mixed states, $p$ is undefined.]

The entanglement possessed by
superposition of macroscopically distinct states
is totally different from bipartite entanglement which was studied in
the previous works \cite{JL,Vidal}.
[Hence, it was called 'macroscopic entanglement' in
Refs~\cite{SM05,MSS05,MS06,SS05}.
However, we do not use this term in this paper
because the same term is used in other senses by other authors.]
For example,
some pure states with $p=2$ (such as the GHZ state)
have very small bipartite entanglement
whereas some other states with $p=1$ (such as energy eigenstates of
many-body chaotic systems)
have very large bipartite entanglement \cite{MSS05,SS05}.
Therefore,
{\em simultaneous} requirement (for quantum computational speedup)
of the superposition of macroscopically distinct states
{\em and} large bipartite entanglement
is much stronger than the requirement of either one of them.

For a circuit-based quantum computer
performing Shor's factoring algorithm \cite{Shor,EJ},
we obtained results that support
the above conjecture in the previous paper \cite{US04}.
It is interesting to study the correctness of the conjecture
in other algorithms and/or other models
(such as measurement-based quantum computers).
To explore such general cases unambiguously, however,
the conjecture needs to be generalized.
For example,
quantum states in quantum computers are not only {\em inhomogeneous}
but also {\em dependent on instances} (i.e.,
different for different questions of a given problem).
Since the indices $p$ and $q$
assumed a family of similar states that are spatially homogeneous,
the conjecture (which was based on $p$ or $q$) is not
strictly applicable
to such a general family of states,
in its original form.

Furthermore,
since Shor's algorithm is a representative quantum algorithm
for solving structured problems \cite{NC},
it is very interesting to study whether
the conjecture is correct in the case of
quantum algorithms for solving {\em unstructured} problems.
However,
the quantum speedup achieved by
Grover's quantum search algorithm \cite{Grover},
which is a representative algorithm
for unstructured problems \cite{NC},
is not exponential but quadratic.
The conjecture, in its original form, did not assume
speedup of such a degree.

In this paper,
we first generalize the indices $p$ and $q$
to treat general algorithms and models.
We then generalize the conjecture,
using the generalized indices,
in such a way that it is applicable unambiguously
to general models if a
quantum algorithm achieves exponential speedup.
Based on this generalized conjecture,
we further extend the conjecture to the quadratic speedup
of Grover's quantum search algorithm.
It is shown that this extended conjecture is also correct
for Grover's algorithm.
To show details of evolution of
superposition of macroscopically distinct states,
we also perform numerical simulations of a quantum computer that performs
Grover's quantum search algorithm.

This paper is organized as follows.
In Sec.~\ref{sec:p.and.q}, we generalize the indices $p$ and $q$.
Section \ref{sec:conj} is devoted to
generalize and further extend the conjecture.
Analytic results for Grover's quantum search algorithm
are given in Sec.~\ref{sec:Grover-analytic}, where
we will prove that the extended conjecture is correct
for Grover's algorithm.
We present results of
numerical simulations of a quantum computer that performs
Grover's quantum search algorithm
in Sec.~\ref{sec:Grover-numerical}.
Discussions and summary are given in Sec.~\ref{sec:dc}.

\section{Indices of superposition of macroscopically distinct states}
\label{sec:p.and.q}

The indices of
superposition of macroscopically distinct states
were proposed and studied
for pure states in Refs.~\cite{SM02,MSS05,MS06},
and for mixed states in Ref.~\cite{SM05}.
To study these indices for states in quantum computers,
we here generalize their definitions, because,
as will be illustrated explicitly in Secs.~\ref{sec:Grover-analytic} and
\ref{sec:Grover-numerical},
quantum states in quantum computers are not only inhomogeneous
but also dependent on instances.
Here, an {\em instance} is a particular question of a given problem.
The physical meanings and implications
of the indices will also be described briefly
in this section.

\subsection{Index for a family of pure states}
\label{sec:p}

Let $| \psi_\nu(L) \rangle$'s
be pure states of a system of size $L$,
which are labeled by an index $\nu$, e.g.,
as $| \psi_1(L) \rangle, | \psi_2(L) \rangle, | \psi_3(L) \rangle, \cdots$.
For each value of $L$, the range of $\nu$ is given,
for example as $\nu=1, 2, \ldots, 2^L$.
In a quantum computer which solves a decision problem,
$L$ corresponds to the size of a certain register,
which is usually proportional to the size of the input
of the problem, and $\nu$ labels various inputs
(see later sections).
We do {\em not} assume that
$\langle \psi_\nu(L) | \psi_{\nu'}(L) \rangle = 0$
for $\nu \neq \nu'$.
We consider a family $F$ of $| \psi_\nu(L) \rangle$'s,
\begin{equation}
F \equiv
\{ | \psi_\nu(L) \rangle \ | \mbox{ all $\nu$'s, all $L$} \},
\label{def:F}\end{equation}
which we abbreviate to $\{ | \psi_\nu(L) \rangle \}_{L,\nu}$.

In general, a quantum computer consists of a large number of small
quantum systems, such as qubits, which are distributed spatially.
We call each small quantum system a {\em site},
and an operator acting on a single site a {\em local operator}.
To avoid mathematical complexities,
we limit ourselves to the case where
every local operator
is bounded (i.e., its norm is finite).

Let $\hat a(l)$ be a local operator on site $l$.
We normalize it as $\| \hat a(l) \|=1$.
Although this normalization condition
might look too restrictive at first sight,
it actually imposes only a weak restriction
that makes the
maximization
operation in Eq.~(\ref{def:p}) well-defined \cite{note:a(l)},
as discussed in Appendix \ref{app:why|a|=1}.

Note that we can use either $\| \hat a \|_E$ or $\| \hat a \|_H$
as the operator norm $\| \hat a \|$,
where
\begin{eqnarray}
\| \hat a \|_E &\equiv&
\sup_{\| | \psi \rangle \|=1} \| \hat a | \psi \rangle \|,
\label{norm.E}
\\
\| \hat a \|_H &\equiv& \sqrt{(\hat a, \hat a)},
\label{norm.H}\end{eqnarray}
and
$(\hat a, \hat b) \equiv {\rm Tr} (\hat a^\dagger \hat b)$
denotes the inner product of operators $\hat a$ and $\hat b$.
In fact,
both definitions give the same value of the index $p$,
because
$\| \hat a(l) \|_E \leq \| \hat a(l) \|_H \leq \sqrt{d} \| \hat a(l) \|_E$
and
$\| \hat a(l) \|_H/\sqrt{d} \leq \| \hat a(l) \|_E \leq \| \hat a(l) \|_H$,
where $d$ is the dimension of the Hilbert space of a single site.

By the same symbol $\hat a(l)$
we also denote
$\displaystyle \hat a(l) \otimes \bigotimes_{l' (\neq l)}\hat 1(l')$,
which is an operator on the Hilbert space ${\cal H}$ of the total system,
where $\hat 1(l')$ is the identity operator acting on site $l'$.
Using this notation,
we define an {\em additive operator} $\hat{A}(L)$
as the sum of local operators \cite{SM02,SM05};
\begin{equation}
\hat{A}(L) = \sum_{l=1}^L \hat a(l) \quad (\| \hat a(l) \|=1).
\label{def:A}\end{equation}
Here, we do {\em not} assume that $\hat a(l')$ ($l' \neq l$)
is a spatial translation of $\hat a(l)$.

To simplify notation,
we express the expectation value in
$|\psi_\nu(L) \rangle$
as $\langle \cdot \rangle_{L \nu}$.
We also use the symbols $O, \Omega, \Theta$ to
describe asymptotic behaviors according to
Ref.~\cite{NC}, as summarized in Appendix \ref{app:notation}.
Furthermore, as described in Appendix \ref{app:notation},
a family $\{ f_\nu(L) \}_{L,\nu}$ of non-negative functions of $L$
is said to be $\overline{\Theta}(g(L))$
if $f_\nu(L)$ is $\Theta(g(L))$
{\em for almost every $\nu$},
i.e., apart from possible exceptional
$\nu$'s whose measure (i.e., the number of such $\nu$'s
divided by the total number of $\nu$'s) vanishes as $L$
goes to infinity.

For each state $| \psi_\nu(L) \rangle$,
consider fluctuation
$\langle \Delta \hat A(L)^\dagger \Delta \hat A(L) \rangle_{L \nu}$,
where
$\Delta \hat A(L) \equiv \hat A(L) - \langle \hat A(L) \rangle_{L \nu}$.
Its magnitude
depends on $\hat{A}(L)$, i.e., on the choice of $\hat a(l)$'s.
Since $\| \hat A(L) \|$ is upper-bounded, there exists the maximum value,
$\max_{\hat A(L)}
\langle \Delta \hat A(L)^\dagger \Delta \hat A(L) \rangle_{L \nu}
$.
The maximum value is taken for some additive operator
$\hat A_{\max}(L)$,
which we call the {\em most fluctuating additive operator}.
Using the maximum value, which depends on $L$ and $\nu$,
we define the index $p$ of the family
$F$ ($= \{ | \psi_\nu(L) \rangle \}_{L,\nu}$)
as the positive number (if it exists) that satisfies
\begin{equation}
\max_{\hat A(L)} \
\langle \psi_\nu(L) | \Delta \hat A(L)^\dagger \Delta \hat A(L)
|\psi_\nu(L) \rangle
= \overline{\Theta}(L^{p}).
\label{def:p}
\end{equation}
Note that $p$ does not necessarily exist for a general family.
If $p$ exists for a given family,
we can show (see Appendix \ref{appendix_range}) that
\begin{equation}
1 \leq p \leq 2.
\end{equation}
When a family $\{ | \psi_\nu(L) \rangle \}_{L,\nu}$
has $p=2$ (or $p=1$, etc),
we also say simply that `almost every state
$| \psi_\nu(L) \rangle$ has $p=2$ (or $p=1$, etc).'

The present definition of $p$
contains those of the previous works,
Refs.~\cite{SM02,MSS05,MS06,SS05},
as special cases.
In fact,
Refs.~\cite{SM02,MSS05,MS06} treated homogeneous states,
for which $| \psi(L+1) \rangle$
was simply defined as the enlarged state of $| \psi(L) \rangle$.
For example, when
$| \psi(L) \rangle = |00 \cdots 0 \rangle + |11 \cdots 1 \rangle$
with $L$ sites,
then
$| \psi(L+1) \rangle = |000 \cdots 0 \rangle + |111 \cdots 1 \rangle$
with $(L+1)$ sites.
According to the present general definition of $p$,
such a case corresponds to a family
whose members for each $L$ are identical, i.e.,
$| \psi_\nu(L) \rangle = | \psi(L) \rangle$ for all $\nu$.
Moreover, Ref.~\cite{SS05} treated
energy eigenstates of homogeneous chaotic systems.
Since {\em each} energy eigenstate is {\em inhomogeneous} spatially,
this case is different from the case of homogeneous states.
According to the present definition of $p$,
it corresponds to a family composed of
all energy eigenstates in a certain energy interval.
Therefore,
$p$ defined here is a natural generalization of
$p$ of the previous works, Refs.~\cite{SM02,MSS05,MS06,SS05}.

The physical meaning of the present $p$ is basically the same as
the $p$ of these previous works.
That is, almost every state of a family with $p=2$
contains
superposition of states with macroscopically distinct values of
some additive operator(s) \cite{SM02,MSS05,MS06,SS05}.
We call such an additive operator(s) a
{\em macroscopically-fluctuating additive operator(s)} of
the state (or family).
For example, when
$| \psi_\nu(L) \rangle = |00 \cdots 0 \rangle + |11 \cdots 1 \rangle$
for all $\nu$ then its macroscopically-fluctuating additive operator
is $\sum_l \hat{\sigma}_z(l)$,
which corresponds to the $z$ component of
the total magnetization of a magnetic substance.
Since additive operators are macroscopic dynamical variables \cite{SM02,SM05},
two (or more) states are macroscopically distinct from each other
if they have macroscopically distinct values of an additive operator.
Therefore, one can state definitely that
a state with $p=2$ contains
superposition of macroscopically distinct states.

To illustrate how $p$ is useful and necessary for identifying
such superposition,
we give a few simple examples in Appendix \ref{app:examples_homogeneous}.

In the present general definition of $p$,
a macroscopically-fluctuating additive operator(s)
of a given family
can be different for different $L$ and $\nu$,
unlike the case of
homogeneous states treated in Refs.~\cite{SM02,MSS05,MS06}.
Therefore,
we can say the following:
{\em
For a given family
of pure states,
if there exists a family
of additive operators
\begin{equation}
\{ \hat A_\nu(L) \ | \mbox{ all $\nu$'s, all $L$} \}
\end{equation}
such that
\begin{equation}
\langle \Delta \hat A_\nu(L)^\dagger \Delta \hat A_\nu(L) \rangle_{L \nu}
= \overline{\Theta}(L^{2}),
\label{p=2_some_A}
\end{equation}
then the family has $p=2$.
}
This means that
almost all states of the family contain superposition of
states that have macroscopically distinct values
of some additive operator(s).

It is worth mentioning that there often exist two or more families of such
operators, even for a family of homogeneous states \cite{MSS05,MS06}.

\subsection{Index for a family of mixed states}
\label{sec:q}

The index $p$, which is defined only for pure states, is sufficient
for the concrete analyses in Secs.~\ref{sec:Grover-analytic} and
\ref{sec:Grover-numerical}.
However, to state our conjecture in a general form,
we need a more general index which is applicable to mixed states.
For example, measurement-based quantum computers \cite{mbqc1,mbqc2}
often have a larger number of qubits than corresponding
circuit-based computers.
Hence, in such computers,
superposition of macroscopically distinct states might appear as
a mixed state of a subset of qubits \cite{one-way.Grover}.
Fortunately, generalization of $p$
to mixed states has been made in Ref.~\cite{SM05},
in which a generalized index $q$
was proposed
for homogeneous mixed states.
We here generalize it to families of more general
mixed states in order to apply $q$ to wide classes of quantum computers.

For an additive operator $\hat A(L)$,
as given by Eq.~(\ref{def:A}),
and
a projection operator $\hat \eta$ on ${\cal H}$,
satisfying $\hat \eta^2 = \hat \eta$,
we define the following Hermitian operator;
\begin{equation}
\hat C_{\hat A \hat \eta} \equiv
[ \hat A, [ \hat A, \hat \eta ] ]
=
\hat A^2 \hat \eta - 2 \hat A \hat \eta \hat A + \hat \eta \hat A^2.
\label{eq:C}\end{equation}
For a family $\{ \hat \rho_\nu(L) \}_{L,\nu}$ of mixed states,
which are not necessarily homogeneous spatially,
we define the index $q$
as the positive number (if it exists) that satisfies
\begin{equation}
\max \left\{
L,\
\max_{\hat A, \hat \eta} \langle C \rangle_{L \nu}
\right\} = \overline{\Theta}(L^q),
\label{def:q}\end{equation}
where
$\max_{\hat A, \hat \eta}$ is taken over all
possible choices of $\hat A$ and $\hat \eta$.
If this $q$ exists for a given family
we can show (by slightly generalizing the proof in Ref.~\cite{SM05})
that
\begin{equation}
1 \leq q \leq 2.
\end{equation}
We say a family $\{ \hat \rho_\nu(L) \}_{L,\nu}$ of mixed states
contains superposition of macroscopically distinct states
if and only if $q$ exists and $q=2$.
We also say that almost every $\hat \rho_\nu(L)$
of such a family
contains superposition of macroscopically distinct states.
For pure states,
this is consistent with the corresponding statement based on $p$,
because we can show (following the proof in Ref.~\cite{SM05})
that for pure states $p=2$ implies $q=2$ and vice versa.

The case of Ref.~\cite{SM05} corresponds to the special case where
$\hat \rho_\nu(L)$'s are homogeneous and independent of $\nu$
and
$\hat \rho_\nu(L+1)$ is simply the enlarged state of $\hat \rho_\nu(L)$.
In such a case,
$q$ defined here reduces to $q$ of
Ref.~\cite{SM05}.

\subsection{Properties of states with $p=2$ or $q=2$}
\label{sec:Pofpq}

As application of general theory of Ref.~\cite{SM02},
the index $p$ was studied
for many-magnon states in Ref.~\cite{MSS05},
for energy eigenstates of many-body chaotic systems in Ref.~\cite{SS05},
and for typical many-body states in Ref.~\cite{MS06}.
Comparison with a measure of bipartite entanglement were also made
in these references.
Most importantly,
many states
 were found (such as energy eigenstates of a chaotic system)
 such that they are almost maximally
entangled in the bipartite measure but their $p$ is minimum, $p=1$.
Many other states (such as the GHZ state) are also found
such that their $p$ is maximum, $p=2$, but
their bipartite entanglement is small.
Therefore, the aspect of entanglement which is detected by $p$ or $q$
is completely different from that detected by the bipartite measure.
Furthermore,
it has been shown in Ref.~\cite{SM05}
that a family of
states with $q=2$ has a strong $L$-point correlation,
which is $\Theta(L)$ times larger than that of
any separable states.
Note that any measure of bipartite entanglement can{\em not} detect
such a strong $L$-point correlation for mixed states.
On the other hand,
the index $q$ does not detect
entanglement generated by a small number of Bell pairs,
whereas measures of bipartite entanglement do.
These facts demonstrate that
{\em the index $q$ is complementary to
the measures of bipartite entanglement}.

Note that $p$ is calculated from {\em two-point} correlations
because fluctuation of an additive operator is the sum of
two-point correlations;
\begin{equation}
\langle \Delta \hat A(L)^\dagger \Delta \hat A(L) \rangle_{L \nu}
=
\sum_{l=1}^L \sum_{l'=1}^L
\langle \Delta \hat a(l)^\dagger
\Delta \hat a(l') \rangle_{L \nu}.
\end{equation}
However, this does {\em not} mean that
$p$ is related {\em only} to two-point correlations,
because, as mentioned above, pure states with $p=2$ have $q=2$,
which means a strong $L$-point correlation.
That is,
given the knowledge that a family consists of pure states
one can say that if the family has $p=2$ then it has a strong $L$-point correlation.

It was shown in Ref.~\cite{SM02} that
$p$ is directly related to fundamental stabilities
of many-body states
against decoherence and local measurements.
Regarding decoherence by weak noises,
it was shown that for any state
with $p=1$ its decoherence rate $\Gamma$ by {\em any} noises
{\em never} exceeds $O(L)$.
For a state with $p=2$, on the other hand,
it is possible in principle
to construct a noise or environment
that makes $\Gamma$ of the state $\Theta(L^2)$.
However, this does {\em not} necessarily mean that
such a fatal noise or environment does exist in real physical systems;
it depends on physical situations \cite{SM02}.
A more fundamental stability is the
stability against local measurements, which was proposed and
defined in Refs.~\cite{SM02,Mtzk.cp}.
From the theorem proved there,
we can say that a state with $p=2$ is {\em unstable}
against local measurements, i.e.,
there exists a {\em local} observable by measurement of which
the state changes drastically \cite{2p-corr}.

Furthermore, a quite singular property was proved rigorously
in Ref.~\cite{SM02};
any {\em pure} state with $p=2$ in a {\em finite} system of size $L$
does {\em not} approach a pure state in an {\em infinite}
system as $L \to \infty$.
For readers who are not familiar with quantum theory of
infinite systems \cite{Haag},
we give a brief explanation for this fact in Appendix \ref{app:pure2mixed}.

These observations indicate that states with $p=2$ or $q=2$
are quite anomalous many-body states.
This led to the conjecture of Ref.~\cite{conjecture},
which will be generalized
in Sec.~\ref{sec:conj} of the present paper.

\subsection{Efficient method of identifying
superposition of macroscopically distinct states}
\label{sec:VCM}

Evaluation of a measure or index of entanglement often becomes intractable
for large $L$.
Fortunately, this is not the case for $p$ because
there is an efficient method of calculating $p$
\cite{MSS05,SS05,MS06}.
Since this method assumed homogeneous states,
we here generalize it to study general families of pure states.

In this subsection,
the dimension $d$ of the local Hilbert space is arbitrary,
and we employ $\| \hat a \|_H$ defined by Eq.~(\ref{norm.H})
as the operator norm $\| \hat a \|$.

Let $\{ \hat b_0(l), \hat b_1(l), \cdots, \hat b_D(l) \}$ be a complete
orthonormal basis set of operators on site $l$,
where $\hat b_0(l) = \hat 1(l)/\sqrt{d}$ and
$D \equiv d^2-1$.
We expand $\hat a(l)$ as
\begin{equation}
\hat a(l) = \sum_{\alpha=0}^D c_{l \alpha} \hat b_\alpha(l),
\quad \sum_{\alpha=0}^D |c_{l \alpha}|^2 = 1,
\label{eq:a=cb}\end{equation}
where the latter equality comes from $\| \hat a(l) \|_H = 1$.
Let
$\Delta \hat a(l)
\equiv \hat a(l) - \langle \hat a(l) \rangle_{L \nu}$
and
$\Delta \hat b_\alpha(l)
\equiv \hat b_\alpha(L) - \langle \hat b_\alpha(L) \rangle_{L \nu}$.
Note that
$\Delta \hat b_\alpha(l)$'s, unlike $\hat b_\alpha(l)$'s,
 are {\em not} necessarily orthogonal to each other.

Since $\Delta \hat b_0(l) = 0$,
terms with $\alpha=0$ do not contribute to
$\displaystyle \Delta \hat A(L) = \sum_l \Delta \hat a(l)$, i.e.,
it can be expanded as
\begin{equation}
\Delta \hat A(L)
=\sum_{l=1}^L \sum_{\alpha =1}^D c_{l \alpha} \Delta \hat b_\alpha(l),
\quad \sum_{\alpha=1}^D |c_{l \alpha}|^2 \leq 1.
\label{DA:sum_leq_1}
\end{equation}
As a result,
$\sum_l \sum_{\alpha=1}^D |c_{l \alpha}|^2 \leq L$.
Since this normalization is not convenient,
we temporarily consider another operator $\Delta \hat A'$
whose expansion coefficients are {\em normalized};
\begin{equation}
\Delta \hat A'(L)
=
\sum_{l=1}^L \sum_{\alpha =1}^D c'_{l \alpha} \Delta \hat b_\alpha(l),
\quad \sum_{l=1}^L \sum_{\alpha=1}^D |c'_{l \alpha}|^2 =L.
\label{DA:sum=L}\end{equation}
Here, we do {\em not} require that
$\sum_{\alpha=1}^D |c'_{l \alpha}|^2 = 1$ for every $l$.
The fluctuation of such an operator is calculated as
\begin{equation}
\langle \Delta \hat A'(L)^\dagger \Delta \hat A'(L) \rangle_{L \nu}
=
\sum_{l=1}^L \sum_{\alpha =1}^D
\sum_{l'=1}^L \sum_{\alpha' =1}^D
c^{\prime *}_{l \alpha}
c'_{l' \alpha'}
V_{l \alpha, l' \alpha'}(L,\nu)
\end{equation}
for each $| \psi_\nu(L) \rangle$. Here,
for $\alpha, \alpha'=1, 2, \cdots, D$ and
$l, l'= 1, 2, \cdots, L$, we have defined
\begin{equation}
V_{l \alpha, l' \alpha'}(L,\nu)
\equiv
\langle \Delta \hat b^\dagger_\alpha(l)
\Delta \hat b_{\alpha'}(l') \rangle_{L \nu},
\label{def:VCM}\end{equation}
which can be regarded as elements of
a $DL \times DL$ Hermitian matrix,
which we call the {\em variance-covariance matrix} (VCM).
Therefore, for each $| \psi_\nu(L) \rangle$,
\begin{equation}
\max_{\hat A'(L)}
\langle \Delta \hat A'(L)^\dagger \Delta \hat A'(L) \rangle_{L \nu}
=e_{\rm max}(L,\nu) L,
\label{eq:maxA'}\end{equation}
where $e_{\rm max}(L,\nu)$ is the maximum eigenvalue of the VCM.
This and Eq.~(\ref{def:p}) suggest that the following index $p_e$ should be
useful:
\begin{equation}
e_{\rm max}(L,\nu)
= \overline{\Theta}(L^{p_e-1}).
\label{def:p_e}
\end{equation}
In fact, we can show (see Appendix \ref{app:C=O(L^0)}) that
{\em if $p_e=2$ then $p=2$ and vice versa}.
For a family of homogeneous states, in particular,
we can show that $p=p_e$ for every value of $p$
(see the last paragraph of Appendix \ref{app:C=O(L^0)}).
Hence, {\em one can identify states with $p=2$
by calculating $e_{\rm max}(L,\nu)$}.
This can be done in time Poly$(L)$ because the VCM is a
$DL \times DL$
matrix.

Furthermore,
if $p_e=2$
we can find a macroscopically-fluctuating additive operator
from the eigenvector(s)
$\{ c^{\prime \, \nu}_{l \alpha \, {\rm max}}(L) \}$
of the VCM corresponding to $e_{\rm max}(L,\nu)$,
as follows.
If we normalize $\{ c^{\prime \, \nu}_{l \alpha \, {\rm max}}(L) \}$ as
\begin{equation}
\sum_{l=1}^L \sum_{\alpha=1}^D
|c^{\prime \, \nu}_{l \alpha \, {\rm max}}(L)|^2 =L,
\label{normalization:c'max}\end{equation}
then the operator
\begin{equation}
\Delta \hat{A}^{\prime \nu}_{\rm max}(L)
\equiv
\sum_{l=1}^L \sum_{\alpha =1}^D
c^{\prime \, \nu}_{l \alpha \, {\rm max}}(L)
\Delta \hat b_\alpha(l)
\label{DAmax}\end{equation}
takes the form
of Eq.~(\ref{DA:sum=L}), and it fluctuates macroscopically;
\begin{equation}
\langle \Delta \hat{A}^{\prime \nu \dagger}_{\rm max}(L)
\Delta \hat{A}^{\prime \nu}_{\rm max}(L) \rangle_{L \nu}
= e_{\rm max}(L,\nu) L
= \overline{\Theta}(L^{2}).
\label{fluc:DAmax}\end{equation}
As shown in Appendix \ref{app:C=O(L^0)}, if we put
\begin{equation}
C_\nu (L) \equiv
\max_l \left( \sum_{\alpha=1}^D
\left| c^{\prime \, \nu}_{l \alpha \, {\rm max}}(L) \right|^2 \right),
\label{Cnu(L)}\end{equation}
then $C_\nu (L) = \overline{\Omega}(L^0)$ if $p_e=2$.
Therefore,
the following operator
(which clearly takes the form of Eq.~(\ref{DA:sum_leq_1}))
\begin{equation}
\Delta \hat{A}^{\nu}_{\rm max}(L)
\equiv
\sum_{l=1}^L \sum_{\alpha =1}^D
c^\nu_{l \alpha \, {\rm max}}(L)
\Delta \hat b_\alpha(l),
\quad
c^\nu_{l \alpha \, {\rm max}}(L)
\equiv
{c^{\prime \, \nu}_{l \alpha \, {\rm max}}(L)
\over \sqrt{C_\nu (L)}},
\label{DAmax:normalized}\end{equation}
also fluctuates macroscopically;
\begin{equation}
\langle \Delta \hat{A}^{\nu \dagger}_{\rm max}(L)
\Delta \hat{A}^{\nu}_{\rm max}(L) \rangle_{L \nu}
= e_{\rm max}(L,\nu) L/C_\nu (L)
= \overline{\Theta}(L^{2}).
\label{fluc:DAmax:normalized}\end{equation}
We can then construct an additive operator
$\hat{A}^\nu_{\rm max}(L)$
easily from
$\Delta \hat{A}^\nu_{\rm max}(L)$,
by going from Eq.~(\ref{DA:sum_leq_1}) back to Eq.~(\ref{eq:a=cb}).
Although $\hat{A}^\nu_{\rm max}(L)$ is not uniquely determined
from $\Delta \hat{A}^\nu_{\rm max}(L)$
(as discussed in Appendix \ref{app:why|a|=1}),
this non-uniqueness does not cause any difficulty
because $p$ is defined only through the fluctuation.

\section{Conjecture on quantum computation}\label{sec:conj}

The conjecture of Ref.~\cite{conjecture}
is roughly that
superposition of macroscopically distinct states
should be {\em necessary} for large quantum speedup.
We now generalize it
to treat wide classes of algorithms and models.

We consider decision problems
because
most computational problems can be reduced, with polynomial overheads,
to some decision problems.
The number of bits or qubits in a computer is allowed to be Poly$(L)$,
where $L$ denotes the size of the input measured in bits.
To be definite,
we assume that
a quantum computer is composed of qubits (i.e., two-level quantum systems)
which are separated spatially to each other.
That is,
if we use the terms of the general discussions of the previous section,
each qubit is located on its own site.

We consider the time complexity of problems,
allowing both quantum and classical algorithms
to have a bounded probability of error.
In doing so, we assume a classical
probabilistic Turing machine as a
counterpart of a quantum computer.

\subsection{Exponential Speedup}
\label{sec:def-speedup}

To establish notation and to exclude possible ambiguity,
we first define exponential speedup, according to convention, as follows.

We consider problems which are {\em not} in BPP (Bounded-error
Probabilistic Polynomial time).
For a given (decision) problem,
we denote an instance (input) by $i(L,\nu)$,
where $\nu$ labels different instances (inputs) of size $L$.
The computational time depends not only on $L$ but also on $\nu$.
For a given classical computer $C$ and for a given quantum computer $Q$,
let $T_C(L,\nu)$ and $T_Q(L,\nu)$, respectively, be computational time
for an instance $i(L,\nu)$,
with a bounded probability of error being allowed.

Since we are considering a decision problem which is
{\em not} in BPP,
for any classical computer $C$ there exists a set of infinitely
many instances that cannot be solved in polynomial time.
That is,
\begin{equation}
T_C(L,\nu) > \mbox{Poly}(L)
\mbox{ for some infinitely many instances}.
\label{eq:TC>P}\end{equation}
Here, $T_C(L,\nu) > \mbox{Poly}(L)$ means that $T_C(L,\nu) = \Omega(P(L))$
for any polynomial $P(L)$.
For a quantum computer $Q$ solving such a problem,
we say $Q$ achieves
{\em exponential speedup} if
\begin{equation}
T_Q(L,\nu) = \mbox{Poly}(L)
\mbox{ for all $\nu$}.
\label{def:lqs}\end{equation}

According to this definition,
Shor's algorithm \cite{Shor} achieves exponential speedup
(if the factoring is not in BPP).
On the other hand,
{\em the Deutsch-Jozsa algorithm \cite{DJ} does not achieve
exponential speedup} because
the Deutsch's problem {\em is} in BPP.

\subsection{Extra qubits and redefinition of local sites}

In a quantum computer there can exist many qubits
(such as ancilla qubits) which are not directly related to
quantum computational speedup.
For example,
one can replace a classical circuit that assists
a quantum computer with a quantum circuit.
Then, the size of the quantum computer becomes larger
than the original one.
It is clear that
in the enlarged quantum computer
only the original part is relevant to quantum computational speedup.

Therefore,
{\em we allow looking only at a subsystem of a quantum computer}
in order to find out a relevant part, whose state (according to our conjecture)
would have $q=2$.

Furthermore,
one can add extra qubits and circuits to
a quantum computer
without increasing $T_Q(L,\nu)$ more than a Poly$(L)$ factor.
For example,
to implement quantum error correction \cite{ShorCode,ftc}
one can replace each qubit with a logical
qubit,  which is composed of $n$ qubits,
where, e.g., $n=9$ for the Shor code \cite{ShorCode}.
In such a case, correlation between two qubits
is turned into
correlation between two {\em logical} qubits,
i.e., correlation among $2n $ qubits.
As a result, it is possible that
a state with $q=2$ of the original computer is changed into
another state with $q<2$.
However, such nonessential decrease of $q$ may be
recovered by regarding each {\em logical} qubit as a
`local site'.

Generally, in systems which are composed of discrete sites,
a local site (which may be, say, a quantum dot) physically has a finite spatial dimension.
A set of several neighboring sites
also has a finite dimension.
Hence,
the definition of a `local site' is to a great extent arbitrary.
It is therefore possible and reasonable to redefine a set of
neighboring sites as a new single site \cite{2p-corr}.

In quantum computers, there is further arbitrariness because
it is possible to swap the states of two distant qubits,
paying only polynomial overhead.

From these observations,
{\em we allow all possible redefinition of local sites}
(accordingly, the number of local sites is changed)
by regarding two or more qubits, however distant they are, as a local site.

\subsection{Generalized conjecture}\label{subsec:conj}

In order to apply to wide classes of algorithms and models,
we generalize the conjecture of Ref.~\cite{conjecture} as follows.

{\em For a decision problem which is not in BPP, consider
a quantum computer solving it.
If the quantum computer achieves exponential speedup,
then states having $q=2$, whose size is $\Omega(L)$,
appear during computation,
for some set $H$ of infinitely many instances;}
\begin{equation}
H \equiv \{ i(L,\nu) \ | \mbox{ some infinitely many $(L, \nu)$'s}  \}
\label{eq:instances.in.H}\end{equation}
{\em if `local sites' of the quantum computer are appropriately defined.}

This generalized conjecture can be rephrased as follows.
{\em
After defining local sites appropriately,
look at a certain subsystem which is composed of $\Omega(L)$
local sites of
the quantum computer.
Let $\hat \rho_k(L,\nu)$ be the reduced density operator of such a subsystem
at the $k$-th step of the quantum computation.
Take some function $k_*(L,\nu)$, which takes positive integral values,
of $L$ and $\nu$.
For some set $H$ of infinitely many instances
(Eq.~(\ref{eq:instances.in.H})),
consider the following family of states;
\begin{equation}
F_{k_*}(H) \equiv \{
\hat \rho_{k_*}(L,\nu) \ | \
\mbox{all $\nu$ and $L$ such that } i(L,\nu) \in H
\}.
\label{eq:F}\end{equation}
If the quantum computer achieves exponential speedup,
one can find
an appropriate definition of local sites,
a function $k_*(L,\nu)$,
and a set $H$,
such that
$q=2$ for the family $F_{k_*}(H)$.
}

We will explain physical meaning of the set $H$
in the next subsection.

\subsection{Physical meaning of the set $H$}

If the above conjecture is correct,
we can show that $H$
contains
some infinitely many instances
which cannot be solved in polynomial time by any classical computer.
That is, {\em $H$
contains infinitely many `hard' instances}.
This can be seen using reduction to absurdity as follows.

Suppose that the conjecture is correct but $H$
did {\em not} contain infinitely many instances which
satisfy inequality (\ref{eq:TC>P}).
Then, there would exist a classical
computer that solves all instances in $H$
in time Poly$(L)$. By attaching this classical computer to $Q$ as a
pre-processor, one could obtain another fast quantum computer $Q'$.
However, states having $q=2$ would not appear in $Q'$ at all,
in contradiction to the conjecture.
Therefore,
$H$ must contain
infinitely many instances which satisfy inequality (\ref{eq:TC>P}),
if our conjecture is correct.

Note that $H$ is {\em not} uniquely determined for a given problem
because an appropriate subset of $H$ can be another $H$.
To confirm the above conjecture, it is sufficient to
find {\em one} of many possible $H$'s.

The set $H$ is closely related to a
`complexity core' \cite{cc:Lynch,cc:ESY,cc:OS,cc:BD}.
A {\em complexity core}
(or, polynomial complexity core)
${\cal C}$ was defined by Lynch \cite{cc:Lynch} as
an infinite collection of instances such that every algorithm
solving the problem using a deterministic Turing machine
needs more than polynomial time almost everywhere on ${\cal C}$.
[Note that
${\cal C}$ is not
uniquely determined for a given problem
because an appropriate subset of ${\cal C}$ is also a
complexity core \cite{cc:Lynch,cc:ESY,cc:OS,cc:BD}.]
His idea has been generalized to complexity classes other than P
in Refs.~\cite{cc:ESY,cc:OS,cc:BD}.
Intuitively, a complexity core is a set of `hard' instances.
The above-mentioned fact shows that {\em $H$ includes
a complexity core as a subset}.
Hence, our conjecture claims roughly that
{\em states with $q=2$ appear for infinitely many instances in a
complex core}.

\subsection{Remarks on the conjecture}

Before going further, we make a few remarks.

The conjecture
does {\em not} claim that states with $q=2$ would be {\em sufficient}
for exponential speedup;
it rather claims that they are {\em necessary}.
Hence, if states with $q=2$ appear in some quantum
algorithm, it does not necessarily mean that
the algorithm achieves exponential speedup.

Moreover,
even when a quantum computer does achieve exponential speedup,
the conjecture does {\em not} claim that
{\em all} states with $q=2$ appearing in
the computer would be relevant to exponential speedup.
In fact, we already showed in Ref.~\cite{US04} that
although the final state $|\psi_{\rm DFT}\ket$ of the
computation (before the final measurement) has $p=2$ (hence $q=2$)
it is irrelevant to exponential speedup.

Furthermore,
for some states with $q=2$ of size $L$ (such as the GHZ state),
one can construct  a quantum circuit that converts a product state into
such a state only in $\Theta (L)$ steps
{\em if the target state with $q=2$ is known beforehand}
(i.e., when one constructs the circuit).
This fact has {\em nothing} to do with our conjecture.
The point is that
in quantum computation
the state that appears
at, e.g., the middle point of the computation
is {\em unknown} when the circuit is constructed,
because the state varies considerably according to the instances.

Finally, we note that
the results of Ref.~\cite{US04} can be understood more clearly according to
the present generalized conjecture.
For example, it was shown in  Ref.~\cite{US04} that
states with $p=2$ does not appear when $r =2^n$,
where $n=1,2,3,\cdots$
and $r$ is the least positive integer which satisfies
${\sf x}^{r}\equiv 1$ ($\mathrm{mod}\ {\sf N}$).
[${\sf N}$ is a positive integer to be factored,
and ${\sf x}$ a random integer co-prime to ${\sf N}$
which satisfies $0<{\sf x}<{\sf N}$ \cite{US04,Shor,EJ}.]
This fact does {\em not} conflict with the conjecture.
In fact, according to the generalized conjecture,
one can exclude the instances with $r =2^n$ from $H$,
or, even if one includes such instances in $H$,
such rare instances  do not affect the generalized index $p$
of Sec.~\ref{sec:p}
because it is defined not by $\Theta$ but by $\overline{\Theta}$.

\subsection{Further extention to Grover's quantum search algorithm}
\label{sec:conj-Grover}

Shor's factoring algorithm \cite{Shor}
is a representative algorithm for structured problems \cite{NC}.
For this algorithm,
Ref.~\cite{US04} supported the above conjecture.

On the other hand, a representative algorithm for unstructured problems
is Grover's quantum search algorithm \cite{Grover,NC}.
Hence, it is tempting to examine the conjecture in Grover's algorithm.
However,
we cannot apply the conjecture (even in the above generalized form)
directly to Grover's algorithm
because Eq.~(\ref{def:lqs}) is not satisfied,
i.e.,
it does not achieve exponential speedup.
Nevertheless, it is often argued that the quadratic speedup of
Grover's algorithm is significant \cite{NC}.
Furthermore,
Grover's algorithm is known to be optimal,
i.e.,
no quantum algorithm is faster than Grover's algorithm
by more than a Poly$(L)$ factor in solving the search problem \cite{NC}.
It is therefore very interesting to examine the conjecture, if possible,
for Grover's algorithm.
To make it possible, we here extend the conjecture further to
Grover's algorithm.
Its correctness for Grover's algorithm will be proved in the next section.

Grover's search problem is
the problem of finding a solution to the equation $f_L(x) = 1$
among $N=2^L$ possibilities, where $f_L(x)$ is a function,

f_L: \{0,1\}^{L} \mapsto \{0,1\}.
$
Let $M$ be the number of solutions, and
$x_1, \cdots, x_M$ be the solutions.
For each $L$, the solutions specify an instance.
That is, $(x_1, \cdots, x_M)$ corresponds to $\nu$, which labels instances
as $i(L,\nu)$.
According to convention, we regard the number of oracle calls
as the computational time.

In extending the conjecture, we note that
the degree of quantum speedup depends on the magnitude of $M$
[see Sec.~\ref{sec:spdup-Grover}].
We here consider the case where
\begin{equation}
M=O(2^{mL}) \quad (0 < m <1),
\label{eq:M=large}\end{equation}
where $m$ is a constant, independent of $L$.
In this case, the degree of quantum speedup is similar
to the case of $M=1$ [see Sec.~\ref{sec:spdup-Grover}],
and hence seems significant.

We extend the conjecture of Sec.~\ref{subsec:conj}
simply by replacing the condition
{\em `if the quantum computer achieves exponential speedup'}
with the relaxed condition
{\em `if the quantum computer achieves  exponential speedup
or it solves the quantum search problem
using Grover's algorithm for the case of Eq.~(\ref{eq:M=large})}'.

\section{Analytic results for Grover's quantum search algorithm}
\label{sec:Grover-analytic}

In this section, we show that the extended conjecture of
Sec.~\ref{sec:conj-Grover} is correct for Grover's algorithm.

\subsection{Notation}
\label{sec:notation_Grover}

We first introduce notation.
We assume that $N (=2^L) \gg M$ (the number of solutions), because
otherwise classical computers could solve the problem quickly.

It seems obvious that an index register, composed of $L$ qubits,
is relevant to Grover's algorithm.
We therefore look only at the index register, although
additional quantum circuits would be present in real quantum computers
(see discussions in Sec.~\ref{subsec:conj}).
For each instance $i(L, \nu)$, where
$\nu=(x_1, \cdots, x_M)$ (see Sec.~\ref{sec:conj-Grover}),
we put
\begin{eqnarray}
| \alpha(L, \nu) \rangle &\equiv&
{1 \over \sqrt{N-M}} \sum_{x \, (\neq x_1, \cdots, x_M)} | x \rangle,
\label{eq:alpha}\\
| \beta(L, \nu) \rangle &\equiv&
{1 \over \sqrt{M}} \sum_{x \, (= x_1, \cdots, x_M)} | x \rangle.
\label{eq:beta}\end{eqnarray}
Then the state $| \psi_0(L) \rangle$ just after
the first Hadamard transformation (HT)
(see Sec.~\ref{sec:simulation})
is represented as \cite{NC}
\begin{eqnarray}
| \psi_0(L) \rangle
&=&
| \rightarrow \rightarrow \cdots \rightarrow \rangle
\nonumber\\
&=&
\cos {\theta \over 2} \ | \alpha(L, \nu) \rangle
+
\sin {\theta \over 2} \ | \beta(L, \nu) \rangle,
\label{eq:psi0=}
\end{eqnarray}
where $| \rightarrow \rangle \equiv (|0 \rangle + |1 \rangle)/\sqrt{2}$,
and the angle $\theta$ is given by
\begin{equation}
\cos {\theta \over 2} =
\sqrt{N - M \over N}.
\end{equation}
Let $\hat O(L, \nu)$ be the oracle operator;
\begin{equation}
\hat O(L, \nu) |x \rangle
=
\begin{cases}
- |x \rangle & (x= x_1, \cdots, x_M), \\
|x \rangle & (\mbox{otherwise}).
\end{cases}
\end{equation}
The Grover iteration
\begin{equation}
\hat G(L, \nu) = \left[
2 | \psi_0(L) \rangle \langle \psi_0(L)| - \hat I(L) \right]
\hat O(L, \nu)
\end{equation}
performs the rotation by angle $\theta$ in the direction
$| \alpha(L, \nu) \rangle \to | \beta(L, \nu) \rangle$
in the two-dimensional subspace spanned by
$| \alpha(L, \nu) \rangle$ and $| \beta(L, \nu) \rangle$.
The state $| \psi_k(L, \nu) \rangle$
after $k$ ($=0, 1, 2, \cdots$) iterations is therefore given by  \cite{NC}
\begin{eqnarray}
| \psi_k(L, \nu) \rangle
&=&
\hat G(L, \nu)^k | \psi_0(L) \rangle
\nonumber\\
&=&
\cos \left( {2k + 1 \over 2} \theta \right) | \alpha(L, \nu) \rangle
+
\sin \left( {2k + 1 \over 2} \theta \right) | \beta(L, \nu) \rangle.
\label{eq:G^kpsiHT=}
\end{eqnarray}
Hence, by repeating the Grover iteration
\begin{equation}
R(L) \equiv \left\lceil
\left(\arccos \sqrt{M/N} \right) /\theta \right\rceil
\simeq \left\lceil {\pi \over 4} \sqrt{N \over M}  \right\rceil
\end{equation}
times, the state evolves into
$
| \psi_{R(L)}(L, \nu) \rangle
\simeq
| \beta(L, \nu) \rangle
$.
Here, $\lceil a \rceil$ denotes
the smallest integer among those larger than or equal to $a$.
By observing this state in the computational basis,
one can find a solution to the search problem with probability
$\gtrsim 1/2$.
The range of $k$ is thus
\begin{equation}
0 \leq k \leq R.
\end{equation}

\subsection{$M$ dependence of degree of speedup}
\label{sec:spdup-Grover}

According to convention, we regard the number of oracle calls
as the computational time.
Then, apart from ${\rm Poly}(L)$ factors,
\begin{equation}
T_Q(L,\nu) = R(L) = \Theta\left( \sqrt{N/M} \right)
\label{eq:Q-grover}\end{equation}
for all instances.
In contrast,
for classical computers
there exist infinitely many instances (as $L \to \infty$) such that
\begin{equation}
T_C(L,\nu)= \Theta(N/M).
\label{eq:Qwst-grover}\end{equation}
The quadratic speedup of $T_Q(L,\nu)$ over $T_C(L,\nu)$
is significant when $M$ is small enough
(such as $M= {\rm Poly}(L)$).
On the other hand, {\em no} quantum speedup is achieved
when $M$ is too large such as $M= N/{\rm Poly}(L)$
because then classical computers can solve the problem efficiently.

To be specific,
we limit ourselves to the case of Eq.~(\ref{eq:M=large}), i.e., where
$M=O(2^{mL})$ [$m$ is independent of $L$ and $0 < m <1$],
because almost all interesting applications of Grover's algorithm
would belong to this case.
For example, this includes the case of $M= {\rm Poly}(L)$,
whereas the uninteresting case of $M= N/{\rm Poly}(L)$ is excluded.

When $M=O(2^{mL})$,
we find
\begin{equation}
T_C(L,\nu) = \Theta \left(2^{(1-m)L} \right)
\end{equation}
for some infinitely many instances, and
\begin{equation}
T_Q(L,\nu) = \Theta \left(\sqrt{2^{(1-m)L}} \right)
\end{equation}
for all instances.
This quadratic speedup
seems to be as significant as that of $M=1$.

\subsection{Family of states to evaluate $q$ or $p$}

As discussed above,
the degree of speedup
depends on how the number of solutions $M$ behaves asymptotically as
a function of $L$.
For clarity,
we treat
different asymptotic forms of $M$ separately
when investigating our extended conjecture.

Suppose that we are given a functional form of $M$,
which asymptotically
satisfies inequality (\ref{eq:M=large}),
such as
$M=L^2$.
Then, it will turn out that the set of all instances
is an appropriate choice of $H$ of Sec.~\ref{subsec:conj};
\begin{equation}
H = \{ i(L,\nu) \ | \mbox{ all } L, \mbox{ all $\nu$} \}.
\label{eq:allinstances}\end{equation}
To construct a family of states $F_{k_*}(H)$, Eq.~(\ref{eq:F}),
we specify the number $k_*$ as follows.
Since Grover's algorithm simply repeats the Grover iteration
$R(L)$ times, it seems natural to take $k_* = \lceil R(L)/2 \rceil$.
More generally, it seems reasonable to take
\begin{equation}
k_* = \lceil R(L)/s \rceil,
\label{eq:k*.Grover}\end{equation}
where $s$ is a positive constant independent of $L$.
It will turn out that this choice of $k_*$ is indeed appropriate.
A family of states $F_{k_*}(H)$ is thus constructed,
for a given $k_*$, as
\begin{eqnarray}
F_{k_*}(H)
=
\{
| \psi_{k_*}(L,\nu) \rangle
\ |  \mbox{ all } L, \mbox{ all $\nu$}
\}.
\label{eq:F.Grover}
\end{eqnarray}
Since all states of this family are pure states, we will evaluate
the index $p$ rather than $q$.

\subsection{When $M=1$}\label{sec:M=1}

When $M=1$,
Eq.~(\ref{eq:alpha}) reduces to
$| \alpha(L,\nu) \rangle
= | \psi_0(L) \rangle + O(1/\sqrt{N})
= | \psi_0(L) \rangle + O(1/2^{L/2})
$,
whereas Eq.~(\ref{eq:beta}) reduces to
$| \beta(L,\nu) \rangle = | x_1 \rangle$.
Since $| \psi_0(L) \rangle$ and $| x_1 \rangle$ are product states,
we find that $p=1$ for (the families composed, respectively, of)
$| \psi_0(L) \rangle$, $| \alpha(L,\nu) \rangle$
and $| \beta(L,\nu) \rangle$.
Hence, $p=1$ for (the families of) the initial and final states.

For intermediate states $| \psi_k(L,\nu) \rangle$'s
of interest,
it is convenient to investigate
$\hat M_x \equiv \sum_l \hat \sigma_x(l)$
(which corresponds to the $x$ component of the total magnetization of
magnetic substances).
Note here that
in order to show that $p=2$
it is sufficient to find {\em one} additive observable
(which in this case is $\hat M_x$)
which fluctuates macroscopically.
From Eq.~(\ref{eq:G^kpsiHT=}), we find
\begin{eqnarray}
\langle \psi_k(L,\nu) | \hat M_x | \psi_k(L,\nu) \rangle
&=&
\cos^2 \left( {2k + 1 \over 2} \theta \right) L + O(1),
\label{eq:pkMxpk}\\
\langle \psi_k(L,\nu) | \hat M_x^2 | \psi_k(L,\nu) \rangle
&=&
\cos^2 \left( {2k + 1 \over 2} \theta \right) L^2 + O(L).
\label{eq:pkMx2pk}\end{eqnarray}
Hence,
\begin{eqnarray}
\langle \psi_k(L,\nu) | ( \Delta \hat M_x )^2 | \psi_k(L,\nu) \rangle
&=&
{1 \over 4} \sin^2 \left( (2k + 1) \theta \right) L^2
+ O(L).
\label{eq:pkMx2pk-2}\end{eqnarray}
For all states in the family $F_{k_*}(H)$ of Eq.~(\ref{eq:F.Grover}), we thus find
\begin{equation}
\langle \psi_{k_*}(L,\nu) | ( \Delta \hat M_x )^2 | \psi_{k_*}(L,\nu) \rangle
\simeq
{1 \over 4} \sin^2 \left( {\pi \over s} \right) L^2
+ O(L).
\label{eq:Mx2_Fk*}\end{equation}
Since $s$ is independent of $L$, the right-hand side is $\Theta(L^2)$,
and thus $p=2$ for this family.

\subsection{When $M=$ Poly$(L)$}\label{sec:M=Poly(L)}

We now consider the case where $M \geq 2$.
In this case, unlike the case of $M=1$,
$| \beta(L,\nu) \rangle$ has $p=2$ for some instances.

For example, suppose that $M=2$ and the two solutions for
some instance $\nu$ are
$x_0 \equiv 1010 \cdots 10$ and $x_1 \equiv 0101 \cdots 01$.
Then, $p=2$ for
$| \beta(L,\nu) \rangle = (| x_0 \rangle + | x_1 \rangle)/ \sqrt{2}$
(i.e., for the family $\{ | \beta(L,\nu) \rangle \ | \ \mbox{all } L \}$),
because
$\langle \beta(L,\nu) | ( \Delta \hat M_z^{\rm st} )^2 | \beta(L,\nu) \rangle = \Omega(L^2)$.
Here, $\hat M_z^{\rm st} \equiv \sum_l (-1)^l \hat \sigma_z(l)$,
which corresponds to the $z$ component of the staggered magnetization
of antiferromagnets.
On the other hand,
if $x_0 \equiv 0000 \cdots 00$ and $x_1 \equiv 0000 \cdots 01$
for another instance $\nu'$
then $p=1$ for
$| \beta(L,\nu') \rangle = (| x_0 \rangle + | x_1 \rangle)/ \sqrt{2}$.

Therefore, {\em when $M \geq 2$,
$p$ of the final state depends on the instance, i.e.,
on the nature of the solutions.
}
(On the other hand, it is clear that
$p=1$ for the initial state.)

To compute $p$ of states in intermediate stages of computation
for $M>2$,
we first consider the case where $M=$ Poly$(L)$.
In this case,
Eq.~(\ref{eq:pkMx2pk-2}) still holds
for $| \psi_k(L,\nu) \rangle$ with $k \geq 1$,
and thus the discussion following Eq.~(\ref{eq:pkMx2pk-2}) also holds.
Therefore,
we again find that
$p=2$ for the family $F_{k_*}(H)$ of Eq.~(\ref{eq:F.Grover}).

We can obtain the same conclusion when
$M=O(2^{L^\kappa})$, where $\kappa$ is a constant independent of $L$
and $0<\kappa<1$.
Instead of showing this, we shall derive
the same conclusion when $M$ is even larger in the next subsection.

\subsection{When $M=\Theta(2^{mL})$}\label{sec:M=2mL}

We now study the case where
\begin{equation}
M=\Theta(2^{mL}) \quad (0 < m <1),
\end{equation}
where $m$ is independent of $L$.
This is the upper limit of $M$ that satisfies condition (\ref{eq:M=large}).

As mentioned above,
$p$ of the final state depends on the nature of the solutions
(whereas $p=1$ for the initial state).
Since this might not be trivial when $M$ is as large as
$\Theta(2^{mL})$, we give an example
for $M=2^{L/2}=\sqrt{N}$.
Suppose that the solutions for some instance $\nu$
are as follows;
$x_j = j$ for $j=1, 2, \ldots, \frac{1}{2}\sqrt{N}$
whereas $x_j$'s for $j \geq \frac{1}{2}\sqrt{N}+1$
are multiples of
$2\sqrt{N}$ (less than $N$). Then
\begin{eqnarray}
 |\beta(L,\nu) \rangle
&=&
\frac{1}{\sqrt{2M}}\sum_{y=1}^{\frac{1}{2}\sqrt{N}}|00\cdots
  0y\rangle
+\frac{1}{\sqrt{2M}}\sum_{z=0}^{\frac{1}{2}\sqrt{N}-1}|z0\cdots
  00\rangle \nonumber \\
 &=&
\frac{1}{\sqrt{2}}
|00\cdots 0 \rightarrow \rightarrow \cdots \rightarrow \rangle
+\frac{1}{\sqrt{2}}
|\rightarrow  \rightarrow \cdots \rightarrow 00\cdots 0\rangle
+O(1/\sqrt{N}).
\end{eqnarray}

Since
$\langle \beta(L,\nu) |(\Delta \hat{M'}_x)^2|\beta(L,\nu) \rangle =O(L^2)$,
where
$\hat{M'}_x \equiv \sum_{l=1}^{L/2}\hat{\sigma
}_x(l)+\sum_{l=L/2+1}^{L}\hat{1 }(l)$,
we find that $p=2$ for this state.
By contrast,
if $x_j = j$ for all $j$ for another instance $\nu'$,
then
$ |\beta(L,\nu') \rangle
= |00 \cdots \rightarrow \rightarrow \cdots \rightarrow \rangle$,
for which $p=1$.

To compute $p$ of states in intermediate stages of computation,
we note that
$| \alpha(L,\nu) \rangle = | \psi_0(L) \rangle + O(2^{-(1-m)L/2})$
when $M = \Theta(2^{mL})$. Hence,
abbreviating
$| \psi_k(L,\nu) \rangle, |\alpha(L,\nu) \rangle, |\beta(L,\nu) \rangle$
to
$| \psi_k \rangle, |\alpha \rangle, |\beta \rangle$, respectively,
we find
\begin{eqnarray}
 \langle \psi_k |\hat{M}_x | \psi_k \rangle &=& \cos
  ^2\left( \frac{2k+1}{2}\theta \right)
\langle \alpha |\hat{M}_x|\alpha \rangle
  +\sin
  ^2\left( \frac{2k+1}{2}\theta \right)
\langle \beta |\hat{M}_x|\beta \rangle
  +O(1),
\\
   \langle \psi_k |\hat{M}^2_x | \psi_k \rangle &=&
    \cos ^2\left( \frac{2k+1}{2}\theta \right)\langle \alpha |\hat{M}^2_x|\alpha \rangle
  +\sin
  ^2\left( \frac{2k+1}{2}\theta \right)\langle \beta |\hat{M}^2_x|\beta \rangle +O(1),
  \end{eqnarray}
which yield
\begin{eqnarray}
\langle \psi _k|(\Delta \hat{M}_x)^2|\psi _k\rangle &=&\cos
  ^2\left( \frac{2k+1}{2}\theta \right)\langle \alpha |(\Delta \hat{M}_x)^2|\alpha \rangle
  +\sin ^2\left( \frac{2k+1}{2}\theta \right)\langle \beta |(\Delta \hat{M}_x)^2|\beta
  \rangle \nonumber \\
  &+&\frac{1}{4}\sin ^2((2k+1)\theta )\big{(} \langle
  \alpha |\hat{M}_x|\alpha \rangle -\langle \beta |\hat{M}_x|\beta
  \rangle \big{)}^2+O(L).
\end{eqnarray}
As shown in Appendix \ref{appendix_matsuzaki},
$\langle \alpha |\hat{M}_x|\alpha \rangle =L +O(1)$
and $\langle \beta |\hat{M}_x|\beta \rangle =K L$,
 where $K$ is independent of $L$ and $0<K<1$.
Hence, for $k_*$ of Eq.~(\ref{eq:k*.Grover}), we find
$\langle \psi_{k_*}|(\Delta \hat{M}_x)^2|\psi _{k_*} \rangle =O(L^2)$.
Therefore, $p=2$
for
the family $F_{k_*}(H)$ of Eq.~(\ref{eq:F.Grover}).

We have thus proved that
the extended conjecture of Sec.~\ref{sec:conj-Grover}
is correct for Grover's algorithm.

\subsection{Intermediate values of $p$}

As the quantum computation proceeds (i.e., as $k$ is increased),
$p$ increases from $1$ for the initial state $|\psi_0(L) \rangle$
to $2$ for $|\psi_{k_*}(L,\nu) \rangle$.
In the transient steps,

$p$ takes intermediate values between $1$ and $2$.

Such intermediate values
are taken also, e.g., by states of quantum many-body systems
at critical points of continuous phase transitions,
where two-point correlation functions decay according to power laws
as a function of the distance between two points.
Hence, one might expect some universal properties
of $p$, as critical exponents in continuous phase transitions have.

For states of quantum computers in the transient steps, however,
the intermediate values of $p$ are not universal;
they depend on details such as the nature of the solutions.
Since we are not interested in such non-universal values of $p$
in this paper,
we have focused on the universal result,
which is directly related to our conjecture, that
$p=2$ for
the family composed of $|\psi_{k_*}(L,\nu) \rangle$'s.

\section{Evolution of quantum correlations in Grover's quantum search algorithm}
\label{sec:Grover-numerical}

As summarized in Sec.~\ref{sec:p.and.q},
the index $p$
is calculated from two-point correlations of local operators.
For pure states, $p=2$ if they have
two-point correlations of $\overline{\Theta}(1)$ between
$\Theta(L^2)$ pairs of sites.
[As discussed in Sec.~\ref{sec:Pofpq},
for pure states such strong two-point correlations
imply a strong $L$-point correlation.]
As discussed in Sec.~\ref{sec:VCM},
the existence of such correlations can be detected by
the asymptotic behavior (as $L \to \infty$)
of the maximum eigenvalue $e_{\rm max}$
of the VCM,
because, roughly speaking, $L e_{\rm max}$ is
proportional to the number of pairs of sites whose
correlation is of $\overline{\Theta}(1)$ \cite{rough}.

Although $p$ is simpler and more convenient for stating the conjecture,
$e_{\rm max}$ has more detailed information about
two-point correlations.
[For example, a state with $e_{\rm max}=L$ has stronger
two-point correlations than one with $e_{\rm max}=L/10$,
whereas both states have $p=2$.]
It is therefore interesting to study how
$e_{\rm max}$ evolves as the computation proceeds
from a small value (corresponding to $p=1$) at the initial state
to larger values.
It describes how two-point correlations evolves
(until a strong $L$-point correlation develops for $p=2$, as
discussed in Sec.~\ref{sec:Pofpq}).

In this section,
to investigate the evolution of $e_{\rm max}$,
we simulate numerically a quantum computer that performs
Grover's algorithm.
In the simulation, we study more states than
those studied in the previous section,
where
we have studied
$| \psi_k(L,\nu) \rangle =\hat G^k(L,\nu) | \psi_0(L) \rangle$
($k = 0, 1, 2, \cdots, R(L)$).
In actual quantum computations,
the Grover iteration
$\hat G(L,\nu)$
may be realized, e.g., as a series of local
and pair-wise operations \cite{NC}.
Hence, many intermediate states appear between
the computational steps corresponding to
$| \psi_k(L,\nu) \rangle$ and $| \psi_{k+1}(L,\nu) \rangle$.
Although it was sufficient to investigate $| \psi_k(L,\nu)$'s
for confirming the conjecture,
we also study such intermediate states
to see more details.

We simulate two cases, $M=1$ and $M=2$,
because these cases are most fundamental.
The solution(s) $x_1$ (and $x_2$) is chosen randomly. We have
confirmed that this random choice of a solution(s)
makes no significant difference on the
results of the numerical simulations presented below.

\subsection{Formulation of simulation}\label{sec:simulation}

We explain our simulation for the case of $M=1$.
Simulation for $M=2$ has also been performed similarly.

Since $M=1$, we can simply take $\nu=x_1$.
As in the previous section,
we consider the index register composed of $L$ qubits.
The register is initially set to be in the following product state;
\begin{equation}
|\psi_{\rm init}(L) \rangle = |00 \cdots 0 \rangle.
\label{psi0_G}\end{equation}
Firstly, the HT is performed
by successive applications of the Hadamard gate on individual qubits,
and the quantum state evolves into
$|\psi_0(L) \rangle$ of Eq.~(\ref{eq:psi0=}).
Then we apply the Grover iteration
$\hat{G}(L,\nu)$,
which consists of two HTs,
an oracle operation $\hat{O}(L,\nu)$,
and a conditional phase shift $\hat{P}(L)$ \cite{NC};
\begin{equation}
\hat{P}(L) |x \rangle
=
\begin{cases}
|00 \cdots 0 \rangle & (x=0), \\
-|x \rangle & (x>0).
\end{cases}
\end{equation}

Each HT requires $L$ operations of
the Hadamard gate.
The oracle $\hat{O}(L,\nu)$
requires
its own workspace qubits and computational time.
However, since the oracle is not a proper part of the Grover's algorithm,
we simulate the operation of $\hat{O}(L,\nu)$ as a one-step operation,
and its workspace is not included in the simulation.
The execution of $\hat{P}(L)$
requires $\Omega(L)$ pairwise unitary operations.
For simplicity, however, we simulate $\hat{P}(L)$ as
a one-step operation.
Hence, each Grover iteration is simulated by
$2L+2$ steps of operations.

After application of the Grover iterations $R(L)$ times,
the state $|\psi_0(L) \rangle$ evolves into
\begin{equation}
\hat{G}^{R(L)}(L,\nu)|\psi_0(L) \rangle
=|\psi_{R(L)}(L,\nu)\rangle
\simeq | \beta(L,\nu) \rangle
= |x_1 \rangle.
\label{GRpsi0}\end{equation}
Finally, by observing this state
one can obtain the solution
$x_1$ with a sufficiently high probability.
We do not simulate this measurement process.
The total computational time (steps) $T_Q(L,\nu)$ in our simulation is thus
\begin{equation}
T_Q(L,\nu)=L+ (2L+2)R(L) = \Theta(L\sqrt{2^{L}})
\end{equation}
for all $\nu$.
This is larger than $T_Q(L,\nu)$ of Sec.~\ref{sec:Grover-analytic}
only by a polynomial factor.
For each instance $\nu$,
$T_Q(L,\nu)$ different states,
including $| \psi_k(L, \nu) \rangle$'s of Sec.~\ref{sec:Grover-analytic},
appear during computation.

In our conjecture,
we have
allowed
(i) looking only at a subsystem
and (ii) all possible redefinition of local sites.
For the present model of a quantum computer, however,
we have confirmed
(from the following results and the results of the previous section)
that they are unnecessary.
That is, in the present model,
we can confirm the extended conjecture
by simply calculating the index $p$
of states of the index register.

To find states with $p=2$,
we calculate
$e_{\rm max}(L,\nu)$ of Sec.~\ref{sec:VCM}.
By plotting the $L$ dependence of $e_{\rm max}(L,\nu)$,
we can determine the value of $p_e$ through Eq.~(\ref{def:p_e}).
When states with $p_e=2$ are found,
they have $p=2$
because, as discussed in Sec.~\ref{sec:VCM},
if $p_e=2$ then $p=2$ (and vice versa).
We will also plot how
$e_{\rm max}(L,\nu)$ (for fixed $L$) grows and decays as
the quantum computation proceeds
because it is instructive and impressive.

In defining the VCM of Eq.~(\ref{def:VCM}),
we take $\hat b_\alpha(l)=\hat \sigma_\alpha(l)$ (Pauli operator on site $l$
and $\alpha=1,2,3$), i.e,
\begin{equation}
V_{l \alpha, l' \alpha'}(L,\nu)
\equiv
\langle \Delta \hat \sigma_\alpha(l)
\Delta \hat \sigma_{\alpha'}(l') \rangle_{L \nu}.
\label{def:V-2}\end{equation}
In the following,
for the sake of conciseness,
we will often denote
$e_{\rm max}(L,\nu)$, $V_{l \alpha, l' \alpha'}(L,\nu)$, and so on
simply by $e_{\rm max}$, $V_{l \alpha, l' \alpha'}$, and so on.

\subsection{Results of simulation for $M=1$}\label{ss:nr_Grover}

Figure \ref{Grover9} plots evolution of
$e_{\rm max}$
for $L=8, 9, 10, 12, 14$ and $M=1$,
when $x_1 = 19, 388, 799, 1332, 9875$, respectively.
It is seen that on the whole the curves are exponentially expanded
along the horizontal axis as $L$ is increased.

Figure \ref{initial_G} is a magnification from the $1$st to $40$th steps
for $L=8$,
whereas a magnification from the $1005$th to $1155$th steps for $L=14$
is shown in Fig.~\ref{middle_G}.
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.6\linewidth]{fig1.eps}
\end{center}
\caption{
The maximum eigenvalue $e_{\rm max}$ of the VCM
of quantum states appearing in Grover's quantum search algorithm
for $L=8, 9, 10, 12, 14$
when $x_1 = 19, 388, 799, 1332, 9875$, respectively,
as functions of the step of the algorithm.
The horizontal line represents
the value of $e_{\rm max}$ for product states,
$e_{\rm max}=2$.}
\label{Grover9}
\end{figure}
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.6\linewidth]{fig2.eps}
\end{center}
\caption{
A magnification of Fig.~\ref{Grover9},
from the $1$st to $40$th steps for $L=8$.
Here,
$\hat O$ and $\hat P$ represent
the oracle operation and conditional phase shift, respectively,
in a single Grover iteration  $\hat G$.
}
\label{initial_G}
\end{figure}
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.6\linewidth]{fig3.eps}
\end{center}
\caption{
A magnification of Fig.~\ref{Grover9},
from the $1005$th to $1155$th steps for $L=14$.
Here, $\hat O$ and $\hat P$ represent
the oracle operation and conditional phase shift, respectively,
in a single Grover iteration  $\hat G$.
}
\label{middle_G}
\end{figure}

It is seen that
$e_{\rm max}=2.00$ for all states from
$|\psi_{\rm init} \rangle$ to $|\psi_0 \rangle$,
i.e., during the initial HT
(from the $1$st to $8$th steps in Fig.~\ref{initial_G},
denoted as `HT').
This is because all these states are product states,
for which we can easily show that $e_{\rm max}=2$
(Appendix \ref{app:emax.product.state}).
When the stage of Grover iterations begins,
$e_{\rm max}$ grows gradually, as seen from
Figs.~\ref{Grover9} and \ref{initial_G}.
In each Grover iteration,
Figs.~\ref{initial_G} and \ref{middle_G} show that
$e_{\rm max}$ changes when the oracle operator $\hat O$ is operated,
whereas it is kept constant during the subsequent
HT.
Then, it changes again when $\hat P$ is operated,
whereas it is kept constant again
during the subsequent HT.
As the Grover iterations are repeated,
$e_{\rm max}$ (hence, quantum correlation)
continues to increase as a whole,
until it takes the maximum value after about $R(L)/2$
times applications of $\hat G$.
Further applications of $\hat G$
reduce $e_{\rm max}$,
as seen from Fig.~\ref{Grover9},
toward $e_{\rm max} \simeq 2.00$ for $|\psi_{R(L)}\rangle$,
which is approximately a product state as seen from Eq.~(\ref{GRpsi0}).

These results indicate that
our construction of the family of states,
Eqs.~(\ref{eq:k*.Grover}) and (\ref{eq:F.Grover}),
is natural.
Although we have already shown in Sec.~\ref{sec:Grover-analytic}
that $p=2$ for such a family,
it is instructive to plot $e_{\rm max}(L,\nu)$
of $| \psi_{k_*}(L,\nu) \rangle$ as a function of $L$
when the solution $x_1$ is randomly chosen
(i.e., an instance $\nu$ is randomly chosen) for each $L$.
Figure \ref{maxfluG} plots
$e_{\rm max}$'s of
$|\psi_{\lceil R/2 \rceil} \rangle$,
$|\psi_{\lceil R/3 \rceil} \rangle$ and $|\psi_{\lceil R/4 \rceil} \rangle$
for such randomly-chosen $x_1$
as functions of $L$.
[We have confirmed that almost identical
curves are obtained for other choices of $x_1$ as well.]
Since $e_{\rm max}$'s tend to be proportional to $L$ for large $L$,
we can confirm that $p=p_e=2$.

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.6\linewidth]{fig4.eps}
\end{center}
\caption{
$e_{\rm max}$'s of $|\psi_{\lceil R/2 \rceil} \rangle$ (diamonds),
$|\psi_{\lceil R/3 \rceil} \rangle$  (crosses)
and $|\psi_{\lceil R/4 \rceil} \rangle$ (squares),
as functions of $L$.
They all show that $p=p_e=2$.
The dotted lines are the guides to the eyes,
whereas the horizontal line represents
the value of $e_{\rm max}$ for product states, $e_{\rm max}=2$.
}
\label{maxfluG}
\end{figure}

\subsection{Results of simulation for $M=2$}\label{ss:nr_GroverM=2}

When $M=2$,
the result of Sec.~\ref{sec:M=Poly(L)} indicates that
$p=2$ for most states in the Grover iteration processes
whereas $p$ of the {\em final} state depends on the nature of the solutions.
Figure \ref{GroverM=2} illustrates this clearly, where
we have plotted evolution of
$e_{\rm max}$
for two cases, $p=2$ (profile 1) and
$p=1$ (profile 2) for the final state.
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.6\linewidth]{fig5.eps}
\end{center}
\caption{
The maximum eigenvalue $e_{\rm max}$ of the VCM
of quantum states appearing in Grover's quantum search algorithm
for $L=10$ and $M=2$,
when $x_1 = 2, x_2=1023$ (profile 1) and when
$x_1 = 511, x_2=512$ (profile 2),
as functions of the step of the algorithm.
The horizontal line represents
the value of $e_{\rm max}$ for product states, $e_{\rm max}=2$.
}
\label{GroverM=2}
\end{figure}
For
$|\psi_{\lceil R/2 \rceil} \rangle$,
$|\psi_{\lceil R/3 \rceil} \rangle$ and $|\psi_{\lceil R/4 \rceil} \rangle$,
on the other hand,
we obtain results similar to Fig.~\ref{maxfluG} for both cases.
Hence, $p=2$ for these states.
This result visualizes how our extended conjecture holds when $M \geq 2$.

\section{discussions and summary}\label{sec:dc}

We have studied the conjecture that
superposition of macroscopically distinct states would be necessary for
significant speedup of quantum computers over classical computers.
This conjecture was previously supported for a circuit-based quantum computer
performing Shor's factoring algorithm.
To treat general algorithms and models,
we have generalized the indices $p$ and $q$ for
superposition of macroscopically distinct states.
We then generalize the conjecture
in such a way that it is applicable unambiguously
to general models if a quantum algorithm achieves
an exponential speedup.
We further extend the conjecture to the speedup
achieved by Grover's quantum search algorithm.
This extended conjecture is proved to be correct for Grover's algorithm.
Since Grover's and Shor's algorithms are representative ones for
unstructured and structured problems,
respectively,
the present results and the results of Ref.~\cite{US04}
support strongly the conjecture.
To see details,
we have also presented, by numerical simulation,
how quantum correlation evolves and
the superposition of macroscopically distinct states
develops as the computation proceeds.

Jozsa and Linden previously showed that
entanglement over a cluster whose size is
larger than $O(1)$ is necessary
for an exponential speedup \cite{JL}.
For $p=2$, on the other hand,
entanglement over a cluster whose size is
larger than $O(L)$ is necessary \cite{SM02,MSS05}.
The present conjecture imposes a stronger condition in this sense.

Moreover,
Vidal showed that a necessary condition for an exponential
speedup is that
the amount of the bipartite entanglement
between one part and the rest of the qubits
increases with $L$ \cite{Vidal}.
The bipartite entanglement which was studied by him
is totally different from
the entanglement possessed by
superposition of macroscopically distinct states.
Therefore,
the {\em simultaneous} requirement (for speedup over classical computations)
of Vidal's condition and
{\em and}
the present conjecture
is much stronger than the requirement of either one of them.
That is, for quantum speedups {\em both}
superposition of macroscopically distinct states
{\em and}
a sufficient amount of the bipartite entanglement
are necessary.

It is also interesting to explore relation
between our results and the problem of
time-optimal quantum evolution \cite{Carlini2006, Hosoya}.
In the latter case the optimal evolution requires
large fluctuation of Hamiltonian,
while in the former fast quantum
computations require states with
large fluctuations of additive operators.
This suggests a possible relation
between the quantum speedup and
the optimal evolution \cite{Hosoya}.

\begin{acknowledgments}

We thank M. Koashi and A. Hosoya
for valuable discussions.
This work was supported by
PRESTO, Japan Science and Technology Corporation,
by Grant-in-Aid for
Scientific Research No.\ 18-11581,
and by KAKENHI No.\ 22540407.

\end{acknowledgments}

redpajama_set_name: RedPajamaArXiv


And to all you retailers out there, here is a very interesting article about how to get the best out of your selling opportunities with the help of digital signage as a training tool.
Short term, casual staff that help out during the Xmas period and Sales often lack product knowledge or basic sales techniques. Why not create an engaging, memorable training tool with the help of an interactive digital kiosk? Use the kiosk to display product videos, explain product features and then test knowledge with a quiz at the end.
Ask us about hiring an interactive digital signage training kiosk to boost your Sales campaign this Christmas.


"Bolivia Geography Stats, NationMaster." 1961-2014. <http://www.nationmaster.com/country-info/profiles/Bolivia/Geography>.
"Bolivia Geography Stats", NationMaster [Internet]. 1961-2014. Avaliable from: <http://www.nationmaster.com/country-info/profiles/Bolivia/Geography>.
"Bolivia Geography Stats", NationMaster. Avaliable at: nationmaster.com. Assessed 1961-2014.
Bolivia ranked #14 for area > total amongst Christian countries in 2013.
Bolivia ranked first for area > land per 1000 amongst Former Spanish colonies in 2008.
Bolivia ranked #21 for area > water amongst Hot countries in 2013.


The entry 'Animal Farm' was posted on June 6th, 2011 at 8:59 am	and is filed under Communication, Courage, Esoteric Minutiae. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.


"Dear Fall on Daufuskie Island, you are never close enough" – I said that!
1. Keep swimming! Enjoy the cooler less humid air and the continuation of warm very swimmable water with an average sea temperature of 80 degrees.
2. Fishing is on fire with massive hungry schools of speckled sea trout and beautiful redfish surrounding the island. If you can't catch fish on Daufuskie Island in October, you should probably find another hobby. Of course, you can always charter a trip if you need a little help.
3. With kids back in school, our island has far less visitors making Daufuskie feel like a very private island which is perfect for sunrise and sunset walks on the beach. Couples, the island is all yours!
4. Visit the islands artisans which consist of a pottery studio, metal art gallery, indigo dying studio, woodworking shop and a soap maker. All small businesses are still fully open during fall months on Daufuskie!
5. Save money on Daufuskie Island short term rentals as rates typically drop a bit in October.
6. Go have a coffee or espresso at School Grounds coffee house where you can almost guarantee learning great things about the island from Daufuskie locals.
7. Have lunch at Lucy Bell's or dinner at the Daufuskie Island Crab Company, both Daufuskie eateries are open year round.
8. Go to www.tourdaufuskie.com to see what types of locally guided tours are available. Usually Tour Daufuskie's tours have fewer people on them in the fall which offer a very intimate and personal experience that you could never get during the summer months.
9. Rent kayaks or paddle boards and explore the rivers and creeks less traveled. Kayak rentals also are available through Tour Daufuskie.
10. Bring your bikes, the weather is great. We don't recommend bikes as a primary means of touring Daufuskie due to how spread out everything is. However, if you are lucky enough to be renting a home on the island, bring a bike or make sure you rent a place that offers bikes. Bicycling is a great way to take short explorative trips around Daufuskie.
11. Relax and enjoy the peace and quiet. This makes every list of our "things to do on Daufuskie". Life is hectic and while your on a Daufuskie Island vacation, take advantage of what we don't have, hustle or bustle!


South Africa's lost diamond, Charlize Theron, is this month's GQ cover star. But behind her superhuman beauty, what's she like to photograph?
We asked British photographer Alexi Lubomirski to tell us during the shoot with the Mad Max: Fury Road star, which took place at Milk Studios in Los Angeles.
She is the only British woman to win one of the science Nobel prizes.


You've been assigned the task of designing and producing an embedded device. You've been given time, cost and size constraints that impact your design. An initial analysis of the requirements leads you to the conclusion that a 32-bit processor with a relatively small amount of RAM and Flash are required. A bit of research shows that an ARM processor with 2MB of external Flash and 2MB of external RAM will meet your cost and size constraints.
Life tests have demonstrated the longevity of an electrostatically actuated capacitive switch of a microelectromechanical systems (MEMS) type suitable for handling radio signals having frequencies of multiple gigahertz. The tests were performed to contribute to understanding of factors that affect the reliability of MEMS switches in general and of how improvements in designs and materials can increase operational lifetimes of MEMS capacitive switches. The tests were based partly on the concept that data obtained in monitoring both high-speed and low-speed switching characteristics provide valuable insight into quantifying the lifetime properties of the switches and enable estimation of switching lifetimes under a variety of operating conditions.
Amethod and apparatus have been conceived for using electrochemical impedance spectroscopy (EIS) for determining rates of corrosion of coupled metals. EIS has been used heretofore for determining rates of corrosion of single metals. However, many structures used in corrosive environments include different metals in electrical contact. Moreover, the concept of using a sacrificial metal to suppress or reduce the corrosion of another metal is applied in some structures. The coupling of two different metals can affect the rates of corrosion of both. Hence, there is a need to extend EIS to coupled metals.
A program of research has addressed a methodology of scaling of flight tests of unmanned air vehicles (UAVs) intended primarily for military use in observing and/or attacking targets on the ground. The main goal of this research is to make it possible to design a model UAV that is suitable for evaluating the performance of a given real UAV or family of UAVs. This research also demonstrates the use of results of computational simulations and ground hardware experiments on models of vehicles other than UAVs to predict performances of UAVs prior to conducting flight tests.
A small-scale combustion-chamber testing facility has been designed and partly built for use in evaluating advanced combustor designs for future gas turbine engines. The specific model combustor for which the facility was designed is an approximation of a planar section of an ultra-compact combustor (UCC). In the full-scale UCC (Figure 1), vanes in an annular cavity are positioned and oriented to cause the combustion gases to flow in a spiral pattern and the resulting centripetal acceleration in the cavity is utilized to increase the speed of combustion and thereby make it possible to design the combustion chamber to be shorter than would otherwise be necessary. In the model combustor, the spiral aspect of the flow is approximated by means of a small flow of air directed perpendicular to a main flow. The design of the facility and the model combustor provides access for off-axis optical (including visual) observation and measurement of cavity-vane interactions. The facility can also be used to test many other combustor models.
The Interactive DataWall (IDW) is a computer-driven, high-definition display, large enough to be visible simultaneously to multiple observers, that presents information from multiple sources and exploits advanced techniques of human/computer interaction and data fusion. The IDW originally was intended for collaborative use by a group of Air Force decision-makers who must consider large amounts of dynamic information (e.g., information pertinent to targeting during battle). Sources of displayed and otherwise utilized information can include sensors on terrestrial vehicles, sensors aboard satellites, databases, and video feeds from remote locations.
Experiments have shown that when a miniature semiconductor diode floats in an aqueous solution and an alternating electric field is applied, (1) the diode rectifies the alternating potential induced between the electrodes, and (2) the resulting pulsating DC potential gives rise to an electro-osmotic flow in the vicinity of the diode and associated force that orients the diode along the electric-field direction, and propels the diode through the water. The propulsive force on the diode is along the electricfield direction and can be toward the cathode or the anode end, depending on the precise nature of the surface charge on the diode and the chemical composition of the solution. It has been proposed to exploit this phenomenon in developing microscale and nanoscale pumps and motors for diverse purposes. The proposal is not as radical as it might first seem: Electro-osmosis in applied DC electric fields has been used to pump liquids in microfluidic devices.
Optical-fiber infrasound sensors (OFISs) are being developed for detecting acoustic pressures in the frequency range from a few millihertz to a few hertz. As explained below, these sensors were conceived to overcome some of the limitations of prior infrasound sensors based on pipe filters connected to microbarographs.
Astudy has been performed to establish a foundation for the analysis, design, and further development of inplane- actuated deformable membrane mirrors for lightweight spaceborne telescopes. It is envisioned that the telescopes, having typical mirror diameters of 20 m or larger, would be stowed compactly for launch and transport, then deployed in orbit around the Earth for use in surveillance of the Earth and in exploration of deep space.


text:
Celebrating over 100 Years
The Infant Welfare Society o f Chicago (IWS) was created by concerned volunteers in response to an alarming infant mortality rate—at the turn of the last century, one out of every ten children died before their first birthday.
The Chicago Milk Commission was established in 1908 to combat the consumption of unpasteurized milk, a common cause of infant death. The Commission set up "milk stations" for dispensing free fresh milk to mothers of infants. In 1911, some of the volunteer nurses, physicians, and women from throughout the city who worked at these stations formed IWS and expanded their work to include examining vulnerable infants and educating mothers about infant care. At that time, IWS volunteers made more than 40,000 home visits a year.
By the end of 1912, IWS's work contributed to the reduction of the Chicago infant mortality rate. In 1913, the IWS Auxiliary was formally established to support the work of the organization by volunteering at the stations, making home visits, raising funds, sewing clothes, and even donating iceboxes.
As the century progressed, IWS continued to respond to the escalating demand for health care with innovative and quality services. In the 1920s, IWS was one of the first public health organizations in Chicago to institute mental health services. In 1950, it achieved national recognition for instituting a preschool program.
Dental care was first offered at this location in 1972, modernized in 1985, and expanded to six exam chairs in 1990. The 1991 renovation of the North Halsted building doubled IWS's usable clinic space.
Since that time, IWS has continued to develop and refine its programming in response to patient needs. Gynecological, prenatal, and general health services for women were combined into our Whole Women's Wellness model in 1995. In 2002, IWS began offering Healthy Steps, an early childhood development program based on a national best practices curriculum.
The continuum of care is our ideal, one that we see shaping our philosophy of care and patient treatment plans as we move into the future. As the demand for services increased and the patient population moved farther west, the Infant Welfare Society of Chicago relocated to a new, larger facility. In April 2005, IWS opened the doors of the Angel Harvey Infant Welfare Society of Chicago Community Health Center in the heart of the west Logan Square community, where patients have easier access to the services provided by IWS.
Today, the Angel Harvey Family Health Center of the Infant Welfare Society of Chicago, located at 3600 W. Fullerton Avenue offers full-service preventive medicine and chronic disease management for the entire family: infants, children, women, and men.

redpajama_set_name: RedPajamaCommonCrawl


text:
Your First Prenatal Visit
Pre-pregnancy Health Check
Pregnancy FAQ
Symptoms of Pregnancy
Diet for a Healthy Pregnancy
Nutrition in Pregnancy
The skin in pregnancy
Diagnosis of pregnancy
Urge Urinary Incontinence
Bypass Incontinence
Disorders During Pregnancy
- Preeclampsia
- Eclampsia
- Chronic Hypertension
Diabetes Mellitus and Pregnancy
- Type 1 Diabetes
- Gestational Diabetes
Neurologic Disorders
Medical conditions complicating pregnancy
Facts About Ovulation
Home Pregnancy Tests
Are You Ovulating?
Infertility Diagnosis
Secondary Infertility
Facts On Infertility
Hi-Tech Solutions for Infertility
Treating Infertility With Herbs
Acupuncture and Infertility
Birthing Alternatives
- Home Birth
Pediatric and Adolescent Gynecology
Contraception for Adolescents
Delayed Puberty
Adolescent Dysmenorrhea
Ovarian Masses
Breast Diseases
Precocious Puberty
Vulvo-Vaginal Disorders
Cervicitis
Cervical Polyps
Genital Prolapse
Uterine Prolapse
Menopausal Syndrome
Gynecology news |
Sterilization more common among rural women: study
Jul 14, 2013 Viewed: 381
Rural women, especially those without much education, are more likely to have their "tubes tied" in their 20s and early 30s than urban and suburban women, according to a new study.
The procedure, known medically as tubal ligation, is a permanent form of birth control. Although it may be a good option for many women, researchers said, some others go on to regret it - especially when it's performed at a young age.
It's possible, they speculated, that more rural women get sterilized because they don't have access to or can't afford long-term but reversible forms of contraception, such as intrauterine devices.
"Long-acting reversible contraception is something we'd want these younger women (who get sterilized) to consider," said Dr. Nikki Zite, from the University of Tennessee Graduate School of Medicine in Knoxville, who has studied trends in female sterilization.
But, she added, doctors who provide those options may be easier to find in cities.
For their new study, Dr. Britt Lunde from the Icahn School of Medicine at Mount Sinai in New York and her colleagues analyzed data from a national survey of about 4,700 women aged 20 to 34, conducted in 2006 through 2010.
All of those women were sexually active without fertility problems, but did not want to become pregnant.
About 23 percent of women living in rural areas of the U.S. said they'd been sterilized. That compared to less than 13 percent of urban and suburban women.
The researchers found that disparity was especially strong among less educated women. More than 55 percent of rural women who hadn't finished high school had been sterilized, compared to 26 percent of urban women without a high school degree.
However, a similar proportion of rural and urban women with more than a high school education reported tubal ligation - between seven and nine percent.
General geographic differences held up when the researchers accounted for women's age and race, whether they were married and how many kids they had.
Making less money and not having private insurance were also tied to a higher likelihood of sterilization, they reported in Obstetrics & Gynecology.
"From a study like this, we can't always get the why," Zite, who wasn't involved in the new research, told Reuters Health.
"If they are women who genuinely understood they were being sterilized and desired sterilization, then I wouldn't have a concern," she said of rural women in the study.
But it's unclear whether that was always the case. On the surveys, 39 percent of rural women and 37 percent of urban women who had been sterilized said they regretted the decision.
Many states extend Medicaid, the government-funded health insurance program for the poor, to pregnant women who might not otherwise qualify. Those women are then covered until two months after they give birth.
Some new mothers who have not been able to afford contraception may try to fit a tubal ligation into that post-delivery window so as not to worry about the cost of the procedure in the future, Zite noted.
She said going forward, the goal is to make sure women understand - and have access to - all contraceptive options.
"Health care providers and the public health system need to work to ensure equal and adequate access to all methods of contraception for all women, no matter their geographic location or education level," Lunde and her colleagues wrote.
SOURCE: Obstetrics & Gynecology, online July 8, 2013.
Latest Gynecology Headlines
Research shows efficacy of steroid use in late…
Salt intake appears to have little impact on bone…
Taming hot flashes without hormones: What works,…
24-hour OBs, midwives lead to less C-sections
Hysterectomy can be safely combined with cosmetic…
Women undergoing fertility treatment can succeed…
Data mining DNA for polycystic ovary syndrome…
The global cost of unsafe abortion
C-sections could influence babies' ability…
Umbilical cord 'milking' improves…
Adolescent Girl
Delayed Puberty Epidemiological Aspects
Menstrual Irregularities in Adolescence - Definitions,…
Hyperandrogenism in Adolescent Girls
Adolescent Dysmenorrhea Etiology
Diagnosis of Hyperandrogenism in Female Adolescents
Hyperandrogenism in Female Adolescents - Conclusions
Classification of Polycystic Ovary Syndrome (PCOS)
Congenital Gonadotropin Deficiency
Polymenorrhea
Urinary Incontinence and Urinary Tract Infection
Hysterectomy and stress urinary incontinence
Managing Urinary Incontinence
Hysterectomy and risk of stress-urinary-incontinence surgery:…
Does hysterectomy cause urinary incontinence?
Checklist for a Healthy Pelvic Floor Before & After…
How is the Vaginal Opening Affected by Childbirth –…
Risk for Stress-Urinary-Incontinence Surgery After Hysterectomy…
Hysterectomy: A Risk Factor for Urinary Incontinence?


text:
Woke White Professor Gets Fired After Mixing up the Names of Two Minority Students
By Alex Parker | 11:30 PM on November 30, 2021
(Joerg Carstensen/dpa via AP)
Has a worker ever wounded you so shamefully, they should've been fired?
Such a thing looks to have occurred in September at Fordham University.
Professor Christopher Trogan committed an oral offense.
As the story goes, he called some folks the wrong name.
Per his written explanation sent to the entire Composition II class, the man was distracted and accidentally erred.
While "reading the work of another student," he recalled, two female students walked in late.
In a "confused" moment, he mismatched the pair's monikers.
But the duo was less than laughing.
They issued him a written complaint.
Fordham paper The Observer reports:
[The two] sent [Christopher] an email after class expressing that they felt disheartened and disrespected…
The instructor insisted it was an "innocent mistake."
But as it happens, Christopher is white.
The same can't be said of those he harmed.
He referenced that fact in his response:
"I have done my best to validate and reassure the offended student that I made a simple, human, error. It has nothing to do with race."
They don't see it that way. According to The Observer, the ladies suspect "the mistake occurred because they were both Black."
And Christopher was already on thin ice with one of them.
Call him a repeat offender:
One of the first-year students who was involved in the…incident said their experience in Trogan's class prior to the incident was not great. The student, who asked to remain anonymous due to privacy concerns, told The Observer that Trogan repeatedly got their name incorrect over the course of four classes.
"I felt really disrespected. I did not feel heard because every time he [misnamed me] I would tell him, and it just seemed like he would brush it off or that he did not care," she told the outlet.
The other girl — Chantel Sims — downplayed the initial disaster:
"[What he penned] seemed a little excessive, like all you needed to do was say sorry and it would have been fine. We were not actually that upset about him mixing up our names. It was more so the random things he would throw into the response."
In his email, Christopher said he was willing to step down if the students felt discriminated against.
Trogan encouraged students to relay any complaints to Dean of Fordham College at Lincoln Center (FCLC) Laura Auricchio, English Department Chair Mary Bly and other administrators.
"Depending on your response to the officials above," he wrote, "I may — or may not — be your professor in class next week. It's all up to you."
Well, the teacher got torpedoed.
Two days after the name swap, "he was placed on immediate suspension with pay and benefits and that his actions were under investigation by the university. [Dean of the Faculty of Arts and Sciences Eva Badowska] gave him an order to not contact any Fordham student or he would face immediate termination. Part of the suspension included barring his access to Fordham's electronic systems — including email."
The end came October 25th.
And now, he claims, his physical and psychological health have suffered.
The termination was effective immediately and cut off Trogan's salary, health benefits, life insurance and retirement fund.
"I was never informed of the charges against me, nor of the nature of the investigation of which I was the subject," he claimed in a nine-page October 29th letter to all 80 of his former students. "I was kept completely in the dark."
The official letter of termination asserted he hadn't demonstrated "proper development."
Who'd have thought a guy like Christopher could've gotten canned?
It appears he'd tried extremely hard to be hip.
He'd even stuck to the strict and appropriate academic aim of English education:
In the email to students, Trogan assured students the course was "centered specifically and explicitly around issues of justice, equality, and inclusion," and that he has devoted his "entire life" to these issues — describing his dedication to racial justice throughout his career in depth.
Sadly, it wasn't enough.
Sims said the section of the email that listed his credentials and "everything he has done for minorities" gave her the impression of a white savior complex. The other first-year student interviewed by The Observer agreed with this assessment.
"The eight semesters I had taught as an adjunct were erased," he lamented.
Still, he's hoping for that English Composition element that matters most — justice:
Trogan told The Observer that he believes he should be paid his remaining salary for the academic year, and that his benefits should be immediately reinstated to rectify his termination. He also demanded that the Office of Human Resources expunge the incident from his record and stated Badowska should take questions openly from the Fordham community on his termination.
"If any student would like to help me achieve some justice now that my name is mud and my reputation has been ruined, they could insist that Badowska carry out the above three actions at a bare minimum," Trogan said.
Perhaps he'll find vindication.
Then again, maybe not: Tragically, the teacher may have become so woke, he inadvertently catapulted himself to the top of our social hierarchy.
He announced he'd step down, but he was given no points for mere symbolic sacrifice.
So goes the mystery of life, but at least he achieved that greatest contemporary accomplishment: victimhood.
He reached for the stars and lassoed the moon.
And now his career has been eclipsed.
Yet, The Observer notes, "questions still remain" regarding his discharge.
Hopefully, in the end, "racial justice" will have been served.
RedState's offering a big discount on VIP subscriptions.
Join now and get 30% off with code CM30.
Wanna give it as a gift? Use code VIPGIFT.
See more content from me:
'The View' Host Argues for a 'Tweak' of the 1st and 2nd Amendments — George Washington Wasn't a Blue Checkmark
Students at a Pro-Transgender Women's College Decry Its Anti-Nonbinary Attitude
Hillary Clinton Decries Greedy Politicians, Condemns the Right's Violent Ways
Find all my RedState work here.
Thank you for reading! Please sound off in the Comments section below.
Tags: ACADEMIA BLACK EDUCATION NEW YORK RACISM THE OBSERVER
Shadi Hamid's Now Deleted Tweet Shaming Philly Football Fans Is a Reminder to Let People Enjoy Things
Bonchie


The hydraulics game has come a long way thanks to Hoppo's.
The hydraulic suspensions found in our lowriders have come a long way since the '60s. In its infancy stage, the hydraulics game was plagued with cars being butchered with torches, and all too familiar were the wood blocks holding up A-arms until parts could be found, repaired, or replaced. Well, those days are gone and here today are a plethora of parts that can make any hydraulic setup a dream to build. We've got quick disconnects, power balls, telescopic drivelines, Johnny joints, and accumulators all there to make the jobs that much more dependable and cleaner.
Though most hydraulic system components, like pumps, armatures,reservoirs, valves/dumps, and hoses are still basically the same, they're better constructed, but that doesn't mean they won't break, and part of that reason is because you've got folks hauling around 12 batteries at their beck and call and they're not afraid to use them—so of course things are prone to break when you push the limits.
Today, what's in your trunk is as important as what's under your hood, and now that chrome, gold plating, engraving, custom-fit lines, and AN fittings have become all the rage, well, it's given us a chance to see what can really go down. But not too long ago, crappy products and poor installs gave hydraulics a bad name. Here today we have tested, approved, and guaranteed-to-perform hydraulic suspensions.
Hoppo's. For 30 years, tens of thousands of rides have come to launch thanks to their experience and quality products. Aside from exceptional customer service and craftsmanship installations, Hoppo's has a big hand in giving lowrider hydraulics a good name.
We've seen them grow from a small shop to a factory of sorts that produces their own components. The Hoppo's family, crew, and their peers are an encyclopedia of knowledge when it comes to hydraulics or air suspension tech, and to see their full-blown machine shop in action is enough to keep you in awe. From cutting-edge parts to cutting and crimping hoses down to select sizes, this one-stop shop has it all, including vintage aircraft parts and radical "one-off" systems. Even for those looking to save a buck or two, they also offer basic budget-built systems.
We recently brought them a lowrider Buick to have one of their quality setups installed and we sat with camera, pen, and paper taking notes. They not only showcased a plethora of new tricks but showed us the latest in battery and pump frames, which are welded into place. From there on in everything was bolted down (as you can see in the images) and their wiring was clean and precise.
In the end, the final test was to hit that switch and it performed flawlessly. The install was clean, their products all manufactured to precise standards, proving once again why they've earned the reputation as being the leading hydraulics shop to serve our lifestyle. Be sure to drop on by or visit them online. You won't be disappointed.
Before trunk and battery brackets are sealed off in black.
Hydro hoses made to fit.
Batteries in place, pumps are next.
Alex bolting down the pumps.