Question on creating an MPO

Hello, I’m looking to simulate Grovers algorithm and investigate the scaling of the bond dimension with number of qubits. My first hurdle is the controlled not gate (CNOT) which acts on an arbitrary number of qubits. My first question - is it at all possible to represent this as an MPO? And if so, how could I go about implementing it in ITensor (I’m fairly new to ITensor). Thank you!

Do you want to construct the diffusion and reflection operators? (They look like qubit operators with respect to the target state and the manifold that is the target state’s complement.) If so they are generally big, many-body, operators that will be hard to efficiently factorize in a tensor network or MPO manner unless there is additional structure to leverage which is specific to your example.

I can imagine thinking about the projector onto the target state as an outer product of an MPS but you’ll have to subtract it from the identity operator and that would subsequently be hard to box into a nice tensor.

This question has been studied a bit in where the authors show many great intermediate-bond dimension operators are out there for search purposes. I think the message got a bit lost due to the title and Aaronson’ good meaning but overly intense analysis Shtetl-Optimized » Blog Archive » Xavier Waintal responds (tl;dr Grover is still quadratically faster)

1 Like

Thank you for sharing

A very convenient way to make a controlled gate like CNOT as an MPO using ITensor is to use our “OpSum” system. Here’s an example:

  n = 10 # 10 qubits, no problem to do more
  s = siteinds("Qubit",n)
  i = 3 # i will be the "control" site
  j = 7 # j will be the site where the gate acts 

  cnot = OpSum()
  cnot += "Proj0",i,"Id",j
  cnot += "Proj1",i,"X",j
  CNOT = MPO(cnot,s)

The above is using the following way of writing the CNOT gate:

CNOT_{i,j} = \ket{0}_i \bra{0}_i \otimes I_j + \ket{1}_i \bra{1}_i \otimes X_j

and the fact that the Pauli X operator is identical to the NOT single-qubit gate.