CODEWITHSUNDEEP
pythonalgorithmnumpyquantum-computing
Syzorr
Syzorr

Reputation: 607

Coding Deutsch Algorithm

I am currently trying to code the Deutsch algorithm and struggling with how to measure the |x> qubit. Reading the example here has helped but doesn't solve my fundamental problem.

Using the following diagram as a basis for presenting my issue that I'm having, at the point that they propose the second Hadamard transformation, I still have my information encoded as a vector of probabilities corresponding to |00>, |01>, |10> and |11>.

Deutsch Algorithm Diagram

Everything I've read suggests that all I do is take the top 2 values (as they correspond to the first qubit) and apply the Hadamard transform, and then see if it is a zero or one but that doesn't seem to work. Has anybody implemented this and have any advice for how to actually achieve this? I am currently coding in Python using Numpy and the following is what I have:

x = np.array([[1], [0]])
y = np.array([[0], [1]])
h = calc_hadamard(1)

phi2 = np.kron(h.dot(x), h.dot(y))

constantF = np.array([[1, 0, 0, 0],
                      [0, 1, 0, 0],
                      [0, 0, 1, 0],
                      [0, 0, 0, 1]])

balancedF = np.array([[1, 0, 0, 0],
                      [0, 1, 0, 0],
                      [0, 0, 0, 1],
                      [0, 0, 1, 0]])

print(constantF.dot(phi2))
print(balancedF.dot(phi2))

Where what is output by those print functions is

As should hopefully be obvious, this is what is expected but performing a subsequent Hadamard transformation on the first two values gives the same answer. What am I missing here?

Upvotes: 4

Views: 541

Answers (2)

SilentMan
SilentMan

Reputation: 71

Where what is output by those print functions is

(0.5, -0.5, 0.5, -0.5), and
(0.5, -0.5, -0.5, 0.5)

This is correct indeed. If we write these vectors using the Dirac notation and factoring the 2-qubit state, it gives :

  • 1/2 ( |00> - |01> + |10> - |11> ) = 1/2 ( |0> + |1> ) ( |0> - |1> ) for the constant case
  • 1/2 ( |00> - |01> - |10> + |11> ) = 1/2 ( |0> - |1> ) ( |0> - |1> ) for the balanced case

As expected in the Deutsch algorithm (Wikipedia : Deutsch's algorithm), we can treceout (remove) the second register and apply Hadamard to the first one. It gives

  • H ( |0> + |1> ) = |0> for the constant case
  • H ( |0> - |1> ) = |1> for the balanced case

The mistake you make is that the first register on which we need to apply Hadamard then measure does not correspond to what you call the first two values. We need to go back to the Dirac notation and factor the global state as a tensor product (Kronecker product) of the 2 registers first.

Upvotes: 2

Craig Gidney
Craig Gidney

Reputation: 18276

Everything I've read suggests that all I do is take the top 2 values (as they correspond to the first qubit) and apply the Hadamard transform,

No, that's not what you do. You have to apply the Hadamard operation to the top pair and the bottom pair. Equivalently, you have to expand the 1-qubit Hadamard matrix to apply to the 2-qubit system by tensoring it together with an identity operation for the other qubit:

phi3 = constantF.dot(phi2)  # or balancedF
h_on_1_for_2 = np.kron(np.eye(2), h)
phi4 = np.dot(h_on_1_for_2, phi3)

Upvotes: 3

Related Questions