I need to find a way to parallelize a set of controlled-unitaries that are all controlled by the same qubit and are targetting $n$ different qubits. The main constraint that I have is that I can only implement $k$-body interactions where $k$ is independent on $n$ (if I did not have this constraint I could easily perform in a unique timestep the set of controlled unitaries).

In order to illustrate, you can look at the image below. The circuit I want to implement is on the left. Its "naïve" implementation if I am limited to bounded $k$-body interactions consists in doing the circuit on the right (the circuit depth is then $n$ in this case).

enter image description here

Now, there is a trick provided in this paper which consists to use extra ancilla to do this same circuit. Basically, by entangling the control qubit to $n-1$ ancilla and by disentangling it after, one can run the circuit in $\log(n)$ depth.

enter image description here

My question:

Are there other tricks known to parallelize such circuits? I would like the depth to be "less than polynomial" as a function of $n$ the number of qubits in the target register. Any depth scaling as $\alpha \log(n)^{\beta}$ for any constants $\alpha$ and $\beta$ would be fine with me.

  • $\begingroup$ Is there something in particular that you object to about the parallelisation that you've given (which is probably what I would have done)? What difference is it that you're hoping to achieve via a different method? $\endgroup$
    – DaftWullie
    May 25, 2022 at 6:39
  • $\begingroup$ @DaftWullie My current issue is probably a bit specific but basically, if you assume to have a noise model based on $Z$ errors (each gate has a probability to apply the operator $Z$ after being applied), (i) I don't want $Z$ errors to propagate from those extra ancilla to my first qubit and (ii) I don't want to create any $X$ error from a previous $Z$ error (so Hadamard are not allowed in the circuit). This construction here won't work because cNOTs propagate $Z$ errors from target to control. $\endgroup$ May 25, 2022 at 8:30
  • $\begingroup$ You can assume that the controlled unitaries with the data block are do not propagate any $Z$ error from the target register to the qubit they are controlled by. $\endgroup$ May 25, 2022 at 8:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.