Superposition of quantum gates

Question

In the standard model of quantum computation a gate is a unitary that acts on a subsystem. Physically, it can be implemented by some device. Now, any device is also a part of our quantum world, thus it has a quantum state. This quantum state, in theory, can be in superposition with some other state. For example, it can be in a superposition with a state of device that implements different unitary gate.

The question is, are there some rigorous theoretical considerations of what superposition of gates is and how we can model its effect on a quantum state?

Answer 1

Gate superposition

Superposition is a complex linear combination of pure states with a physical interpretation of coefficients. One aspect of this interpretation concerns the probability of measurement outcomes on a superposition state. Gates are not pure states and generally cannot be measured. Therefore, strictly speaking, there is no such thing as a superposition of quantum gates.

Quantum computer in superposition

In order to answer the part of the question regarding the operation of a quantum computer which is itself in a superposition of two different programs, we need to adopt a model of the quantum computer. Assume that our computer includes a classical control register that encodes the parameters of a unitary gate to be performed and a quantum data register whose state lives in the Hilbert space $\mathcal{H}_d$. If at time $t_0$ the control register is in state $r$ and the data register is in state $|\psi_0\rangle$ then at a later time $t_1$ the data register is in state

$$ |\psi_1\rangle = U(r) |\psi_0\rangle. $$

We also assume that application of quantum gates to the data register does not change the control register.

In this model, a quantum computation is performed by initializing the data register, loading values $r_0, r_1, \dots, r_n$ in order into the control register to effect the desired quantum gates and finally performing a computational basis measurement on the data register. Our model ignores the mechanism which sets the control register.

Now, let us do what the question suggested and consider the above quantum computer to be a quantum system. Thus, the state of our control register now lives in the Hilbert space $\mathcal{H}_c$ and the state space of our computer is $\mathcal{H}_c \otimes \mathcal{H}_d$.

For simplicity, let us first consider the situation where at time $t_0$ the control register is in a classical state $|r\rangle$ and the data register is in state $|\psi_0\rangle$. By the correspondence principle, at time $t_1$ the computer will be in state

$$ (I \otimes U(r))|r\rangle |\psi_0\rangle = |r\rangle |\psi_1\rangle.\tag1 $$

Note that the states $|r\rangle$ form a basis of $\mathcal{H}_c$. In the case where the control register is binary, these can be identified as the computational basis states in $\mathcal{H}_c$. Now, since these states form a basis, the equation $(1)$ provides us with the full specification of the action of the quantum computer. This operation can be written as a matrix

$$ C = \begin{pmatrix} U(0) & 0 & 0 & \dots & 0 \\ 0 & U(1) & 0 & \dots & 0 \\ 0 & 0 & U(2) & \dots & 0 \\ \dots \\ 0 & 0 & 0 & \dots & U(N-1) \end{pmatrix}\tag2 $$

or more succinctly as the direct sum

$$ C = U(0) \oplus U(1) \oplus \dots \oplus U(N-1)\tag{2'} $$

where $U(k)$ for $k=0, \dots, N-1$ are the gates that our quantum computer can natively perform (this is often called the "gateset").

Suppose now that at time $t_0$ the control register is in state

$$ |s\rangle = \alpha |r\rangle + \beta |r'\rangle $$

for appropriate $\alpha$ and $\beta$ and that the data register is in state $|\psi_0\rangle$. By the superposition principle, at a later time $t_1$ the computer will be in state

$$ \begin{align} C |s\rangle|\psi_0\rangle &= C (\alpha |r\rangle + \beta |r'\rangle)|\psi_0\rangle \\ &= \alpha \,C |r\rangle|\psi_0\rangle + \beta \,C |r'\rangle|\psi_0\rangle \\ &= \alpha \,(I \otimes U(r))|r\rangle|\psi_0\rangle + \beta \,(I \otimes U(r'))|r'\rangle|\psi_0\rangle \\ &= \alpha \,|r\rangle|\psi_1\rangle + \beta\,|r'\rangle|\psi_1'\rangle \end{align} $$

where $|\psi_1'\rangle = U(r')|\psi_0\rangle$.

This operation can be viewed as a quantum analogue of the classical switch statement that selects a unitary to be applied on the data register based on the contents of the control register. It is sometimes called the quantum multiplexor (see e.g. here).

However, while the direct sum of the unitary gates and the entangled state of the control and data registers explains what happens in a quantum computer that is in a superposition of two different programs, direct sum of two gates lacks many properties familiar from state superposition. In particular, direct sum of unitary gates has no amplitudes. Also, the superposition of the full quantum computer turns into a mixture when the control register is traced out and so - as pointed out in the comments - the data register itself is not in superposition. Thus, the model above does not define a notion one could call "gate superposition". This is expected as unlike states, unitary evolutions do not superpose. It is also informative to see how other approaches to defining such a notion fail.

Naive linear algebra

Naively forming a "superposition" of two unitary gates $U$ and $V$ by taking

$$ M = \alpha U + \beta V $$

for $\alpha, \beta \in \mathbb{C}$ such that $|\alpha|^2 + |\beta|^2 = 1$ does not generally result in $M$ unitary. This is a consequence of the fact that the set of unitary operators is not a complex vector space. Similarly to how one can normalize non-zero ket to unit norm, one can also extract the unitary part of a non-singular matrix using the polar decomposition

$$ M = WP $$

where $P$ is positive and $W$ unitary. However, this lacks the physical meaning associated with superposition.

State-channel duality

One could also seek a way to define gate "superposition" by looking at the superposition of the corresponding states under state-channel duality. Let $|i\rangle$ for $i=1, \dots, d$ denote an orthonormal basis of a $d$-dimensional Hilbert space $\mathcal{H}$ and let $|\psi\rangle = \frac{1}{\sqrt{d}}\sum_{i=1}^d |i\rangle|i\rangle$ be a maximally entangled state. Denote by $U$ and $V$ two unitary gates on $\mathcal{H}$. The corresponding states are

$$ \rho_U = (I \otimes \mathcal{U})(|\psi\rangle\langle\psi|) = \frac{1}{d}\sum_{i,j=1}^d |i\rangle\langle j| \otimes U|i\rangle\langle j|U^\dagger \\ \rho_V = (I \otimes \mathcal{V})(|\psi\rangle\langle\psi|) = \frac{1}{d}\sum_{i,j=1}^d |i\rangle\langle j| \otimes V|i\rangle\langle j|V^\dagger. $$

Note that $\rho_U$ and $\rho_V$ are pure. Their superposition with amplitudes $\alpha$ and $\beta$ is

$$ \begin{align} |\psi_M\rangle &= \alpha \left(\frac{1}{\sqrt{d}}\sum_{i=1}^d |i\rangle \otimes U|i\rangle\right) + \beta \left(\frac{1}{\sqrt{d}}\sum_{i=1}^d |i\rangle \otimes V|i\rangle \right) \\ &= \frac{1}{\sqrt{d}}\sum_{i=1}^d |i\rangle \otimes (\alpha U + \beta V)|i\rangle \\ &= \frac{1}{\sqrt{d}}\sum_{i=1}^d |i\rangle \otimes M|i\rangle \\ &= (I \otimes M) |\psi\rangle \end{align} $$

where as before $M = \alpha U + \beta V$. Note that $|\psi_M\rangle$ is not normalized. In fact, when $M$ is singular, it may be impossible to normalize it. However, even when $|\psi_M\rangle$ can be normalized, it is not necessarily a maximally entangled state. Consequently, it does not map back to a unitary operation via state-channel duality.

Answer 2

This is nothing but a controlled-unitary gate. The only difference to an "ordinary" controlled-unitary is that now, the control qubit is encoded in the overall state of the device that implements the unitary.

Answer 3

Just to sort of "talk out" the conceptual difficulty of a "superposition of gates" would be (which was discusssed in a more abstract way by @Adam Zalcman), let's try to conceptually think of an experiment where it would be reasonable to say there's a "superposition of two gate operations." Consider the following experiment:

Our quantum computer first "flips a quantum coin". It just makes a measurement of the qubit $$ \frac{1}{\sqrt{2}}\Big(|H\rangle+|T\rangle \Big)$$

if heads $|H\rangle$, we rotate state "a" $|0\rangle_a$ with unitary operation $U_H$: $$|0\rangle_a\xrightarrow{U_H} \frac{1}{\sqrt{2}}\Big(|0\rangle_a+|1\rangle_a \Big)$$

if tails we do nothing: $$|0\rangle_a\xrightarrow{U_T} |0\rangle_a $$

From this we can see that in the quantum computer's perspective we are in a mixed state of 50% $U_H|0\rangle_a$ and 50% $U_T|0\rangle_a$. But (through the Wigner's friend paradox), our quantum computers state (before we, an external observer, checks it) is in a superposition state:

$$ U_H|0\rangle_a |F_H\rangle + U_T|0\rangle_a |F_T\rangle $$

Now we can see that our quantum computer really is in a superposition of performing two different gate operations. And in fact, this superpositionness is physical, as I can come up with a observable Q that can observe nonclassical quantum interference "fringes".

Writing out $ |\langle Q|\psi\rangle|^2$

$$ |\langle Q| \frac{1}{\sqrt{2}} \Big(U_H|0\rangle_a |F_H\rangle + U_T|0\rangle_a |F_T\rangle \Big)|^2$$

$$ \frac{1}{\sqrt{2}} \Big( \langle 0 | U_H^\dagger \langle F_H | + \langle 0 | U_T^\dagger \langle F_T| | Q\rangle \Big) |\langle Q| \frac{1}{\sqrt{2}} \Big(U_H|0\rangle_a |F_H\rangle + U_T|0\rangle_a |F_T\rangle \Big)$$

$$ =\frac{1}{2} \Big( \langle 0 | U_H^\dagger \langle F_H || Q\rangle \langle Q| U_H|0\rangle_a |F_H\rangle + \langle 0 | U_T^\dagger \langle F_T| | Q\rangle \langle Q|U_T|0\rangle_a |F_T\rangle + \langle 0 | U_H^\dagger \langle F_H || Q\rangle \langle Q|U_T|0\rangle_a |F_T\rangle + \langle 0 | U_T^\dagger \langle F_T| | Q\rangle \langle Q| U_H|0\rangle_a |F_H\rangle \Big)$$

$$ =\underbrace{\frac{1}{2} |Q_H|^2 + \frac{1}{2}|Q_T|^2}_{\text{Terms via Normal Probability}} + \underbrace{ \frac{1}{2}Q_H^*Q_T + \frac{1}{2}Q_H Q_T^*}_{\text{Quantum Interference Terms}}$$

One important point here is that we don't actually observe these "Quantum interference terms" if we measure in the origional basis of the state. For instance if we make a measurement of $|0\rangle_a |F_H\rangle$ or $|0\rangle_a |F_T\rangle$ (assuming $\langle F_H|F_T\rangle = 0$), then these quantum terms drop out.

So the reality is that this observable Q needs be a projection on a state like $\frac{1}{\sqrt{2}}\Big(|F_T\rangle + |F_H\rangle\Big)$, which doesn't seem easy. Most likely this will require some kind of interference between the two states of the quantum computer. (You're going to do an interference experiment using the entire quantum computer, measurement devices and gates included??)

This to me is the main difficulty with refering to such things as "superpositions of gates." To get some interesting observable evidence of the "superpositionness" you really need to reference (and interfere) the entire computer as a state when normally we only refer to individual parts of the quantum computer as being in superpositions.

ALSO a different type of answer:

A sort of different interpretation of "superposition of gates" is simply what happens if you have a gate that interacts with a superposition state.

For example if you consider the operation: $$|1\rangle \otimes \frac{1}{\sqrt{2}}\Big(|0\rangle+|1\rangle\Big) \rightarrow |1\rangle \otimes \frac{1}{\sqrt{2}}\Big(|0\rangle-|1\rangle\Big) $$

and

$$|0\rangle \otimes \frac{1}{\sqrt{2}}\Big(|0\rangle+|1\rangle\Big) \rightarrow |0\rangle \otimes \frac{1}{\sqrt{2}}\Big(|0\rangle+|1\rangle\Big) $$

Here you can see that if our gate interacts with a superposition state, in the first qubit, both possiblites happen simultaneously:

$$\begin{align} \left(\alpha|0\rangle + \beta|1\rangle \right) \otimes \frac{1}{\sqrt{2}}\Big(|0\rangle+|1\rangle\Big) \rightarrow & \alpha |0\rangle \otimes \frac{1}{\sqrt{2}}\Big(|0\rangle-|1\rangle\Big) \\ & + \beta |1\rangle \otimes \frac{1}{\sqrt{2}}\Big(|0\rangle+|1\rangle\Big) \end{align}$$

So I think also here this is, in some sense, a "superposition of gates," as mentioned by Norbert.

Answer 4

Putting something as massive as even the simplest gate-device into a superposition goes beyond currently understood physics. At a "device-scale" general relativistic considerations may become significant because the two device-states will have different mass-distributions and distinct gravitational self-energies.

Roger Penrose has worked through the implications of this rigorously and argues that this difference in gravitational self-energy (exceptionally tiny as it may be) ultimately forces one to attempt to superpose states belonging to two different vacua, i.e. two incompatible Hilbert spaces, which is not allowed by quantum mechanics (Section 4.2 of Fashion, Faith, and Fantasy, with ample references therein).

This takes the analysis of such a system "outside the normal framework of quantum mechanics, and there does not seem to be an unambiguous way to proceed." Penrose goes on to propose a way to manage the situation, within a framework that borrows heavily from Bohmian mechanics, by quantifying the error introduced by these "illegal" superpositions and treating it as a form of energy uncertainty.

The approach outlined by Penrose is manifestly falsifiable, and my understanding is that there are several groups attempting to devise experiments to test it.