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

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.

• There is nothing special about quantum gates. They are merely random human selections from the set of all possible Hamiltonians. That's no different from classical gates which are also just human selections from the set of all possible Boolean functions. In classical logic a single type of two input gate plus the constants are enough to form an arbitrary function. I don't know how many different quantum gates it takes to achieve the same. My guess is that it's not many. – CuriousOne Apr 9 '16 at 3:16
• It's not clear how to produce the same state I gave using traditional Quantum gates – frogeyedpeas Apr 9 '16 at 3:36
• Since Gates only yield super positions, not super positions of super positions. Unless those are secretly the same and I'm being silly – frogeyedpeas Apr 9 '16 at 3:37
• Fun question! I think that this is not impossible or non-linear, you have just made a mistake in how to write it down. Your basis states should be the tensor product of Q and A, so the initial state is $(Q_0 A_0, Q_0 A_1, Q_1, A_0, Q_1 A_1)$. This can be mapped to the final state you want by a suitable 4x4 matrix. – Rococo Apr 9 '16 at 17:08
• Ah yes! I understand now @Rococo – frogeyedpeas Apr 10 '16 at 0:13