|
|
 |
| |
|
|
|
An Efficient Quantum Solution for NP-Complete Problems using n Partial Measurements |
|
|
|
PP: 31-35 |
|
|
|
doi:10.18576/qpl/110203
|
|
|
|
Author(s) |
|
|
|
Dhananjay P. Mehendale,
|
|
|
|
Abstract |
|
|
| We choose the $k-$SAT problem, $k\ge 3,$ involving $n$ variables, defined by the Boolean
function, $\Phi,$ having unique correct assignment, $x=t,$ such that $\Phi(t)=1$
and $\Phi(x)=0$ for all $x\neq t.$ We prepare sufficiently many copies of quantum register, $|\Psi\ran,$ containing
superposition of all computational basis states representing different possible assignments. We will find the correct
assignment $t$ as a quantum state $|t\ran = |t_1t_2t_3t_4\cdots t_{(n-1)}t_{n}\ran$ through $n$ partial measurements.
We perform $n$ partial measurements of the state, $|\Psi_1\ran = U_\Phi|\Psi\ran,$ where
$U_\Phi$ is the unitary operator corresponding to the Boolean function $\Phi.$ The action of this unitary operator, $U_\Phi,$
on $|\Psi\ran$ inverts the phase of the solution state $|t\ran$ and the quantum
register $|\Psi\ran = (\prod_{i=1}^{\ots (n)}H|0\ran),$ where $H$ stands for the Hadamard gate,
becomes $|\Psi_1\ran = U_\Phi|\Psi\ran = (\prod_{i=1}^{\ots{(n)}}H|0\ran)-\frac{2}{\sqrt{2^{n}}}|t_1t_2t_3t_4\cdots t_{(n-1)}t_{n}\ran.$
Performing the partial measurement on $|\Psi_1\ran$ we measure its first qubit and record this result. If this result
will not be equal to $|t_1\ran$ then $|\Psi_1\ran$ will change to state
$|\Psi_2\ran = (\prod_{i=1}^{\ots{(n-1)}}H|0\ran),$ a completely separable state with $(n-1)$ linear factors,
$\frac{1}{\sqrt{2}}(|0\ran+|1\ran)$ and if this result will be equal to $|t_1\ran$ then $|\Psi_1\ran$ will change to state
$|\Psi_3\ran = (\prod_{i=1}^{\ots{(n-1)}}H|0\ran)-\frac{2}{\sqrt{2^{n-1}}}|t_2t_3t_4\cdots t_{(n-1)}t_{n}\ran,$
a completely entangled state with no factors.
Thus, using together (i) The knowledge about the result of the partial measurement of the first qubit, and (ii) The knowledge
about which state between the experimentally distinguishable states $|\Psi_2\ran$ and $|\Psi_3\ran$ has arrived as a result
of this partial measurement,
we will know $|t_1\ran$. By repeating the same procedure from the beginning for the
remaining qubits we will know $|t_2\ran, |t_3\ran, \cdots, |t_n\ran$ etc.
and thus in total $n$ such partial measurements we will know the solution state, $|t\ran$ through performing
$n$ partial measurements. |
|
|
|
|
|
|
|
