BlockEncoding interface seems too permissive: register names or ordering should be defined

[petim0]

Context

I am implementing the quantum singular value transformation (QSVT) algorithm, see Lin Lin's lecture chapter 8.3 and the circuit is the following:

Figure 8.1. Circuit of quantum singular value transformation to construct $U_{P^\diamond_{Re}} \in BE_{1,m+1}(P^\diamond_{Re}(A))$, using $U_A \in BE_{1,m}(A)$.

$|0^m>$ are the ancillas of the block encoding $U_A$.

The Issue

To translate that into Qualtran, I define a class QSVT(blockEncoding) that takes a blockEncoding. It is easy to define a correct signature, for example:

bloqEnc : BlockEncoding
def signature(self):
        return Signature([
               Register("signal", QBit()), 
               Register("ancilla", QAny(self.bloqEnc.ancilla_bitsize)),
               Register("system", QAny(self.bloqEnc.system_bitsize)),
        ])

But when implementing the build_composite_bloq(), I run into the following problem:

signal, ancilla = bb.add(controlled_rotation_bloq, target=signal, ctrl=ancilla)
ancilla, system = bb.add(bloqEnc, what_to_put_here=ancilla, what_to_put_here=system)

To make this generic, I would need either the names or ordering of the registers expected by an arbitrary block encoding. But the current BlockEncoding interface gives no guarantees about either.

I may be missing something, maybe there is a method to use bb.add correctly, but add_t and add_d don't seem to work here.

One other solution is to create a new interface, child of the BlockEncoding interface, but it seems impractical, every time someone needs to use QSVT they will need to use this other interface.

I could also impose a naming convention myself and throw an error if it is not respected, but this defeats the purpose of a general interface.

I saw that the LinearCombination bloq automatically wraps block encodings using AutoPartition. That might be the best solution, but it feels like a big overhead to do this every time we want to work with general block encodings.

I feel like the cleanest solution would be to change the BlockEncoding interface so that every block encoding must have standard system and ancilla registers (maybe a resource register as well). We know that every block encoding will have a system register and an ancilla register (except in the edge case where the matrix you are block encoding is unitary).
I also saw that this was the case before the commit 0d45c82, so there must be a reason for this design choice.

The only downside I can see in changing the BlockEncoding interface is the amount of refactoring required.

[mpharrigan]

Thanks for bringing this up and articulating it so nicely.

There are indeed two ways of doing interfaces or generic (quantum) programming. The set-up is that we want MetaBloq to call a wrapped subbloq e.g. SubBloqA(..) or SubBloqB(..) so long as it follows some sort of interface.

Template-style metaprogramming

Before 0d45c82 -- and still in many places in the library -- the signature of the subbloq is factorized and/or arbitrary. For example, SelectHubbard has registers U, V, p_x, p_y, alpha, q_x, q_y, beta among others. In this style of metaprogramming, the subbloq uses a Python-based abstract method to inform the caller metabloq what its signature is. Continuing the example, SelectHubbard implements a method that says "these registers are the selection register(s)".

Quantum interfaces

The subbloqs have un-factorized generic signatures like selection, system. Someone can use something like AutoPartition to wrap a bloq with a factorized signature into one that follows the quantum interface.

Based on your write-up, you might dismiss this as a simple "naming convention" but I must point out that that's what e.g. Python's abstract base classes are. Instead of having the host programming language enforce the convention at Python-import-time, the qualtran framework would raise an error if a subbloq doesn't follow the quantum interface.

---

Both of these approaches exist in qualtran.bloqs. Indeed, if you look at BlackBoxSelect, it converts between the two approaches.

I'm not really sure which one you prefer. You say you want standard "system" and "ancilla" registers; but reference that commit where the register names were not standard and don't like AutoPartition.

---

In my opinion and at this time, I prefer the "quantum interfaces" approach.

• I find the dynamic signatures to be very confusing.
• The underlying structure of "these sub-registers are all parts of the system register" lives only in Python-host-program-land and is not encoded anywhere in the compute graph, so it is lost if you try to serialize/send your quantum program to another tool.
• I suspect there are niceties we can add to make the quantum interfaces less clunky in practice; whereas I suspect the templating style will always be clunky

The only downside I can see in changing the BlockEncoding interface is the amount of refactoring required.

Yeah that's always the problem :) I'd take a look at the Select vs BlackBoxSelect classes to see how you can migrate gradually

Let me know what you think

[petim0]

I think I didn't explained myself properly and the commit I mentioned indeed doesn't align with what I was saying, I'm sorry I read it too quickly.

Indeed, the template-style metaprogramming is not what I’m looking for at all. I’m fully on board with having interfaces and un-factorized registers. My issue is that the current Block Encoding interface isn’t “strong” enough when it comes to register naming.
When auto-partitioning, linear_combination seems to assume that the block encodings it receives use registers named "system", "ancilla", and "resource" (when their size is > 0). From that, I guess that the interface implies these names via methods like system_bitsize(), but doesn’t actually enforce them.

So before understanding this implicit naming of the registers I was stuck when writing my QSVT bloq:
"if I am given a block encoding how can I know how to call it properly ? I know there is a system register of a certain size but what is the actual name of the register ?".

I also didn't really understand the real use of AutoPartition, I thought this bloq automatically solved that issue of not knowing the real name of the registers. But no you still have to give it the name of the registers of the sub-bloq you are wrapping.

Maybe the Block Encoding interface should include a signature to enforce the name of its registers, something like:

@property
def signature(self) -> Signature:
        return Signature.build_from_dtypes(
            system = QAny(self.system_bitsize),
            ancilla = QAny(self.ancilla_bitsize),
            resource = QAny(self.resource_bitsize),
        )

Or have it mentioned in the doc-string that registers should be named "system", "ancilla" and "ressouce". Maybe it’s just me, but that convention wasn’t clear at all from the current doc/interface.

[mpharrigan]

Ok great, we're on the same page.

Yes, I think it is key that the interface's signature is made abundantly clear; and I agree that it isn't well documented. Some loose thoughts

• we could move the signature property to the base class, but then reading the code of the implementing classes you wouldn't see the signature
• we could add a post-init method to the base class to check that the signature matches the names we expect
• we should definitely document the expected registers in the base class docstring
• I know during the design of the block encoding system, the question of what to do with absent registers came up; I wonder how much difficulty that introduces into using the interface

[mpharrigan]

Yes, autopartition isn't that automatic. It's used to make a subbloq follow an interface; for example class Unitary(BlockEncoding) takes any unitary with arbitrary signature and calls it "system"