- Source: Hadamard test
In quantum computation, the Hadamard test is a method used to create a random variable whose expected value is the expected real part
R
e
⟨
ψ
|
U
|
ψ
⟩
{\displaystyle \mathrm {Re} \langle \psi |U|\psi \rangle }
, where
|
ψ
⟩
{\displaystyle |\psi \rangle }
is a quantum state and
U
{\displaystyle U}
is a unitary gate acting on the space of
|
ψ
⟩
{\displaystyle |\psi \rangle }
. The Hadamard test produces a random variable whose image is in
{
±
1
}
{\displaystyle \{\pm 1\}}
and whose expected value is exactly
R
e
⟨
ψ
|
U
|
ψ
⟩
{\displaystyle \mathrm {Re} \langle \psi |U|\psi \rangle }
. It is possible to modify the circuit to produce a random variable whose expected value is
I
m
⟨
ψ
|
U
|
ψ
⟩
{\displaystyle \mathrm {Im} \langle \psi |U|\psi \rangle }
by applying an
S
†
{\displaystyle S^{\dagger }}
gate after the first Hadamard gate.
Description of the circuit
To perform the Hadamard test we first calculate the state
1
2
(
|
0
⟩
+
|
1
⟩
)
⊗
|
ψ
⟩
{\displaystyle {\frac {1}{\sqrt {2}}}\left(\left|0\right\rangle +\left|1\right\rangle \right)\otimes \left|\psi \right\rangle }
. We then apply the unitary operator on
|
ψ
⟩
{\displaystyle \left|\psi \right\rangle }
conditioned on the first qubit to obtain the state
1
2
(
|
0
⟩
⊗
|
ψ
⟩
+
|
1
⟩
⊗
U
|
ψ
⟩
)
{\displaystyle {\frac {1}{\sqrt {2}}}\left(\left|0\right\rangle \otimes \left|\psi \right\rangle +\left|1\right\rangle \otimes U\left|\psi \right\rangle \right)}
. We then apply the Hadamard gate to the first qubit, yielding
1
2
(
|
0
⟩
⊗
(
I
+
U
)
|
ψ
⟩
+
|
1
⟩
⊗
(
I
−
U
)
|
ψ
⟩
)
{\displaystyle {\frac {1}{2}}\left(\left|0\right\rangle \otimes (I+U)\left|\psi \right\rangle +\left|1\right\rangle \otimes (I-U)\left|\psi \right\rangle \right)}
.
Measuring the first qubit, the result is
|
0
⟩
{\displaystyle \left|0\right\rangle }
with probability
1
4
⟨
ψ
|
(
I
+
U
†
)
(
I
+
U
)
|
ψ
⟩
{\displaystyle {\frac {1}{4}}\langle \psi |(I+U^{\dagger })(I+U)|\psi \rangle }
, in which case we output
1
{\displaystyle 1}
. The result is
|
1
⟩
{\displaystyle \left|1\right\rangle }
with probability
1
4
⟨
ψ
|
(
I
−
U
†
)
(
I
−
U
)
|
ψ
⟩
{\displaystyle {\frac {1}{4}}\langle \psi |(I-U^{\dagger })(I-U)|\psi \rangle }
, in which case we output
−
1
{\displaystyle -1}
. The expected value of the output will then be the difference between the two probabilities, which is
1
2
⟨
ψ
|
(
U
†
+
U
)
|
ψ
⟩
=
R
e
⟨
ψ
|
U
|
ψ
⟩
{\displaystyle {\frac {1}{2}}\langle \psi |(U^{\dagger }+U)|\psi \rangle =\mathrm {Re} \langle \psi |U|\psi \rangle }
To obtain a random variable whose expectation is
I
m
⟨
ψ
|
U
|
ψ
⟩
{\displaystyle \mathrm {Im} \langle \psi |U|\psi \rangle }
follow exactly the same procedure but start with
1
2
(
|
0
⟩
−
i
|
1
⟩
)
⊗
|
ψ
⟩
{\displaystyle {\frac {1}{\sqrt {2}}}\left(\left|0\right\rangle -i\left|1\right\rangle \right)\otimes \left|\psi \right\rangle }
.
The Hadamard test has many applications in quantum algorithms such as the Aharonov-Jones-Landau algorithm.
Via a very simple modification it can be used to compute inner product between two states
|
ϕ
1
⟩
{\displaystyle |\phi _{1}\rangle }
and
|
ϕ
2
⟩
{\displaystyle |\phi _{2}\rangle }
: instead of starting from a state
|
ψ
⟩
{\displaystyle |\psi \rangle }
it suffice to start from the ground state
|
0
⟩
{\displaystyle |0\rangle }
, and perform two controlled operations on the ancilla qubit. Controlled on the ancilla register being
|
0
⟩
{\displaystyle |0\rangle }
, we apply the unitary that produces
|
ϕ
1
⟩
{\displaystyle |\phi _{1}\rangle }
in the second register, and controlled on the ancilla register being in the state
|
1
⟩
{\displaystyle |1\rangle }
, we create
|
ϕ
2
⟩
{\displaystyle |\phi _{2}\rangle }
in the second register. The expected value of the measurements of the ancilla qubits leads to an estimate of
⟨
ϕ
1
|
ϕ
2
⟩
{\displaystyle \langle \phi _{1}|\phi _{2}\rangle }
. The number of samples needed to estimate the expected value with absolute error
ϵ
{\displaystyle \epsilon }
is
O
(
1
ϵ
2
)
{\displaystyle O\left({\frac {1}{\epsilon ^{2}}}\right)}
, because of a Chernoff bound. This value can be improved to
O
(
1
ϵ
)
{\displaystyle O\left({\frac {1}{\epsilon }}\right)}
using amplitude estimation techniques.
References
,
Kata Kunci Pencarian:
- Bilangan prima
- Hadamard test
- Hadamard transform
- Randomness test
- Quantum logic gate
- Glossary of quantum computing
- Root test
- Swap test
- One Clean Qubit
- Block design
- Aharonov–Jones–Landau algorithm
