Is QC with Superpositioned Quantum Gates any different than normal Quantum Computation?

Question

This might be more appropriate for theoretical CS stackexchange, but it feels sufficiently low level to be relevant here.

Consider the following thought experiment:

I have a Quantum FPGA, it is a Quantum Computer, whose gates themselves can be controlled programmatically.

For example: Suppose I can have a gate object G which can be in a superposition of being a 1 Qubit Pauli X or a 1 Qubit Hadamard gate. The gate object could then be superpositioned into:

$$a_0 \left| P_x \right> + a_1 \left| H \right>$$

So when I apply this gate to a single Qubit $Q = Q_0 \left| 0 \right>+ Q_1 \left| 1 \right>$

The resulting state is

$$ a_0 \left| P_x Q \right> + a_1 \left|H Q \right>$$

$$ a_0 \left| \left( Q_1 \left| 0 \right> + Q_0 \left| y \right> \right) \right> +a_1 \left| \left( \frac{Q_0 + Q_1}{\sqrt{2}} \left| 0 \right> + \frac{Q_0 - Q_1}{\sqrt{2}}\left| y \right> \right) \right> $$

As far sampling the Qubit goes, this state looks identical to perhaps some other composition of concrete gates, but at a high level, it may be possible to determine for example the nature of $G$, in which case, the Qubit collapses to a smaller superposition.

So my question:

Is Quantum Computation with Concrete Gates Equivalent in its computational power to Quantum Computation with Superpositioned Gates?

Obviously they must be equivalent up to Polynomial time differences, simply because the first is capable of simulating any quantum system including the latter in polynomial time. But do we know for fact that the latter class, isn't say polynomially faster?

Something to note here (and switching to matrix notation).

The system is initialized with qubits $A,Q$ of the form:

$$Q = \begin{bmatrix} Q_0 \\ Q_1 \end{bmatrix} , A = \begin{bmatrix} A_0 \\ A_1 \end{bmatrix} $$

We have a gate G, that can act as either unitary operator $$ C = \begin{bmatrix} C_{00} & C_{01} \\ C_{10} & C_{11} \end{bmatrix}, D = \begin{bmatrix} D_{00} & D_{01} \\ D_{10} & D_{11} \end{bmatrix} $$

Depending on $A$, and acts on $Q$. So the resulting output is

$$ \begin{bmatrix} A_0 (C_{00} Q_0 + C_{01} Q_1)+ A_1(D_{00}Q_0 + D_{01} Q_1) \\ A_0 ( C_{10} Q_0 + C_{11} Q_1) + A_1 (D_{01} Q_0 + D_{11} Q_1 ) \end{bmatrix} $$

This is a distinctly non-linear process. that cannot be represented using a unitary transform since the output Qubits have probabilities of the form $A_i Q_j$

So while this may be simulated by a Quantum Machine it definitely is doing something a bit different.

Answer 1

If a superposed gate is equivalent to a choice of gates controlled by some pre-initialized ancilla qubits, then you can get the exact same effect with a normal gate. Just have the appropriately initialized ancilla be passed in, instead of hidden inside.

I don't think hiding the ancilla inside will give any polynomial benefit in gate count or other metrics. Unless you play games with counting the cost of passing in the ancilla for normal gates, but not counting the cost for superposed gates.

---

Also, be aware that a superposition of gates will act like a probability distribution of gates. At least, it will if the ancilla backing the superposition are not used for anything else.

Clearly you could measure the hidden backing ancilla at the end of the circuit without affecting the already-measured result. But measurement commutes with controls, and the only things on the gates' ancilla qubits are controls. So you can just slide those measurements all the way to the start of the circuit without affecting the expected outcome.

If the backing qubits were already measured at the start, you have a probability distribution of gates instead of a superposition of gates. Which somehow seems a lot less promising, but must be equivalent.