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.

  • $\begingroup$ 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. $\endgroup$
    – CuriousOne
    Commented Apr 9, 2016 at 3:16
  • $\begingroup$ It's not clear how to produce the same state I gave using traditional Quantum gates $\endgroup$ Commented Apr 9, 2016 at 3:36
  • $\begingroup$ Since Gates only yield super positions, not super positions of super positions. Unless those are secretly the same and I'm being silly $\endgroup$ Commented Apr 9, 2016 at 3:37
  • 1
    $\begingroup$ 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. $\endgroup$
    – Rococo
    Commented Apr 9, 2016 at 17:08
  • 1
    $\begingroup$ Ah yes! I understand now @Rococo $\endgroup$ Commented Apr 10, 2016 at 0:13

1 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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.