Generalization of quantum gates to qudits

[viathor]

Now that cirq supports qudits, we should generalize our quantum gates where possible/appropriate. Some examples of gates that should work on qudits:

• generalization of Pauli gates: X|k⟩ -> |k + 1 mod m⟩, Z|k⟩ -> e^(2πi/m)|k⟩,
• generalization of Hadamard/Fourier transform that takes X to Z under conjugation.

Naming will get tricky. We should probably not make users look for generalized gates under obscure names. Instead, the most pythonic solution is to just make cirq.X etc work on qudits. Hadamard/Fourier is probably a little trickier, because the matrix of the qudit version of the Hadamard gate is not a Hadamard matrix, so cirq.H is a weird name. We could follow literature and call it cirq.W, but that might qualify as hiding generalized gates under obscure names.

Gates such as CX and CZ when control is a qubit and target is a qudit are straightforward, but it would be misleading to stringify the qudit version of CX as "CNOT".

Filing for discussion @balopat @dabacon @Strilanc

[viathor]

The current behavior of the gates when applied to qudits is to raise a ValueError:

ValueError: Wrong shape of qids for <cirq.H>. Expected (2,) but got (3,)

[viathor]

Related: #3058

[Strilanc]

What we found when we considered doing this is that it had a lot of really bad corner cases, especially when involving noise operations.

Here is a relevant question on the quantum computing stack exchange where the same issue is encountered with "how do I control a Kraus operator?": https://quantumcomputing.stackexchange.com/questions/12196/deriving-a-controlled-kraus-operator-from-an-uncontrolled-kraus-operator . The same logic applies to trying to apply a Kraus operator to the 01 subspace but not the 2 space.

[Strilanc]

For example, consider the Reset operation when using the "just work on the 01 subspace" interpretation suggested at the start of this issue. Is the reset operation really something that leaves the |2> state alone, or is the obviously correct generalization the one that also sends |2> to |0>? That's certainly what happens for the reset operation in our hardware.

I'm not even sure I would say the obvious generalization of X to a qutrit is to leave 2 alone. The "Pauli operations" on qutrits include +0, +1, and +2 (mod 3), not "swap 0 and 1". So perhaps X should be thought of as +1 (mod 2) in which case it would become +1 (mod 3) when operating on a qutrit.

[viathor]

I didn't suggest that we should implement qudit gates by unleashing corresponding qubit gates "on the 01 subspace". This is rarely (never?) the right thing to do. Instead, I noted that some gates admit natural generalization and provided examples for unitary gates:

• generalization of Pauli gates: X|k⟩ -> |k + 1 mod m⟩, Z|k⟩ -> e^(2πi/m)|k⟩,

As you point out, natural generalizations are sometimes also available for non-unitary operations (e.g. reset).

I argue that:

• wherever a unique natural generalization exists, we should use it (e.g. Paulis).
• wherever multiple generalizations exist, but one if most common/natural, we should probably use it (e.g. reset).
• wherever generalization is ambiguous, we should raise an exception.

Regarding Pauli X on qutrit: "swap 0 and 1" is the wrong thing to do and +1 mod 3 is the right thing to do. The former fails to satisfy the canonical commutation relations that users would expect of X and Z. The latter satisfies the CCRs. In fact, by Stone-von Neumann theorem, it is the unique generalization of Pauli operators that satisfies the CCRs.

[viathor]

Interesting caveat: I think there is actually some freedom in the form of generalized X. If we let

X|k⟩ -> |k + h mod m⟩

then we obtain reasonable(*) commutation relations as long as gcd(h, m) = 1. In a Hilbert space of prime dimension m any h=1, ..., m-1 works. The advantage of the choice h=1 is that it works in any dimension m. I think this still qualifies it as the right choice.

Also, I had a closer look at Stone-von Neumann and the uniqueness guarantee is in fact qualified with a free parameter corresponding to h (it hides in the exponentiated form of the commutation relations).

---

(*) By reasonable I mean that I can find an isomorphism onto the finite Heisenberg group. The isomorphisms for different h differ in how they map the generator of the center. Also, if gcd(h, m) > 1 then it's easy to see that no representation can contain X as defined above.

[viathor]

Regarding the idea of "swapping 0 and 1": In addition to the math way of seeing that this isn't the right way to generalize Pauli X there is also the physics way:

The math way: "swap 0 and 1" is order two operator (i.e. X^2 = I), but the Heisenberg group on Z/3Z does not include any element of order two.

The physics way: X and Z correspond to the position and momentum operators, so if you identify computational basis with the position basis then it becomes natural to expect that X does something like X|k⟩ -> |k + h mod m⟩. In particular, one would expect that X doesn't have fixed points among the position basis, so it cannot leave higher levels unchanged.

[dabacon]

Heisenberg-Weyl gates would be great. This would be good to add to the roadmap feature for how we want gates to be interoperable or not. I'm not sure of the advantage of overloading Pauli, for example, but I do see the advantage of overloading procedural calls (the former leads to problems that are consumers...each needs to support all qudit infrastructure or reject it, whereas the later is about construction, where we want it to be easy for users to create these objects).

[viathor]

I agree: if cirq has qudits then cirq should have Heisenberg-Weyl gates. As is so often the case, the hard issue is how to name the new gates?

Some options:

1. Overload cirq.X and cirq.Z.
2. cirq.Clock and cirq.Shift.
3. cirq.HeisenbergWeylX and cirq.HeisenbergWeylZ or somesuch.

My preference is for 1 over 2 over 3.

In support of 1: It seems awkward to have cirq.X(qudit) raise an exception when the name together with input type make it clear what the intention is. Consider the precedent in numpy: np.sqrt works with both a scalar and a matrix - after all you can think of a scalar as a 1x1 matrix. Along the same lines, it seems reasonable that cirq.X works with both a qubit and a qudit - after all you can think of a qubit as a 2-level qudit. It seems safe, unambiguous and pythonic to just let users write cirq.Z(qudit) etc.

In support of 2: Longer than 1, but perhaps still short enough to render well in circuits. I have seen the names used only occasionally (e.g. in the wikipedia article on generalized Paulis), but the intuitive connection between the names and what the gates do is very clear.

Against 3: The long names are ugly and render poorly in circuit diagrams.

WDYT?

---

There is also the question of generalizing other gates/operations that have clear meaning for multi-level systems, e.g. reset. I think necessity will eventually push us towards including such gates. This presents an additional argument for option 1 above: When we generalize reset to qudits it is unlikely we'll want a different name for it. Once this happens and if we don't choose option 1 then we'll have an inconsistent API where some generalizations have their own names and others share the well-known name for qubits.

[cduck]

I think that there could be some confusion when reading Cirq code cirq.X(qudit) is

• a qudit Pauli (+1 mod d) gate or
• a qubit X gate on the 0-1 subspace

but I would prefer the first as a default if there is a clear way to also get the second (maybe cirq.X.on_01_subspace(qudit) that defaults to adding no phase to the other states).

For measurement (and reset), maybe there should be a "QubitHardwareMeasurementGate" that correctly simulates leaked (non-0/1) states in a hardware-specific way to produce only 0/1 measurements. This would be used for NoiseModels that use qudits. The usual cirq.measure(qudit) (cirq.reset(qudit)) already does the expected ideal qudit measurement (reset to 0).

---

In my own research I've used qudits in two paradigms with often conflicting names:

• Extended Clifford hierarchy gates like you discuss for base-d computation and qudit error correction. Example names: X, CSUM (often the same circuit diagram as CNOT), H/Chrestenson.
• Qubit gates on the 0-1, 0-2, 1-2, etc. subspaces [1, 2]. Example names: X_01, H_02, C2X02 (X on the 0-2 subspace if the control is a |2>)

I've implemented some of these gates for my own use but haven't contributed them to Cirq yet because the names aren't all consistent and the questions about integration with the rest of Cirq that you bring up. (I haven't found a good name for the qudit Hadamard gate. The name Chrestenson that I used for that comes from [3, 4])

[viathor]

One clear way to get the X gate on the 0-2 subspace would be something like

cirq.X(qudit.subspace(0, 2))

where subspace method of a qudit exposes a subspace as a qubit. This helps avoid the need for hardcoding subspace information in names of gates (and proliferation of different classes/instances for what is essentially one thing).

Re QubitHardwareMeasurementGate: Is there a universally valid "quantum hardware measurement" that accounts for leakage in the way appropriate to all types of quantum hardware?

"CSUM" is a good printed name for the qudit CX (in place of "CNOT").

Re name for the analog of Hadamard: on second thought I think that if we overload cirq.X and cirq.Z for Heisenberg-Weyl gates then we should probably overload cirq.QFT for the Chrestenson gate (perhaps that's an argument against overloading any of the names, but I think the argument about precedents for inferring details of functionality from the type of arguments applies to QFT as well).

[vtomole]

+1 for

cirq.X(qudit.subspace(0, 2))

We should extend the gates we have to qudits since qudits are general. Having cirq.H and cirq.Chrestenson is duplication IMO.

[cduck]

cirq.X(qudit.subspace(0, 2)) is an interesting idea. Would you implement it something like this (being careful about infinite recursion)?

class Gate:
    ...
    def on(self, *qubits):
        if any(isinstance(q, QuditSubspace) for q in qubits):
            return SubspaceGate(self, <subspace indices for each qubit>).on(*qubits)
        ...

This would require an awkward new type, QuditSubspace (that probably shouldn't be a Qid subclass), only used as an indicator for constructing gates on subspaces of qudits.

[daxfohl]

I looked into this, and it looks like this will have to be done gate-by-gate. The reason is that most gates define an _apply_unitary_, and we'd have to update each of those to accept an optional subspace argument and use it accordingly.

I see two ways of avoiding gate-by-gate. First, the apply_unitary protocol first calls ApplyUnitaryArgs._for_operation_with_qid_shape before passing the result of that into the gate's _apply_unitary_ method. We could update that function to accept the optional subspace argument and use that in constructing the transformed ApplyUnitaryArgs for the gate. However I don't see a way to do such an operation efficiently, as the view would have different dimensions and thus require a full copy of the tensors rather than just a view (unless numpy has some magic I'm not aware of).

The other option would be to remove _apply_unitary_ from all these gates and allow the unitary protocol to fall back to the _strat_apply_unitary_from_unitary strategy. Within that strategy, the unitary of the gate could then be stuffed with identity on the non-applied subspace, to make it the appropriate shape before applying it. But I assume that this would be less efficient or we wouldn't have gone through the trouble of implementing _apply_unitary_ everywhere?

[daxfohl]

Or wait, for the first alternative above, it looks like that's exactly what slices allows. We're just using it to slice the full size of the qid_shape, but it could be specialized to slice to a subspace. I'll try that out.

Update: Nope, looks like slices don't allow arbitrary indices. And when you try to use an index array to get the arbitrary indices it does a full copy. Now, we could do it by allowing the copy in this case, but we'd have to fix up _incorporate_result_into_target, which I'm not sure if there's a well-defined way to do this.

Another option, since the most likely use cases here would be two-dimensional subspaces, is that we could require subspaces to be defined by slices. 2-D subspaces can be slice [d0, d1, d0-d1]. This may be the lowest-hanging option.

[daxfohl]

To note, #4783 is a valid mathematical representation of it, and the simulator worked great for all our unitary gates. The only thing is there are places where we need to make sure we're using the underlying qudits instead of the wrapped ones. Diagram drawing for instance. I closed the PR because I don't think I'll have any time to work on it. But if for some reason this becomes a big need, that PR is a good starting point.

Also FWIW Reset already supports qudits. https://github.com/quantumlib/Cirq/blob/d58b58ba7c71af97cb96b667e7e6a3865c9a4bc4/cirq-core/cirq/ops/common_channels.py#L744-L746

[daxfohl]

Upon implementing it, putting a wrapper around qubits and making a qudit.subspace(0, 2) was too dangerous IMO. Even though it worked, there were just too many places we'd have to distinguish between a Qid and a QidSubspace.

I changed the linked PR so that we wrap the gate instead. It's DimensionAdapterGate(cirq.X, slice(0, 3, 2)).on(qudit). It all still uses slices under the hood to work efficiently. We can of course write a helper to clean that up to cirq.X.for_subspace(0, 2) or something. Again it all seems to work, and this time it's "just another gate" type, so far less invasive. And given it's just a gate, it's something that could more easily be serialized and run on HW too.

@viathor @dabacon How do you feel about this approach? Or, given this is an ancient issue, are we no longer interested in the feature?

[dabacon]

I think the DimensionAdapterGate is a reasonable thing to have, though it does sort of miss the original problem which was that we wanted this to be seemless. I think the conclusion was the the seemless version wasn't going to work and we have decided to create specific X and Z gates for qudits.

Let's close this for now, but if we want to revive DimensionAdapterGate we could definitely do that, but I don't think we have the evidence that people will use that over existing or custom gates.