# Quantum Heaviside Eigen Solver

Zheng-Zhi Sun  School of Physical Sciences, University of Chinese Academy of
Sciences, P. O. Box 4588, Beijing 100049, China  Gang Su<EMAIL_ADDRESS>Kavli
Institute for Theoretical Sciences, and CAS Center for Excellence in
Topological Quantum Computation, University of Chinese Academy of Sciences,
Beijing 100190, China  School of Physical Sciences, University of Chinese
Academy of Sciences, P. O. Box 4588, Beijing 100049, China

###### Abstract

Solving Hamiltonian matrix is a central task in quantum many-body physics and
quantum chemistry. Here we propose a novel quantum algorithm named as a
quantum Heaviside eigen solver to calculate both the eigen values and eigen
states of the general Hamiltonian for quantum computers. A quantum judge is
suggested to determine whether all the eigen values of a given Hamiltonian is
larger than a certain threshold, and the lowest eigen value with an error
smaller than $\varepsilon$ can be obtained by dichotomy in
$O\left({{{\log}}{1\over\varepsilon}}\right)$ iterations of shifting
Hamiltonian and performing quantum judge. A quantum selector is proposed to
calculate the corresponding eigen states. Both quantum judge and quantum
selector achieve quadratic speedup from amplitude amplification over classical
diagonalization methods. The present algorithm is a universal quantum eigen
solver for Hamiltonian in quantum many-body systems and quantum chemistry. We
test this algorithm on the quantum simulator for a physical model to show its
good feasibility.

## Introduction

Quantum computer is a computing machine based on the principles of quantum
mechanics, which preforms unitary evolutions on qubits [1, 2]. It promises
algorithms to solve important problems with exponential or polynomial speedup
for many algebraic, number theoretic and oracular algorithms [3, 4, 5, 6, 7,
8, 9], etc. Among them, solving eigen states and eigen values of a quantum
many-body system is one of central tasks in condensed matter physics and
quantum chemistry [10, 11, 12, 13]. Many classical numerical methods were
suggested to study many-body systems such as density functional theory [14],
quantum Monte Carlo [15], and tensor network approach [16], etc. However,
those methods are tied up in strongly correlated systems, where representing
the quantum state is classically inaccessible due to the exponential dimension
of the underlying Hilbert space when the size of system is very large. This
issue can be naturally avoided in a quantum computer since one can store the
quantum states in a number of qubits that scale linearly with the size of the
physical system. The acceleration of solving such eigen problem of Hamiltonian
matrix by quantum algorithms will make great contributions to study strongly
correlated electron systems [17] and to develop new materials [18], good
catalysts [19] and even more effective medicines [20].

At present, there are several quantum algorithms that purpose to tackle this
issue. Quantum phase estimation (QPE) [21] was proposed to estimate the eigen
value of an eigen vector for a Hamiltonian matrix. This approach requires that
the eigen vector [21, 22] or a good approximation [23] is known. A more
feasible solution is to combine a re-configurable quantum processor for the
expectation estimation and a conventional or quantum computer for variational
optimization [24, 12, 25, 26, 27, 28, 29, 30, 31]. This variational quantum
eigen solver (VQE) designs a parameterized quantum circuit as the ground state
ansatz and optimizes it according to the results from the quantum processor. A
good approximation or ansatz of the ground state is necessary for QPE and VQE
to find the corresponding eigen value, which confines their applications to
the systems with a good understanding. Besides, adiabatic algorithms can
obtain a state close to the ground state of a given Hamiltonian for
sufficiently long runtimes [32]. However, the runtimes of these algorithms are
extremely difficult to calculate or bound in practice, which makes adiabatic
algorithms used as heuristic methods in most cases [32, 33, 34].

Solving the eigen problem of Hamiltonian matrix includes the calculation of
eigen values and eigen states. Once either eigen values or eigen states is
given, there are quantum algorithms that can calculate another one [21, 35,
22, 34]. However, no digital quantum algorithm can solve both the eigen values
and eigen vectors for the general form of Hamiltonian [36]. An essential path
to design such a quantum algorithm is to judge the difference between correct
results and the trial values. More specifically, it is better to design a
quantum eigen solver to judge whether all the eigen values of the given
Hamiltonian are higher than a trial eigen value. Then all eigen values can be
calculated with dichotomy one by one starting from the ground state energy.

Figure 1: Sketch of quantum Heaviside eigen solver. (a) The illustration to
solve the eigen problem of the Hamiltonian with the quantum judge and quantum
selector. Note that the excited state energies and the corresponding eigen
states can be figured out one by one starting from the ground state energy.
(b) The detailed flow-chart to design the quantum selector/judge and solve the
given Hamiltonian. This process is vividly shown as a quantum radio that
receives the signal (Hamiltonian) and output the contents (eigen states)
according to the signal and trial frequency (eigen value/threshold). The
amplitude amplification algorithm within the dash box can amplify the
amplitude of states corresponding to the trial eigen value, or all eigen
values lower than the given threshold, and filter out other states, which is
the core of quantum Heaviside eigen solver.

In this work we present a quantum algorithm called quantum Heaviside eigen
solver (QHES) to calculate both the eigen values and eigen states of the given
Hamiltonian matrix. It consists of a quantum judge to calculate the eigen
values by dichotomy and a quantum selector to calculate the corresponding
eigen states. The Hamiltonian is defined on the space of $N$ qubits which can
be written as ${\bf{H}}=\sum\limits_{l}^{N}{{{\bf{H}}_{l}}}$, where each
${{{\bf{H}}_{l}}}$ can act on qubits [37]. The QHES can solve any Hamiltonian
in quantum many-body systems. Generally, solving the ground state energy of
this common form of Hamiltonian has been proved to be QMA-complete [38], where
QMA stands for quantum Merlin Arthur and is the quantum analog of NP. It is
generally believed that it cannot be solved in polynomial time even on quantum
computer. Solving a $\chi$-dimensional Hamiltonian matrix usually requires the
classical bits scaling as $O\left(\chi\right)$ and its running time scales as
$\Omega\left(\chi\right)$ [39]. By contrast, the amplitude amplification
algorithm [40, 41] with an exquisite design of oracle circuit in this work can
solve this problem using the qubits that scale as $O\left({\log\chi}\right)$
and its running time scales as $O\left({\sqrt{\chi}}\right)$.

The quantum judge is an amplitude amplification algorithm that evolves the
initial state into a state belonging to the “good subspace”, which is spanned
by the eigen states with eigen values lower than the trial threshold. By
detecting the presence of states in the good subspace from the output of
quantum judge, one can judge whether all eigen values of the given Hamiltonian
${\bf{H}}$ are higher than the trial threshold. The lowest eigen value of
${\bf{H}}$ with an error lower than $\varepsilon$ can be obtained by
$O\left({\log{1\over\varepsilon}}\right)$ times of binary searches of the
trial threshold. Similarly, the quantum selector is an amplitude amplification
algorithm where the good subspace is spanned by eigen states corresponding to
the given eigen value. It can directly evolve the initial state to the target
eigen states. The process of that uses QHES to solve the eigen values and
eigen states is shown in Fig. 1(a). The core kernel in this process is the
quantum circuit to achieve the identification of eigen states in quantum judge
and quantum selector. In this paper, we accomplish this task for the general
form of Hamiltonian with a quantum Heaviside circuit (QHC) and a quantum Dirac
circuit (QDC).

## Results

### A sketch of quantum Heaviside eigen solver

The QHES is like a quantum radio in the way as shown in Fig. 1(b). This
quantum radio receives the signal and outputs contents corresponding to the
frequency, where the signal represents the Hamiltonian matrix, frequency
represents the trial eigen value or all eigen values lower than the trial
threshold, and the output contents represent the corresponding eigen states
that are called qualified states. When the frequency is set at a trial
threshold and QHC is adopted in the green boxes, this quantum radio judges
whether there is any eigen state that corresponds to an eigen value lower than
the trial threshold. Combined with the dichotomy, one can obtain the lowest
eigen value with an error lower than $\varepsilon$ in
$O\left({\log{1\over\varepsilon}}\right)$ iterations of performing quantum
judge and adjusting trial threshold. This eigen value is then taken as the
trial eigen value and the quantum radio can output the corresponding eigen
states when QDC is adopted in the green boxes. These two processes are both
achieved by the amplitude amplification based on QHC and QDC, respectively,
which amplifies the amplitude of qualified states and filters out others from
the randomly initialized state $\left|{{\psi_{r}}}\right\rangle$.

Now we explain the steps to construct the quantum selector or the quantum
judge shown in Fig. 1(b).

step 1

Select a trial eigen value for QDC, or a trial threshold for QHC by dichotomy.

step 2

Shift the Hamiltonian to fix the trial eigen value to $0$, or to fix the
threshold to ${1\over 2}$. This step is to avoid redesigning the whole
circuit, where only the Hamiltonian evolution circuit needs to be changed.

step 3

Construct the QDC or QHC according to the shifted Hamiltonian, where the trial
eigen value and trial threshold is fixed. This is the most difficult and
important part in QHES.

step 4

Construct the amplitude amplification algorithm based on QDC or QHC, which is
used to mark the qualified states.

step 5

Determine the number of iterations in amplitude amplification. This step is
evaded since we use the fixed-point quantum search [42] as the amplitude
amplification algorithm.

step 6

Initialize the input state $\left|{{\psi_{r}}}\right\rangle$, which is a
superposition of all eigen states. A random circuit is usually competent.

step 7

Amplify the amplitude of qualified states and filter out others using the
circuit within the dash box.

Steps 1, 2 and 7 are classical routine operations which are introduced in the
Supplemental Material. Step 3 is to design the quantum circuit of QHC and QDC
with the given Hamiltonian, which is the core of QHES. Step 4 can be achieved
by the standard flow to construct the amplitude amplification algorithm whose
oracle circuit is QHC or QDC. Step 5 is to determine how many iterations in
amplitude amplification algorithm are needed to amplify the amplitude of
target state sufficiently. Using the fixed-point search, the number of
iterations is $O\left({\sqrt{\chi}}\right)$ on the assumption that the overlap
between $\left|{{\psi_{r}}}\right\rangle$ and target states is no less than
$O\left({{1\over\chi}}\right)$. Step 6 is to initialize the initial state
satisfying the above assumption, which can be done by a random circuit with
high probability. Next, we will introduce the central idea to construct QDC
and QHC. The mathematical analysis and detailed instructions for all steps are
presented in the Supplemental Material.

### Constructing quantum Heaviside circuit

The purposes of QHC and QDC are to mark the qualified eigen states for the
amplitude amplification. These two quantum circuits are unitary operators
working on $N$ physical qubits, $K$ auxiliary qubits and one mark qubit. They
output the results on the mark qubit while do not change the inputs on
physical qubits at all time. The states on auxiliary qubits change in the
process of quantum circuit while they are disregarded. We define the qualified
states $\left|{{E_{q}}}\right\rangle$ for these two circuits as the states on
$N$ physical qubits whose output on the mark qubit is $\left|0\right\rangle$.
For QHC, the qualified states are eigen states whose corresponding eigen
values are smaller than a given threshold $\theta$.

The QHC is designed to filter out the eigen states with eigen values larger
than the given threshold $\theta$ and to preserve as much proportion of the
eigen states with eigen values smaller than $\theta$. This process consists of
two parts. The first part is to identify the eigen values of all eigen states,
and the second part is a simple filter circuit based on the eigen values. The
QPE is proposed to entangle the eigen states with the binary representation of
their corresponding eigen values on the auxiliary qubits [21]. However, QPE is
not capable for this task due to its uncertainty, which is also called heavy
tail [35]. Here we use three strategies on the original QPE algorithm to
construct the quantum Heaviside circuit. The first is a multiple filtering
scheme to ensure the quantum Heaviside circuit can definitely filter out the
unqualified states. The second is a fine-tuning scheme to ensure the qualified
states is definitely preserved. The last is a recycling scheme using a
freezing operator to reduce the number of auxiliary qubits. To the best of our
knowledge, this is the first filtering method for a general Hamiltonian.

The quantum phase estimation is proposed to calculate the eigen values of a
given Hermite matrix, where the corresponding eigen state is given. The QPE
works on the physical qubits initialized to the corresponding eigen state and
$R$ extra qubits initialized to ${\left|0\right\rangle^{\otimes R}}$, which
are called representation qubits. This algorithm does not influence the eigen
state on physical qubits and changes the state on representation qubits to an
approximation of the binary representation of the corresponding eigen value.
The success probability of QPE to output the right (nearest) binary
representation of the corresponding eigen value on representation qubits is no
less than ${4\over{{\pi^{2}}}}$ [21]. This indicates the filter on
representation qubits after single QPE can filter out at least
${4\over{{\pi^{2}}}}$ of the unqualified states.

To make sure that all unqualified states are filtered well out, we adopt
$Q=O\left(N\right)$ QPE circuits at the same time, which is the first
strategy. Here all $Q$ QPE circuits act on the same physical qubits and
different representation qubits, which means the total number of
representation qubits is $Q\times R$. This multiple filtering scheme can
reduce the amplitude of unqualified states to exponentially small, that is,
lower than ${\left({1-{4\over{{\pi^{2}}}}}\right)^{Q}}$. Unfortunately, this
method may filter out the qualified states when the gap between the eigen
values and their nearest binary representations is large.

The strength of this filtering effect is determined by the accuracy of QPE
circuit, which is related to the accuracy of binary representation of eigen
values. Since the QPE circuit uses $R$ representation qubits, the maximum
error to express the eigen values is ${\pi\over{{2^{R}}}}$, and the
corresponding accuracy of QPE circuit is ${{4\over{{\pi^{2}}}}}$. In the worst
case, the eigen states with eigen values higher than the given threshold are
retained up to ${\left({1-{4\over{{\pi^{2}}}}}\right)^{2Q}}$. Meanwhile, we
can only guarantee that at least ${\left({{4\over{{\pi^{2}}}}}\right)^{2Q}}$
of the eigen states with eigen values lower than the given threshold are
preserved.

To solve this issue, we perform a batch of filtration for $W$ different
Hamiltonian matrices in sequence, which are shifted from the given normalized
Hamiltonian matrix recorded as ${{\bf{H}}_{0}}$. This set of Hamiltonian
matrices can be expressed as

$\displaystyle\left\\{{{{\bf{H}}_{w}}}\right\\}:{{\bf{H}}_{w}}={{\bf{H}}_{0}}+{w\over
W}{\pi\over{{2^{R-1}}}}.$ (1)

When we filter all these Hamiltonian, the error to express the eigen value
using $R$ representation qubits is reduced to no more than
${\pi\over{W{2^{\pi}}}}$ at least once. In this case, it is proved in the
Supplemental Material that at least
${\left({1-{{{\pi^{2}}}\over{2{W^{2}}}}}\right)^{2Q}}$ of the qualified states
are preserved, which can be written as $O\left(1\right)$ when
$W=O\left({\sqrt{N}}\right)$. This is the second strategy to make sure that
all qualified states are not filtered out at least once.

With these two strategies, the changed QPE circuit can efficiently filter out
the unqualified states while preserve qualified states. The number of
auxiliary qubits is $Q\times R$, which can also be written as
$O\left({N\log{1\over\varepsilon}}\right)$. Here the term of
$O\left({\log{1\over\varepsilon}}\right)$ is unavoidable since it is used for
the binary representation of the eigen values, where $\varepsilon$ is the
error bound of the quantum judge. However, its multiplication with $N$ makes
this method impractical on the near term quantum hardware. For example, if we
want to solve the eigen problem of a Hamiltonian matrix with the size of
${2^{50}}\times{2^{50}}$, it needs $50$ physical qubits to represent the
physical system and about $50\times{\log_{2}}\left({{{10}^{6}}}\right)$ qubits
to obtain the results with an error lower than ${10^{-6}}$. Next we introduce
the freezing operator as the last strategy that can reduce the number of
auxiliary qubits from $O\left({N\log{1\over\varepsilon}}\right)$ to

$\displaystyle O\left({\log N+\log{1\over\varepsilon}}\right).$ (2)

The third strategy can be described as performing QPE $Q$ times on $R$
representation qubits instead of performing QPE once on $Q\times R$
representation qubits. This strategy is similar to the iterative quantum phase
estimation (iQPE) [43] that involves measurement and reuse of qubits, which
means that it cannot be used as the subroutine of the QHES. So we design the
unitary freezing operator to “reset” the auxiliary qubits after each QPE
circuit instead of resetting the auxiliary qubits with measurement.

### Constructing quantum Dirac circuit with quantum coin toss

The task of QDC is to qualify the eigen states corresponding to a given eigen
value, which can be done by a quantum coin toss. We define the flipping
operator to achieve

$\displaystyle{{\bf{U}}_{c}}\left|{{E_{j}}}\right\rangle\left|0\right\rangle=\cos\left({{E_{j}}}\right)\left|{{E_{j}}}\right\rangle\left|0\right\rangle+i\sin\left({{E_{j}}}\right)\left|{{E_{j}}}\right\rangle\left|1\right\rangle,$
(3)

whose design is given in the Supplemental Material. Here we call the qubit to
express states $\left|0\right\rangle$ and $\left|1\right\rangle$ as quantum
coin. The ${{\bf{U}}_{c}}$ is designed to flip the state on the quantum coin
according to the state on physical qubits. If we use $M$ quantum coins at the
same time, the amplitude of all quantum coins remain
${\left|0\right\rangle^{\otimes M}}$ is ${\cos^{M}}\left({{E_{j}}}\right)$.
When $M$ is large enough, ${\cos^{M}}\left({{E_{j}}}\right)$ can be seen as an
analog of the Dirac function of ${{E_{j}}}$.

To meet the requirements of being the oracle circuit of the quantum selector,
the quantum coin toss should distinguish the eigen states with the given eigen
value ${E_{g}}$ and the states with the closest eigen value. Without losing
generality, here we suppose the given eigen value ${E_{g}}$ is zero and the
gap between ${E_{g}}$ and its closest eigen value is $\Delta$. Detailed
analysis in Supplemental Material shows that to obtain the $\varepsilon$-close
eigen state corresponding to the given eigen value ${E_{g}}$, one needs the
minimum number of quantum coins as

$\displaystyle
M=O\left({{1\over{{\Delta^{2}}}}\left({N+\log{1\over\varepsilon}}\right)}\right),$
(4)

and the error bound of ${E_{g}}$ is ${\varepsilon_{0}}=O\left(\Delta\right)$.
Under this condition, the QDC outputs ${\left|0\right\rangle^{\otimes M}}$
with an amplitude of $O\left(1\right)$ when the states on physical qubits
correspond to an eigen value $\varepsilon_{0}$-close to ${E_{g}}$, and outputs
${\left|0\right\rangle^{\otimes M}}$ with an exponentially small amplitude in
other cases. Using this QDC as the oracle circuit of amplitude amplification
algorithm, the quantum selector can obtain the eigen states of the eigen
values solved by quantum judge. Similar to the case of QHC, the number of
quantum coins is far beyond the capabilities of current quantum hardware.
Fortunately, this number can be exponentially reduced to $O\left({\log
M}\right)$ by the freezing operator.

### Freezing operator

To reduce the number of quantum coins, we replace the single toss of $M$
quantum coins to $M$ tosses of one quantum coin. A simple idea of designing
such circuit is to perform ${{{\bf{U}}_{c}}}$ when the quantum coin is in the
state of $\left|0\right\rangle$, and to perform an identity operator when the
quantum coin is in the state of $\left|1\right\rangle$. However, the operation
to complete this process is not unitary, which is forbidden by the quantum
computer. We extend this non-unitary operator to a unitary operator by
introducing the freezing operator and extra $K$ counting qubits. The freezing
operator ${{\bf{U}}_{F}}$ acts on the quantum coin and $K$ counting qubits.
The state on the counting qubits is regarded as a binary number $x$. For
example, we record $\left|{0110}\right\rangle$ as $\left|{x=6}\right\rangle$.
Then ${{\bf{U}}_{F}}$ is designed to achieve

$\displaystyle{{\bf{U}}_{F}}\left|x\right\rangle\left|0\right\rangle=\left|x\right\rangle\left|0\right\rangle,$
(5a)
$\displaystyle{{\bf{U}}_{F}}\left|x\right\rangle\left|1\right\rangle=\left|{x+1}\right\rangle\left|1\right\rangle.$
(5b)

This can be easily done by a unitary
${{\bf{U}}_{add}}=\sum\limits_{x}{\left|{x+1}\right\rangle\left\langle
x\right|}$ controlled by the quantum coin. The ${{\bf{U}}_{add}}$ is an
elementary arithmetic operation which can be efficiently performed [44]. If we
initialize the state on counting qubits to ${\left|1\right\rangle^{\otimes
K}}$ and apply ${{\bf{U}}_{F}}$, we note that the first counting qubit, which
is the highest order in the binary representation, will not be
$\left|1\right\rangle$ for ${2^{K-1}}$ times of performing ${{\bf{U}}_{F}}$
once the quantum coin is changed to $\left|1\right\rangle$.

This freezing operator can exponentially reduce the number of auxiliary qubits
by controlling ${{\bf{U}}_{c}}$ with the first counting qubit. More
specifically, the quantum coin toss can be performed on one quantum coin and
$K=O\left({\log M}\right)$ counting qubits instead of $M$ quantum coins. In
$M$ times of performing ${{\bf{U}}_{c}}$ and ${{\bf{U}}_{F}}$, once the
quantum coin is changed to $\left|1\right\rangle$, the state on the first
counting qubit will not be $\left|1\right\rangle$ based on Eq. (5). No
${{\bf{U}}_{c}}$ will be applied to the quantum coin since it is controlled by
the first counting qubit, which means the quantum coin is frozen in
$\left|1\right\rangle$ once it is changed to $\left|1\right\rangle$. If the
quantum coin is $\left|0\right\rangle$ after $M$ quantum coin tosses, it must
remain $\left|0\right\rangle$ in each quantum coin toss, which means the
amplitude of the quantum coin being $\left|0\right\rangle$ in the end is also
${\cos^{M}}\left({{E_{j}}}\right)$.

Figure 2: Example of reducing number of quantum coins using the freezing
operator. (a) Graphic representations of quantum coins, quantum coin toss,
state on counting qubits and quantum coin toss controlled by counting qubits.
Only coin toss processes that are used in the quantum selector are indicated.
(b) All ${2^{M}}$ possible results of tossing $M$ quantum coins once. We need
$M$ auxiliary qubits (quantum coins) to record the results. (c) The process of
tossing one quantum coin $M$ times controlled by counting qubits. There are
$M+1$ possible results, which is exponentially less than the case of quantum
coin toss without the control of counting qubits. We only need $O\left({\log
M}\right)$ auxiliary qubits (counting qubits) and one quantum coin to express
the results. Note that there are some simplifications compared with practical
design to explain this process more intuitively.

The nature of this exponential reduction of auxiliary qubits is the reduction
of the dimension of the state space as shown in Fig. 2. In the quantum coin
toss scheme, the quantum circuit must have the ability to express all possible
results of tossing $M$ quantum coins. The number of possible results of
tossing $M$ quantum coins once is ${2^{M}}$, which is the same as that of
tossing one quantum coin $M$ times. Since we are only interested in the result
of all quantum coins being $\left|0\right\rangle$, we choose to ignore the
state with one or more quantum coins being $\left|1\right\rangle$. Note that
we cannot decide the result of each quantum coin toss, we can only stop the
quantum coin toss by the freezing operator when the result of
$\left|1\right\rangle$ appears. The result of tossing one quantum coin $M$
times may be that all quantum coin tosses end up with $\left|0\right\rangle$
or one of the $M$ quantum coin tosses end up with $\left|1\right\rangle$. In
this situation, the dimension of result space is $M+1$, which means that we
only need $O\left({\log M}\right)$ auxiliary qubits to record the results.

In the quantum coin toss, the freezing operator guarantees that all flipping
operators are performed on the $\left|0\right\rangle$ of the quantum coin. We
define $\left|0\right\rangle$ as the target state of this freezing operator,
where all other states is frozen. Similarly, the freezing operator can be used
to reduce the number of auxiliary qubits of QHC from
$O\left({N\log{1\over\varepsilon}}\right)$ to $O\left({\log
N+\log{1\over\varepsilon}}\right)$. In this case, we need two freezing
operators whose target states are $\left|0\right\rangle$ on the first (the
highest order) representation qubit and ${\left|0\right\rangle^{\otimes R}}$
on all representation qubits, respectively. Note that the first representation
qubit being $\left|0\right\rangle$ represents the eigen value being lower than
${1\over 2}$, and ${\left|0\right\rangle^{\otimes R}}$ is the initial state of
QPE algorithm. Each iteration of the filtering process starts with a QPE
circuit controlled by the counting qubits, then the first freezing operator
prevents the states filtered out by the QPE circuit from the following
process. An inverse of the QPE circuit resets the representation qubits to an
approximation of ${\left|0\right\rangle^{\otimes R}}$, and the second freezing
operator makes sure that the next iteration exactly starts from
${\left|0\right\rangle^{\otimes R}}$.

With these three strategies, the QHC can effectively filter out unqualified
state and preserve qualified states with only $O\left({\log
N+\log{1\over\varepsilon}}\right)$ auxiliary qubits. Using this circuit as the
oracle circuit of the amplitude amplification algorithm, the quantum judge can
identify the eigen states with eigen values lower than ${1\over 2}$ from the
initial states. Since the input quantum state is randomly initialized to a
superposition of all eigen states, the quantum judge can judge whether there
is any eigen value of the given Hamiltonian which is lower than ${1\over 2}$.
By changing the trial threshold with dichotomy, or equivalently shifting and
zooming the Hamiltonian matrix, the lowest eigen value with an error lower
than $\varepsilon$ can be obtained in
$O\left({\log{1\over\varepsilon}}\right)$ iterations. The higher eigen values
can also be calculated one by one with a quantum judge that only identifies
states with eigen values between two trial thresholds. After the eigen values
are calculated by the quantum judge, the corresponding eigen states can be
given by the quantum selector that takes quantum coin toss as the oracle
circuit of the amplitude amplification algorithm. Detailed description and
complexity analysis are given in the Supplemental Material.

###  .1 Simulation results of quantum judge and quantum selector

Here we apply an open-source quantum simulator [45] to produce the numerical
results to solve the ground state energy of the given Hamiltonian
${\bf{H}}=-{1\over{N-1}}\sum\limits_{n=1}^{N-1}{{\bf{\sigma}}_{n}^{z}}{\bf{\sigma}}_{n+1}^{z}$
with quantum judge. The calculation of the lowest eigen value starts with a
trial eigen value, and then judges whether all eigen values are larger than
the trial eigen value using quantum judge. Following the standard process of
dichotomy, we can obtain the lowest eigen value whose precision is confined by
the precision of quantum judge. Here we define the error ${\varepsilon_{v}}$
to solve the ground state energy of the given Hamiltonian as

$\displaystyle{\varepsilon_{v}}=\left|{{E_{c}}-{E_{g}}}\right|,$ (6)

where ${{E_{c}}}$ is the result of dichotomy using quantum judge and
${{E_{g}}=-1}$ is the ground state energy of the given Hamiltonian.

Figure 3: Numerical results by using quantum judge to solve the ground state
energy of the given Hamiltonian
${\bf{H}}=-{1\over{N-1}}\sum\limits_{n=1}^{N-1}{{\bf{\sigma}}_{n}^{z}}{\bf{\sigma}}_{n+1}^{z}$.
Here $N$ is the number of physical qubits to represent the physical system and
$R$ is the number of the representation qubits in the QPE circuit. It can be
seen that the error of calculated eigen value decreases exponentially with the
increase of $R$. There is no result where $N=5$ and $R>7$ because of the
limitation of our computation resource.

According to Eq. (2) and the relationship of
${\varepsilon_{v}}=O\left(\varepsilon\right)$, the number of representing
qubits $R$ scales linearly to $\log{1\over\varepsilon_{v}}$, which is
consistent with the numerical result in Fig. 3. Due to the limitation of the
depth of quantum circuits in the quantum simulator, we construct the quantum
judge with an extra classical process to generate Hamiltonian set
$\left\\{{{{\bf{H}}_{w}}}\right\\}$ to make the judgment. This compromise on
numerical simulation is to change the quantum search of
$O\left({\sqrt{N}}\right)$ Hamiltonian matrices contained in the QHC to a
classical search attached to the QHC, which does not affect the verification
of Eq. (2) from Fig. 3. There is no result when $N=5$ and $R>7$ even with the
above compromise because of the high basic cost of QPE circuit owing to the
limitation of the present quantum simulator.

We also performed the numerical simulations to check the feasibility of
quantum selector, which is used to solve the ground state of the given
Hamiltonian
${\bf{H}}=-{1\over{N-1}}\sum\limits_{n=1}^{N-1}{{\bf{\sigma}}_{n}^{z}}{\bf{\sigma}}_{n+1}^{z}$.
The ground state of this Hamiltonian is a superposition of
$\left|{{\psi_{0}}}\right\rangle={\left|0\right\rangle^{\otimes N}}$ and
$\left|{{\psi_{1}}}\right\rangle={\left|1\right\rangle^{\otimes N}}$. Here we
define the error ${\varepsilon_{s}}$ to solve the ground state of the given
Hamiltonian using quantum selector as

$\displaystyle{\varepsilon_{s}}=1-{\left|{\left\langle{{{\psi_{c}}}}\mathrel{\left|{\vphantom{{{\psi_{c}}}{{\psi_{0}}}}}\right.\kern-1.2pt}{{{\psi_{0}}}}\right\rangle}\right|^{2}}-{\left|{\left\langle{{{\psi_{c}}}}\mathrel{\left|{\vphantom{{{\psi_{c}}}{{\psi_{1}}}}}\right.\kern-1.2pt}{{{\psi_{1}}}}\right\rangle}\right|^{2}},$
(7)

where $\left|{{\psi_{c}}}\right\rangle$ is the eigen state calculated by the
quantum selector. The coefficient matrix of $\left|{{\psi_{c}}}\right\rangle$
can be obtained by quantum tomography experimentally, or directly be outputted
from the quantum simulator.

Figure 4: Numerical results by using quantum selector to solve the ground
state of the given Hamiltonian
${\bf{H}}=-{1\over{N-1}}\sum\limits_{n=1}^{N-1}{{\bf{\sigma}}_{n}^{z}}{\bf{\sigma}}_{n+1}^{z}$.
Here $N$ is the number of physical qubits to represent the physical system and
$K$ is the number of counting qubits. The vertical axis starts from zero where
$\varepsilon$ equals approximately to $0.4$. The results with larger error are
meaningless where the quantum selector does not function properly because of
the lack of counting qubits. The gray dash line represents the standard line
where $\varepsilon_{s}={10^{-12}}$.

According to Eq. (4) and the relationship of
${\varepsilon_{s}}=O\left({{\varepsilon^{2}}}\right)$, the number of counting
qubits $K$ scales linearly to $\log\log{1\over\varepsilon_{s}}$, which is
consistent with the numerical result in Fig. 4. It can be seen that the error
of the quantum selector as quantum eigen state solver drops below ${10^{-12}}$
quickly. Note that we choose the simple Hamiltonian matrix to reduce the
computational source required for the simulations. The eigen values and the
corresponding eigen states of any k-local Hamiltonian [37] can be calculated
using QHES. More specifically, what we only require here is the controlled
time evolution of the given Hamiltonian can be efficiently implemented for
unit time, which is a trivial task for any k-local Hamiltonian [46, 47, 48,
49]. The k-local Hamiltonian describes more general quantum systems than
quantum many-body systems, where the former includes not only short-range
interactions but also long-range interactions.

## Discussion

In this work we presented a quantum Heaviside eigen solver to solve both the
eigen values and eigen states for the general Hamiltonian matrix using quantum
computers. The QHES can solve the eigen values of given Hamiltonian with an
error smaller than $\varepsilon$ in
$O\left({{{\log}}{1\over\varepsilon}}\right)$ binary searches using quantum
judge, which can judge whether all eigen values of the given Hamiltonian are
higher than a trial threshold. Then the quantum selector in QHES outputs eigen
states corresponding to the solved eigen values. In designing the oracle
circuit of quantum judge, the parallel identification of eigen values is based
on QPE, where three strategies are adopted to avoid its heavy tail. Besides
QPE, we only use elementary quantum arithmetic operations, which is distinct
from those based on non-trivial tasks such as block-encoding of the target
Hamiltonian. This eigen solver was also tested on a physical model, showing
its better feasibility.

We would like to mention that the QHC and the freezing operator proposed here
may contribute to other quantum algorithms. To name but a few, the QHC may be
used as an activation function in quantum (deep) neural networks [50, 51].
Furthermore, the freezing operator can exponentially reduce the dimension of
freedom space (coin space) [52] and the number of auxiliary qubits, which is
very useful when a quantum circuit contains several parts, such as the quantum
principal component analysis [53] and the quantum random walks [54, 55].

## Methods

Here we give the definition of QHC and QDC. As the oracle circuit of quantum
judge, QHC should identify all eigen states whose corresponding eigen values
are higher than the trial threshold $\theta$. It can be expressed as

$\displaystyle{{\bf{U}}_{H}}\left|{{E_{j}}}\right\rangle{\left|0\right\rangle^{\otimes
K}}\left|0\right\rangle={\alpha_{j}}\left|{{E_{j}}}\right\rangle{\left|0\right\rangle^{\otimes
K}}\left|0\right\rangle+{\beta_{j}}\left|{{E_{j}}}\right\rangle\left|{{\varphi_{j}}}\right\rangle\left|1\right\rangle,$
(8)

where ${\left|{{\alpha_{j}}}\right|^{2}}+{\left|{{\beta_{j}}}\right|^{2}}=1$
and $\left|{\varphi_{j}}\right\rangle$ represents the state that varies with
different designs of QHC on $K$ auxiliary qubits. The state
$\left|{\varphi_{j}}\right\rangle$ on auxiliary qubits is not concerned since
it does not influence the qualification of eigen states. The results of this
qualification are obtained from $\left|0\right\rangle$ and
$\left|1\right\rangle$ on the mark qubit. More specifically,
$\left|0\right\rangle$ on the mark qubit is entangled with the eigen states
with eigen values lower than $\theta$ and $\left|1\right\rangle$ is entangled
with other states. To achieve this purpose, ${\alpha_{j}}$ should be an
approximation to a Heaviside function as
${\alpha_{j}}=u\left(\theta-{{E_{j}}}\right)$, where $u$ is the classical unit
step function.

Similarly, the QDC should identify eigen states whose corresponding eigen
value is $\left|{{E_{g}}}\right\rangle$, which is defined as

$\displaystyle{{\bf{U}}_{D}}\left|{{E_{j}}}\right\rangle{\left|0\right\rangle^{\otimes
K}}\left|0\right\rangle={\gamma_{j}}\left|{{E_{j}}}\right\rangle{\left|0\right\rangle^{\otimes
K}}\left|0\right\rangle+{\rm{}}{\eta_{j}}\left|{{E_{j}}}\right\rangle\left|{\phi_{j}}\right\rangle\left|1\right\rangle,$
(9)

where ${\left|{{\gamma_{j}}}\right|^{2}}+{\left|{{\eta_{j}}}\right|^{2}}=1$
and $\left|{\phi_{j}}\right\rangle$ is also the unconcerned auxiliary state.
Here ${\gamma_{j}}$ should be much higher when ${E_{j}}={E_{g}}$ than when
${E_{j}}\neq{E_{g}}$, which is an analog to the Dirac function.

Detailed analysis in the Supplemental Material shows the requirements for
${\alpha_{j}}$ and ${\gamma_{j}}$ to obtain the eigen values and eigen states
with an error lower than $\varepsilon$ are

$\left|{{\alpha_{j}}}\right|\begin{cases}=O\left(1\right)&{E_{j}}<\theta-\varepsilon,\\\
\leq O\left({{1\over\chi}}\right)&{E_{j}}>\theta,\end{cases}$ (10)

and

$\left|{{\gamma_{j}}}\right|\begin{cases}=O\left(1\right)&{E_{j}}={E_{g}},\\\
\leq
O\left({{\varepsilon\over{\sqrt{\chi}}}}\right)&{E_{j}}\neq{E_{g}},\end{cases}$
(11)

respectively.

## Acknowledgments

We thank Zi-Yong Ge for inspiring discussions. Funding: This work is supported
in part by the National Natural Science Foundation of China (11834014), the
Strategic Priority Research Program of the Chinese Academy of Sciences
(XDB28000000), the National Key R$\&$D Program of China (2018YFA0305800), and
Beijing Municipal Science and Technology Commission (Grant No. Z190011).
Author contributions: Zheng-Zhi Sun performed all the work presented in this
manuscript under the full guidance and supervision of Gang Su. Competing
interests: We declare no competing interests. Data availability: All data
needed to evaluate the conclusions in the paper are present in the paper. The
code to generate the results in this paper can be obtained by reasonable
request to the authors.

## References

  * Feynman [1982] R. P. Feynman, Simulating physics with computers, International Journal of Theoretical Physics 21, 467 (1982).
  * Preskill [2018] J. Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  * Grover [1996] L. K. Grover, A fast quantum mechanical algorithm for database search, in  _Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing_ (ACM Press, 1996).
  * Shor [1997] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing 26, 1484 (1997).
  * Grover [1997] L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Physical Review Letters 79, 325 (1997).
  * Bennett  _et al._ [1997] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, Strengths and weaknesses of quantum computing, SIAM Journal on Computing 26, 1510 (1997).
  * Szegedy [2004] M. Szegedy, Quantum speed-up of markov chain based algorithms, in  _45th Annual IEEE Symposium on Foundations of Computer Science_ (IEEE, 2004).
  * Harrow  _et al._ [2009] A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Physical Review Letters 103, 150502 (2009).
  * Montanaro [2016] A. Montanaro, Quantum algorithms: an overview, npj Quantum Information 2, 15023 (2016).
  * Imbrie [2016] J. Z. Imbrie, On many-body localization for quantum spin chains, Journal of Statistical Physics 163, 998 (2016).
  * Shiozaki [2016] T. Shiozaki, An efficient solver for large structured eigenvalue problems in relativistic quantum chemistry, Molecular Physics 115, 5 (2016).
  * Kandala  _et al._ [2017] A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets, Nature 549, 242 (2017).
  * Jia  _et al._ [2018] C. Jia, Y. Wang, C. Mendl, B. Moritz, and T. Devereaux, Paradeisos: A perfect hashing algorithm for many-body eigenvalue problems, Computer Physics Communications 224, 81 (2018).
  * Koch and Holthausen [2001] W. Koch and M. C. Holthausen,  _A Chemist’s Guide to Density Functional Theory_ (Wiley, New York, 2001).
  * Foulkes  _et al._ [2001] W. M. C. Foulkes, L. Mitas, R. J. Needs, and G. Rajagopal, Quantum monte carlo simulations of solids, Reviews of Modern Physics 73, 33 (2001).
  * Ran  _et al._ [2020] S.-J. Ran, E. Tirrito, C. Peng, X. Chen, L. Tagliacozzo, G. Su, and M. Lewenstein,  _Tensor Network Contractions_ (Springer International Publishing, Berlin, 2020).
  * Liu [2002] Y.-L. Liu, Universal description of strongly correlated systems, International Journal of Modern Physics B 16, 773 (2002).
  * Babbush  _et al._ [2018] R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, Encoding electronic spectra in quantum circuits with linear t complexity, Physical Review X 8, 041015 (2018).
  * Reiher  _et al._ [2017] M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Elucidating reaction mechanisms on quantum computers, Proceedings of the National Academy of Sciences 114, 7555 (2017).
  * Aspuru-Guzik  _et al._ [2018] A. Aspuru-Guzik, R. Lindh, and M. Reiher, The matter simulation (r)evolution, ACS Central Science 4, 144 (2018).
  * Cleve  _et al._ [1998] R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, Quantum algorithms revisited, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454, 339 (1998).
  * Zhou  _et al._ [2013] X.-Q. Zhou, P. Kalasuwan, T. C. Ralph, and J. L. O‘Brien, Calculating unknown eigenvalues with a quantum algorithm, Nature Photonics 7, 223 (2013).
  * Abrams and Lloyd [1999] D. S. Abrams and S. Lloyd, Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors, Physical Review Letters 83, 5162 (1999).
  * Peruzzo  _et al._ [2014] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, A variational eigenvalue solver on a photonic quantum processor, Nature Communications 5, 4213 (2014).
  * Liu  _et al._ [2019] J.-G. Liu, Y.-H. Zhang, Y. Wan, and L. Wang, Variational quantum eigensolver with fewer qubits, Physical Review Research 1, 023025 (2019).
  * Wang  _et al._ [2019] D. Wang, O. Higgott, and S. Brierley, Accelerated variational quantum eigensolver, Physical Review Letters 122, 140504 (2019).
  * Parrish  _et al._ [2019] R. M. Parrish, E. G. Hohenstein, P. L. McMahon, and T. J. Martínez, Quantum computation of electronic transitions using a variational quantum eigensolver, Physical Review Letters 122, 230401 (2019).
  * Izmaylov  _et al._ [2019] A. F. Izmaylov, T.-C. Yen, R. A. Lang, and V. Verteletskyi, Unitary partitioning approach to the measurement problem in the variational quantum eigensolver method, Journal of Chemical Theory and Computation 16, 190 (2019).
  * LaRose  _et al._ [2019] R. LaRose, A. Tikku, É. O’Neel-Judy, L. Cincio, and P. J. Coles, Variational quantum state diagonalization, npj Quantum Information 5, 57 (2019).
  * Higgott  _et al._ [2019] O. Higgott, D. Wang, and S. Brierley, Variational quantum computation of excited states, Quantum 3, 156 (2019).
  * Mitarai  _et al._ [2020] K. Mitarai, Y. O. Nakagawa, and W. Mizukami, Theory of analytical energy derivatives for the variational quantum eigensolver, Physical Review Research 2, 013129 (2020).
  * Farhi  _et al._ [2000] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution, (2000), arXiv:quant-ph/0001106 [quant-ph] .
  * Jansen  _et al._ [2007] S. Jansen, M.-B. Ruskai, and R. Seiler, Bounds for the adiabatic approximation with applications to quantum computation, Journal of Mathematical Physics 48, 102111 (2007).
  * Ge  _et al._ [2019] Y. Ge, J. Tura, and J. I. Cirac, Faster ground state preparation and high-precision ground energy estimation with fewer qubits, Journal of Mathematical Physics 60, 022202 (2019).
  * Poulin and Wocjan [2009] D. Poulin and P. Wocjan, Preparing ground states of quantum many-body systems on a quantum computer, Physical Review Letters 102, 130503 (2009).
  * Lin and Tong [2020] L. Lin and Y. Tong, Near-optimal ground state preparation, Quantum 4, 372 (2020).
  * Cubitt and Montanaro [2016] T. Cubitt and A. Montanaro, Complexity classification of local hamiltonian problems, SIAM Journal on Computing 45, 268 (2016).
  * Kempe  _et al._ [2006] J. Kempe, A. Kitaev, and O. Regev, The complexity of the local hamiltonian problem, SIAM Journal on Computing 35, 1070 (2006).
  * Golub and van der Vorst [2000] G. H. Golub and H. A. van der Vorst, Eigenvalue computation in the 20th century, Journal of Computational and Applied Mathematics 123, 35 (2000).
  * Brassard and Hoyer [1997] G. Brassard and P. Hoyer, An exact quantum polynomial-time algorithm for simon's problem, in  _Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems_ (IEEE Comput. Soc, 1997).
  * Grover [1998] L. K. Grover, Quantum computers can search rapidly by using almost any transformation, Physical Review Letters 80, 4329 (1998).
  * Yoder  _et al._ [2014] T. J. Yoder, G. H. Low, and I. L. Chuang, Fixed-point quantum search with an optimal number of queries, Physical Review Letters 113, 210501 (2014).
  * Dobšíček  _et al._ [2007] M. Dobšíček, G. Johansson, V. Shumeiko, and G. Wendin, Arbitrary accuracy iterative quantum phase estimation algorithm using a single ancillary qubit: A two-qubit benchmark, Physical Review A 76, 030306 (2007).
  * Vedral  _et al._ [1996] V. Vedral, A. Barenco, and A. Ekert, Quantum networks for elementary arithmetic operations, Physical Review A 54, 147 (1996).
  * García-Pérez  _et al._ [2020] G. García-Pérez, M. A. C. Rossi, and S. Maniscalco, IBM q experience as a versatile experimental testbed for simulating open quantum systems, npj Quantum Information 6, 1 (2020).
  * Berry  _et al._ [2015a] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Simulating hamiltonian dynamics with a truncated taylor series, Physical Review Letters 114, 090502 (2015a).
  * Berry  _et al._ [2015b] D. W. Berry, A. M. Childs, and R. Kothari, Hamiltonian simulation with nearly optimal dependence on all parameters, in  _2015 IEEE 56th Annual Symposium on Foundations of Computer Science_ (IEEE, 2015).
  * Low and Chuang [2017] G. H. Low and I. L. Chuang, Optimal hamiltonian simulation by quantum signal processing, Physical Review Letters 118, 010501 (2017).
  * Low and Chuang [2019] G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum 3, 163 (2019).
  * Killoran  _et al._ [2019] N. Killoran, T. R. Bromley, J. M. Arrazola, M. Schuld, N. Quesada, and S. Lloyd, Continuous-variable quantum neural networks, Physical Review Research 1, 033063 (2019).
  * Zhao and Gao [2021] C. Zhao and X.-S. Gao, QDNN: deep neural networks with quantum layers, Quantum Machine Intelligence 3, 15 (2021).
  * Panahiyan and Fritzsche [2018] S. Panahiyan and S. Fritzsche, Controlling quantum random walk with a step-dependent coin, New Journal of Physics 20, 083028 (2018).
  * Lloyd  _et al._ [2014] S. Lloyd, M. Mohseni, and P. Rebentrost, Quantum principal component analysis, Nature Physics 10, 631 (2014).
  * Aharonov  _et al._ [1993] Y. Aharonov, L. Davidovich, and N. Zagury, Quantum random walks, Physical Review A 48, 1687 (1993).
  * Venegas-Andraca [2012] S. E. Venegas-Andraca, Quantum walks: a comprehensive review, Quantum Information Processing 11, 1015 (2012).