Verification of NP-complete problems: Difference between revisions

Jump to navigation Jump to search

Verification of NP-complete problems (edit)

Revision as of 10:21, 18 April 2019

4,864 bytes removed ,  18 April 2019
→‎Pseudo Code
Line 49: Line 49:
==Pseudo Code==
==Pseudo Code==
===General Case===
===General Case===
For more generality, we use the [[density matrix]] representation of the states which includes [[mixed states]] as well as [[pure states]]. For a simple pure state <math>|\psi\rangle</math> the density matrix representation will be <math>\rho_{\psi} = |\psi\rangle\langle\psi|</math>. Let us assume the initial qubit to be in an unknown state <math>\rho_{\psi}</math>. Our task is to clone this qubit universally, i.e. input-state independently, in such a way, that we can control the scaling of the original and the clone at the output. In other words, we look for output which can be represented as below:</br>
<u>'''Stage 1'''</u>
<math>\rho_{a}^{out} = s_0 \rho_{\psi} + \frac{1 - s_0}{2} \hat{I}</math></br>
#
<math>\rho_{b}^{out} = s_1 \rho_{\psi} + \frac{1 - s_1}{2} \hat{I}</math></br>
<u>'''Stage 2'''</u>
Here we assume that the original qubit after the cloning is “scaled” by the factor <math>s_0</math>, while the copy is scaled by the factor <math>s_1</math>. These two scaling parameters are not independent and they are related by a specific inequality.</br></br>
*
<u>'''Stage 1'''</u> Cloner State Preparation
# Prepare the original qubit and two additional blank qubits <math>m</math> and <math>n</math> in pure states: <math>|0\rangle_{m_0} \otimes |0\rangle_{n_0} \equiv |00\rangle</math>
#Prepare <math>|\psi\rangle_{m_1,n_1} = c_1|00\rangle + c_2|01\rangle + c_3|10\rangle + c_4|11\rangle</math>, where the complex <math>c_i</math> coefficients will be specified so that the flow of information between the clones will be as desired. </br>At this stage the original qubit is not involved, but this preparation stage will affect the fidelity of the clones at the end of the process.
#To prepare the <math>|\psi\rangle_{m_1,n_1}</math> state, a Unitary gate must be performed so that:
<math>U|00\rangle = |\psi\rangle_{m_1,n_1}</math>
*Use following relations to specify <math>c_j</math> in terms of <math>a</math> and <math>b</math>:</br>
<math>c_1 = \sqrt{\frac{s_0 + s_1}{2}}</math>, <math>c_2 = \sqrt{\frac{1 - s_0}{2}}</math>, <math>c_3 = 0</math>, <math>c_4 = \sqrt{\frac{1 - s_1}{2}}</math></br>
these <math>c_j</math> satisfy the scaling equations and also the normalization condition of the state <math>|\psi\rangle_{m_1,n_1}</math>. They are being used to control the flow of information between the clones</br></br>
<u>'''Stage 2'''</u> Cloning Circuit
*The cloning circuit consists of four CNOT gates acting on original and pre-prepared qubits from stage 2. We call the original qubit <math>|\psi\rangle_{in}</math>, ``first qubit", the first ancillary qubit of <math>|\psi\rangle_{m_1,n_1}</math>, ``second qubit" and the second one, ``third qubit". The CNOT gates will act as follows:
#First CNOT acts on first and second qubit while the first qubit is control and the second qubit is the target.
#Second CNOT acts on first and third qubit while the first qubit is control and the third qubit is the target.
# Third CNOT acts on first and second qubit while the second qubit is control and the first qubit is the target.
# Forth CNOT acts on first and third qubit while the third qubit is control and the first qubit is the target.
*Mathematically the cloning part of the protocol can be shown as:</br>
<math>|\psi\rangle_{out} = P_{3,1} P_{2,1} P_{1,3} P_{1,2} |\psi\rangle_{in} |\psi\rangle_{m_1,n_1}</math></br></br>
<u>'''Stage 3'''</u> Discarding ancillary state
*Discard one of the extra states. The output states will be the first and second (or third) output.</br></br>
===Special case with bell state:===
<u>'''Stage 1'''</u> Cloner state preparation
# Prepare the original qubit and two additional blank qubits <math>m</math> and <math>n</math> in pure states: <math>|0\rangle_{m_0} \otimes |0\rangle_{n_0} \equiv |00\rangle</math>
# Prepare <math>|\psi\rangle_{m_1,n_1} = a|\Phi^{+}\rangle_{m_1,n_1} + b|0\rangle_{m_1} |+\rangle_{n_1}</math>, where <math>|\Phi^{+}\rangle</math> is a [[Bell state]] and <math>|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)</math>. In this case, the density matrix representation of the output states will be:</br>
<math>\rho_{a}^{out} = (1 - b^2) |\psi\rangle\langle\psi| + \frac{b^2}{2} \hat{I}</math></br>
<math>\rho_{b}^{out} = (1 - a^2) |\psi\rangle\langle\psi| + \frac{a^2}{2} \hat{I}</math></br>
<u>'''Stage 2'''</u> Cloning Circuit
* The cloning circuit is exactly the same as the general case. after the cloning circuit, the output state will be:</br>
<math>a|\psi\rangle_{in} |\Phi^+\rangle_{m,n} + b|\psi\rangle_m |\Phi^+\rangle_{in,n}</math>
The reduced density matrix of two clones A and B can be written in terms of their fidelities:</br>
<math>\rho_{a}^{out} = F_a |\psi\rangle\langle\psi| + (1 - F_a)|\psi^{\perp}\rangle\langle\psi^{\perp}|</math></br>
<math>\rho_{b}^{out} = F_b |\psi\rangle\langle\psi| + (1 - F_b)|\psi^{\perp}\rangle\langle\psi^{\perp}|</math></br>
<u>'''Stage 3'''</u> Discarding ancillary state
* The same as the general case.


==Further Information==
==Further Information==
<div style='text-align: right;'>''*contributed by Federico Centrone''</div>
<div style='text-align: right;'>''*contributed by Federico Centrone''</div>
Shraddha
Write, autoreview, editor, reviewer
3,129

edits

Retrieved from "https://wiki.veriqloud.fr/index.php?title=Special:MobileDiff/2033"

Navigation menu