- Source: Hidden linear function problem
The hidden linear function problem, is a search problem that generalizes the Bernstein–Vazirani problem. In the Bernstein–Vazirani problem, the hidden function is implicitly specified in an oracle; while in the 2D hidden linear function problem (2D HLF), the hidden function is explicitly specified by a matrix and a binary vector. 2D HLF can be solved exactly by a constant-depth quantum circuit restricted to a 2-dimensional grid of qubits using bounded fan-in gates but can't be solved by any sub-exponential size, constant-depth classical circuit using unbounded fan-in AND, OR, and NOT gates.
While Bernstein–Vazirani's problem was designed to prove an oracle separation between complexity classes BQP and BPP, 2D HLF was designed to prove an explicit separation between the circuit classes
Q
N
C
0
{\displaystyle QNC^{0}}
and
N
C
0
{\displaystyle NC^{0}}
(
Q
N
C
0
⊈
N
C
0
{\displaystyle QNC^{0}\nsubseteq NC^{0}}
).
2D HLF problem statement
Given
A
∈
F
2
n
×
n
{\displaystyle A\in \mathbb {F} _{2}^{n\times n}}
(an upper- triangular binary matrix of size
n
×
n
{\displaystyle n\times n}
) and
b
∈
F
2
n
{\displaystyle b\in \mathbb {F} _{2}^{n}}
(a binary vector of length
n
{\displaystyle n}
),
define a function
q
:
F
2
n
→
Z
4
{\displaystyle q:\mathbb {F} _{2}^{n}\to \mathbb {Z} _{4}}
:
q
(
x
)
=
(
2
x
T
A
x
+
b
T
x
)
mod
4
=
(
2
∑
i
,
j
A
i
,
j
x
i
x
j
+
∑
i
b
i
x
i
)
mod
4
,
{\displaystyle q(x)=(2x^{T}Ax+b^{T}x){\bmod {4}}=\left(2\sum _{i,j}A_{i,j}x_{i}x_{j}+\sum _{i}b_{i}x_{i}\right){\bmod {4}},}
and
L
q
=
{
x
∈
F
2
n
:
q
(
x
⊕
y
)
=
(
q
(
x
)
+
q
(
y
)
)
mod
4
∀
y
∈
F
2
n
}
.
{\displaystyle {\mathcal {L}}_{q}={\Big \{}x\in \mathbb {F} _{2}^{n}:q(x\oplus y)=(q(x)+q(y)){\bmod {4}}~~\forall y\in \mathbb {F} _{2}^{n}{\Big \}}.}
There exists a
z
∈
F
2
n
{\displaystyle z\in \mathbb {F} _{2}^{n}}
such that
q
(
x
)
=
2
z
T
x
∀
x
∈
L
q
.
{\displaystyle q(x)=2z^{T}x~~\forall x\in {\mathcal {L}}_{q}.}
Find
z
{\displaystyle z}
.
2D HLF algorithm
With 3 registers; the first holding
A
{\displaystyle A}
, the second containing
b
{\displaystyle b}
and the third carrying an
n
{\displaystyle n}
-qubit state, the circuit has controlled gates which implement
U
q
=
∏
1
<
i
<
j
<
n
C
Z
i
j
A
i
j
⋅
⨂
j
=
1
n
S
j
b
j
{\displaystyle U_{q}=\prod _{1
from the first two registers to the third.
This problem can be solved by a quantum circuit,
H
⊗
n
U
q
H
⊗
n
∣
0
n
⟩
{\displaystyle H^{\otimes n}U_{q}H^{\otimes n}\mid 0^{n}\rangle }
, where H is the Hadamard gate, S is the S gate and CZ is CZ gate. It is solved by this circuit because with
p
(
z
)
=
|
⟨
z
|
H
⊗
n
U
q
H
⊗
n
|
0
n
⟩
|
2
{\displaystyle p(z)=\left|\langle z|H^{\otimes n}U_{q}H^{\otimes n}|0^{n}\rangle \right|^{2}}
,
p
(
z
)
>
0
{\displaystyle p(z)>0}
iff
z
{\displaystyle z}
is a solution.
References
External links
Implementation of the hidden linear function problem
Kata Kunci Pencarian:
- Kucing Schrödinger
- Hidden linear function problem
- Rectifier (neural networks)
- Nonlinear system
- Linear regression
- Activation function
- Hidden subgroup problem
- Bernstein–Vazirani algorithm
- Millennium Prize Problems
- Hidden Markov model
- Time complexity
