Login New user?  
Quantum Physics Letters
An International Journal


Volumes > Vol. 11 > No. 2


An Efficient Quantum Solution for NP-Complete Problems using n Partial Measurements

PP: 31-35
Dhananjay P. Mehendale,
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.

  Home   About us   News   Journals   Conferences Contact us Copyright naturalspublishing.com. All Rights Reserved