Design discussion: Introduce zero-sized registers to support quantum interfaces

[mpharrigan]

In https://github.com/quantumlib/Qualtran/pull/1094, the desire to have zero-size registers is introduced.

The motivation is to have a consistent set of register names for a "quantum interface" and just set the size to zero if that register isn't actually "used".

I'll write my personal thoughts in a follow-on comment in this issue.

[mpharrigan]

For motivation: we want a class of bloqs that follow the same "quantum interface". Namely: the same, known set of registers with fixed names.

bb.add(arbitrary_bloq, select=select, system=system, ancilla=ancilla)

where arbitrary_bloq will happily accept ancilla even if we don't use it. I think the closest analogy in a classical programming language is to have a callable that must take all the possible arguments but a) might ignore one of them b) we can pass in None to the ignored argument. It's distinct from the concept of a "default argument", which is the opposite case where we don't pass in a value but a default one is substituted.

The reason why we can't simply take in extraneous wires and just ignore them is that we want to accurately estimate the quantum resource requirements of these algorithms, so we need to encode the fact that that line isn't actually used.

In general, I think it's helpful to ask how zero-sized registers would be handled by the protocols

• qubit counts: easy: the zero size registers don't add anything to qubit requirements
• bloq counts: at some point, a bloq that is called with a zero-size register will need to alter its decomposition to ignore that wire. For example: if a Toffoli is called with a zsr in one of its control lines, it should probably be counted as a CNOT (?)
• drawing: the zero-size registers/Connections/wires would exist and probably need to be drawn. This could be unintuitive
• classical simulation: I think the analogous classical value would be None?
• tensor simulation: I'm not sure how zero size registers would fit into this
• composition: you can only compose zero-size registers with other zero-size registers (like any data type). It's unclear to me how a zero-size register would be handled as we recurse through multiple levels of decomposition. Would we need a special allocation and freeing to allocate these null values?

---

We have the power to use the classical, Python layer of qualtran to dynamically set the signature of a bloq. There's a hierarchy of how dynamic a signature is; with a corresponding hierarchy in complexity.

1. completely fixed (e.g. CNOT)
2. simple parameterization of bitsizes (e.g. Swap)
3. different data types (e.g. Add signed/unsigned)
4. presence/absence of some of the registers (e.g. anything with a cvs argument that pops a "ctrl" register into existence)
5. completely dynamic (e.g. prior block encoding interface)

The proposal would affect level (4) by turning it into level (3).

---

I think having zero-size registers would be a decent amount of work to get right; and might end up being more confusing than it's worth. I agree with @tanujkhattar 's sentiment that we'd need to show how it would work with all the protocols I outlined above.

Are there other syntactic sugars we can use to support wiring up bloqs where one of the registers may or may-not exist? A half-baked idea would be to modify the logic of bb.add() to ignore a certain sentinel Soquet.

def add(self, bloq, **soqs):
  for k, v in soqs.items():
    if v == IGNORE_SOQUET:
       del soqs[k]

   ...
   assert soqs.keys() in bloq.reg_names
   ...

now you can call

bb.add(arbitrary_bloq, select=select, system=system, ancilla=ancilla)

where in some sort of setup code or prior composition, ancilla is set to IGNORE_SOQUET.

if self.cvs:
  ctrl_soq = bb.allocate()
else:
 ctrl_soq = IGNORE_SOQUET

bb.add(QROM(cvs=self.cvs), ctrl=ctrl_soq, select=select, target=target))

curious to hear others' thoughts

[charlesyuan314]

The concrete example I had in mind for the convenience of a zero-sized register is as follows.

You have a hierarchy of bloqs that all have a (non-zero-sized) system register and possibly an ancilla register. You want to combine a number of these bloqs together into a super-bloq, similarly to what AutoPartition does, that has the same interface as the sub-bloqs.

With zero-sized registers permitted, the process to define the super-bloq is simple:

1. partition the system register into individual registers, and hook each up to each sub-bloq
2. partition the ancilla register and hook it up similarly

Without zero-sized registers, the process is clumsier and requires more dynamic signatures:

1. partition the system register and hook it up as above
2. if none of the sub-bloqs have an ancilla, then the super-bloq also does not have one
3. otherwise, partition the ancilla into pieces for each sub-bloq that has one, and hook them up, skipping over sub-bloqs that have no ancilla

The process gets clunkier still in the presence of more registers, say a resource register.

[charlesyuan314]

In classical programming, a zero-sized register is represented by the void type (NoneType in Python), which is inhabited by one value (None). So that is the correct value to use in classical simulation.

If we think not about running programs but rather about compiling them to some lower-level representation, then we would still want to compile the zero-sized data type to a singleton object that stores no information. IGNORE_SOQUET seems to serve such a purpose.

But if I understand correctly, Soquets are only a concept that comes about at program "runtime" (circuit generation). They are not part of the program (registers, signature) itself. Thus, to stretch the analogy, introducing this Soquet may not fully solve the problem that arises in "static analysis" (qubit counts) or an alternative "virtual machine" execution (tensor simulation) of the program.

[charlesyuan314]

Would we need a special allocation and freeing to allocate these null values?

A null value stores zero information and every instance of the null value can be physically assigned the same resources (there is only one None in Python). This is the most static allocation process one can have. If this is the path we go down, I would not expect allocation to be nearly as complex as it is for "real" registers.

[charlesyuan314]

With all the above said, I would also be easily convinced that the effort required to correctly push zero-sized registers through the code would be not worth it right now, at least not without simultaneously improving other aspects of the quantum data type system. I'm certainly not advocating that we just do it if it is that difficult.

[mpharrigan]

That answers one of my questions about where these zero-size registers come from. The answer is: they are a result of a partitioning.

Point taken that it would indeed be clunkier to filter out all the zero-size cases on an individual basis.

I'll leave the ultimate decision up to you, but I think if we want to add zero-size registers we would need tests for each of the protocols. There's also the question of whether e.g. QUInt(0) and QFxp(0) are different quantum data types.

It might be worth doing the clunky thing at first, linking to this issue, and refactoring with zero-size registers as part of a complete, tested zero-size register feature

[charlesyuan314]

There's also the question of whether e.g. QUInt(0) and QFxp(0) are different quantum data types.

My thought early on was actually that there should be a QNone type and that QAny(n) should require n > 0 as should all the other types.

I thought that was getting dangerously close to a territory of QTuple and QSum types though.

[charlesyuan314]

Point taken that it would indeed be clunkier to filter out all the zero-size cases on an individual basis.

And (this was your point) it is clunkier to have a dynamic signature where a super-bloq may or may not have registers named ancilla and resource. That would be the interface we are obligated to expose to the user without zero-sized registers.

[mpharrigan]

When reviewing #924 I noticed that we don't have any checks that prevent zero-sized registers. When I added some; it looks like there are already places in the library with zero-sized registers. More information as I parse it