Adopt high quality coding standards and clean up technical debt before the repo becomes too large. Add CI checks so that merging is blocked until all tests pass and PR is approved.

• Unary iteration currently has optimized decomposition's specified for the cases when number of controls is 0 or 1.
• We should also add decomposition's for the general case when number of controls can be > 1.
• As an example, the Hubbard model select circuit in Fig 19 of https://arxiv.org/abs/1805.03662 needs to execute "ApplyZToLthGate" with 2 controls instead of 1.

cc @NoureldinYosri I think this is something that you can also help with, in case you have the bandwidth.

Implement what's described in https://algassert.com/post/1903

See screenshot for context:

It's not type safe coz it doesn't satisfy LSP - i.e. every derived class method should be able to accept arbitrary number of **soqs: 'SoquetT'.

We can either choose to ignore type checking here by removing SoquetT from the base class definition so that mypy doesn't type check the arguments at all. Or we'd have to somehow change the design to make it satisfy LSP.

#17

I don't think we need to be pulling in all the vendor stuff @tanujkhattar

Right now the PR merge button is set to "merge" which makes an ugly main tree.

Suggest changing to "Squash and merge" like our other repos for a nice clean series of main commits. cc @tanujkhattar

We now have the following QROM implementations to load N classical data items to a b bit register using a log(N) size selection register:

1. QROM: Implemented using Unary Iteration

   • T-complexity: $O(4N − 4)$
   • Qubit count: $O(2 * log(N) + b)$ clean qubits.

2. SelectSwapQROM: Unary iteration based QROM assisted by dirty ancillae. Given a tunable parameter $1 <= \lambda <= N$:

   • T-complexity: $2 * O(\frac{N}{\lambda}) + 4 * O(b\lambda)$ (modulo constant factors)
   • Qubit count: $O(2 * log(N / \lambda) + log(\lambda) + b)$ clean qubits and $O(b * \lambda)$ dirty qubits.
     To compute the T-complexity, notice that we have 2 applications of traditional QROM, each requiring $O(4 * (\frac{N}{\lambda} - 1))$ T-gates and 4 applications of SwapWithZero gate, each requiring $O(4 * (b - 1) * \lambda)$ T-gates.

3. If we have access to clean ancillae instead of dirty ancillae, we can further reduce the T-complexity of data lookups by doing measurement based uncomputation instead of applying the adjoint of QROM and SwapWithZero gates, as done in the second approach above. This approach is described on Page 25 of https://arxiv.org/abs/1902.02134 and (briefly) in https://algassert.com/post/1903

This issue is to track adding a new primitive using appraoch-3.

Add SelectSwap QROM implementation given in https://arxiv.org/abs/1812.00954; which uses a combination of UnaryIteration + SwapWithZeroGate to first select the correct window and then swap the correct index with 0'th register in that window.

This is a bad name anyways and caused some preliminary confusion to @tanujkhattar

The idea is that the bitsize bits are always bundled, i.e. you can't manipulate them individually; but the user-developer can index into wireshape arrays

UnaryIteration is defined recursively, but it recursively flattens things using yield from instead of yield in the decompose method. I was playing around with keeping it hierarchical and noticed that in that case we'd be doing aliasing of qubits. Namely: we use one of the ancilla as the control for the sub-operation but still pass the full ancilla register.

Qubit aliasing is anathema to folks in the QPL literature and I think stuff like this will hinder our ability to do "static analysis" on compute graphs.

@tanujkhattar

the longer name is really unnecessary

As we transition to using Bloqs for expressing the high level circuits, we'd need to add support for either reusing existing fundamental cirq gates as Bloqs; or reimplement all the functionality as bloqs.

It would be nice if we can have a way to import any valid cirq circuit as a CompositeBloq with minimal friction to avoid duplication of all the logic in Cirq ops.

on my cloudtop:

• test_fci_util takes 1:37
• test_select_swap_qrom takes 0:49

for a total execution time of 4 minutes. We should trim down these 1% of tests taking 50% of runtime @tanujkhattar @ncrubin

Add support for common 2-qubit operations in Cirq to act on qubit registers instead of qubits. For example:

• Swap
• Multi target single controlled SWAP
• CNOT

Provide efficient decompositions under the hood in terms of optimizing T gates.

The tests for generic subprepare fail when eps is < 1e-2. If the alt / keep logic is working as intended then this should not occur. We need to inspect why sub prepare fails for lower eps and fix the issue to make high accuracy simulations work as intended.

https://github.com/ncrubin/cirq-qubitization/blob/bc090f75f142a570e8682c1bc8e7904181ff1b3f/cirq_qubitization/generic_subprepare_test.py#L31

cc @ncrubin

Many fault-tolerant algorithm papers use either T-complexity (T-gates, cliffords and rotations) or Toffli Complexity (i.e. Toffoli gate, Cliffords and Rotations).

A single Toffoli can be decomposed into 4 T-gates but the inverse is harder to do (combining T-gates to get Toffoli's).

We should think about how to add support for getting both T-complexity and Toffoli complexity; and whether we should default to using Toffoli complexity instead of T-complexity.

Most of the circuits we build using this library will be large nested circuits, where we have a few composite outer level operations like loading data from QROM, selectively applying a linear combination of unitaries via Select etc. When visualizing these circuits, it would be useful to provide an interactive visualization tool to users so they can click on a "composite" operation and zoom into it's implementation (which can be obtained by calling cirq.decompose_once(op) on the composite operation). and then zoom out back to top level if needed.

One example of such a visualization is: https://github.com/microsoft/Quantum/tree/main/samples/algorithms/integer-factorization#quantum-vizjs-visualization. We should build a similar version for Cirq that's scalable and doesn't add new unnecessary qubits.

• abstract method that returns the adjoint of a bloq
• implementation for composite bloq that reverses the contents and calls adjoint on each
• adjoint of registers to flip left and right
• Maybe all bloqs should have an attribute that says whether they're the adjointed version or not?

Reminder to do this rename. The plan is

1. rename Registers -> LegacyRegisters for ease of automated-refactoring
2. make sure FancyRegisters is a strict superset of LegacyRegisters functionality. Some methods will throw value errors if not all registers are thru-registers
3. Switch existing cirq stuff to use FancyRegisters
4. Rename FancyRegisters to Registers

Here:
https://github.com/ncrubin/cirq-qubitization/blob/main/cirq_qubitization/generic_select_test.py#L218-L224

        eigenstate_prep = cirq.Circuit()
        eigenstate_prep.append(
            cirq.StatePreparationChannel(ising_wfns[:, iw_idx].flatten()).on(*target)
        )

        input_circuit = (
            turn_on_control
            + prep_circuit
            + eigenstate_prep
            + cirq.Circuit([cirq.I.on(xx) for xx in ancilla])
        )
        input_vec = sim.simulate(input_circuit).final_state_vector

• doesn't state prep channel take anything state to the desired state? doesn't that mean the initial parts of the circuit are completely redundant
• This isn't a unitary operation. Are we relying on the simulator just sampling a path? I tried changing the simulate calls to cirq.final_state_vector, which doesn't work because it's not a unitary circuit.

Unary iteration now supports writing nested for-loops by iterating over multiple qubit registers, each of different lengths. This support should be extended to QROM so that we can load, for example, data[i][j] in the target register when selection registers store i and j.

• For QROM, this should be trivial to extend.
• For SelectSwapQROM, we need to choose a parameter $k_{i}$ for each nested for-loop and then load $N_{i} / k_{i}$ elements using QROM and do swaps correctly for each loaded batch. See Appendix G of https://arxiv.org/pdf/2011.03494.pdf for more details.

Some important gates which don't yet support T-complexity are:

1. Arithmetic gates like LessThanGate.
2. PrepareUniformSuperposition gate that depends on LessThanGate.

Consider adding a new protocol so that each primitive can specify it's complexity (using sympy expressions) in a dunder method implementation and the protocol can recursively decompose complex primitives to compose the complexity of known building blocks as a sympy expression.

The default number of controls should be 0 but we should allow efficient multi controlled versions of QROM.

In the quantum_graph submodule, I will extend Bloqs so that you can have an uneven number of inputs and outputs for a Bloq. This supports allocation, de-allocaiton, and reshaping of Soquets.

registers

Unlike in Cirq where the bitsize of a register is eventually fleshed out into a List[Qid] were each individual bit is an actual object; in my design: the bitsize dimension is like a view object where we can't pick out individual bits. It's like int32 in classical programming -- you need to do a cast or something to get it to an array of bits.

Also similar to classical programming, you can create multidimensional arrays of int32. The first n-1 dimensions of this hyperrectable of bits are the dimensions of the array and the final dimension is size 32. I'm doing analogous to this. That means registers will learn two new fields: wireshape and side.

class Side(enum.Flag):
    LEFT = enum.auto()
    RIGHT = enum.auto()
    THRU = LEFT | RIGHT


@frozen
class FancyRegister:
    name: str
    bitsize: int
    wireshape: Tuple[int, ...] = tuple()
    side: Side = Side.THRU

soquets

Registers declares the function signature of a bloq. The quantum variables that we plumb through are Soquets.
A soquet will now be a particular indexed value-instance: that is -- there will be product(register.wireshape) of them for a given register.

@frozen
class Soquet:
    binst: Union[BloqInstance, DanglingT]
    reg: FancyRegister
    idx: Tuple[int, ...] = field(converter=_to_tuple, default=tuple())

(note that we're changing the second field from reg_name to the actual register.) Reminder that the user-developer won't construct these objects directly. Rather, they are handled (with lineartyping errorchecking et al) by the BloqBuilder.

# e.g.
array_of_soqs = bb.add(AllocateArrayOfQubits(shape=(2,2), bitsize=10_000))
c1, t1 = bb.add(CNOT(), control=array_of_soqs[0, 0], target=array_of_soqs[0, 1])
c2, t2 = bb.add(CNOT(), control=array_of_soqs[1, 0], target=array_of_soqs[1, 1])

reshaping

Since the last, bitsize dimension is "sealed" the user-developer can introduce bookkeeping, reshpaing bloqs. For example:

@frozen
class Split(Bloq):
    n: int

    def registers(self) -> FancyRegisters:
        return FancyRegisters(
            [
                FancyRegister(name='split', bitsize=self.n, wireshape=tuple(), side=Side.LEFT),
                FancyRegister(name='split', bitsize=1, wireshape=(self.n,), side=Side.RIGHT),
            ]
        )

Note that the register names are shared because one is LEFT, one is RIGHT and their total number of bits is equal. This can help with error checking and drawing.

bloq builder

BloqBuilder.add() is now more complicated because it has to differentiate between left (input) and right (output) registers as well as indexing. This complexity is contained within the add method which user-developers will never venture into the guts of.

As part of #157, cirq_qubitization.testing was moved to cirq_qubitization.cirq_infra.testing. Most of the contents of cirq_qubitization.cirq_infra.testing are specific to cirq except cirq_infra.testing.execute_notebook which also used in Bloqs. This method should be moved out to cirq_infra to a shared location, like cirq_qubitization/jupyter_tools.py

Consider having @classmethods on GateWithRegisters where some or many of the init args are register sizes, where this build_on_registers factory function takes registers (like on_registers) and any non-size-info init args but can figure out the size-info init args to construct the gate an immediately call on_registers to return an operation.

Quick example:

class ApplyGateToLthQubit(UnaryIterationGate):
    def __init__(
        self,
        selection_bitsize: int,
        target_bitsize: int,
        nth_gate: Callable[[int], cirq.Gate],
        *,
        control_bitsize: int = 1,
    ):
        self._selection_bitsize = selection_bitsize
        self._target_bitsize = target_bitsize
        self._nth_gate = nth_gate
        self._control_bitsize = control_bitsize

    @classmethod
    def build_on_registers(cls, *, control, selection, ancilla, target, nth_gate, control_bitsize):
        return cls(
            selection_bitsize=len(selection),
            target_bitsize=len(target),
            nth_gate=nth_gate,
            control_bitsize=control_bitsize
        ).on_registers(
            control=control,
            selection=selection,
            ancilla=ancilla,
            target=target
        )

Simulation of Hubbard model using the newly added Select / Prepare primitives is described in section V of https://arxiv.org/abs/1805.03662.

We should write a notebooks to:

1. Implement the select and prepare unitaries tailored for hubbard model in a notebook. This would demonstrate users how they can use existing gate primitives (like UnaryIteration, PrepareUniformSuperposition etc.) and newly added API abstractions (like GateWithRegisters primitive) to implement their own optimized constructions for different chemistry use cases.

   • Note: The select / prepare gates in the notebooks should ideally just be GateWithRegisters that defined a decompose method.
   • If any gate primitives are missing, add them to the repo before implementing the notebook.

2. Figure out and implement utilities that would enable us to get the coefficients of the Hubbard model Hamiltonian using the indexing scheme described in the paper. @ncrubin Maybe you can look into this?

note to self: put the following somewhere:

@dataclasses.dataclass(frozen=True)
class GateSystem:
    gate: GateWithRegisters

    @cached_property
    def r(self):
        return self.gate.registers

    @cached_property
    def quregs(self):
        return self.r.get_named_qubits()

    @cached_property
    def operation(self):
        return self.gate.on_registers(**self.quregs)

    @cached_property
    def circuit(self):
        return cirq.Circuit(self.operation)

The following will make tests and notebook demos easier. It's basically a "view" on a GateWithRegisters. Maybe it could be used elsewhere in the codebase too? or just added to GateWithRegisters?

• multiple control bits
• inverted controls ("open circle" controls)
• Flattening with existing control register

I propose we add an additional argument that gives the name of the desired control register so that the user can have control (heh) over the flattening. Example:

ca = Controlled(Atom(), ctrl_reg_name='control')
cca = Controlled(ca, reg_name='control')  # `control` register flattened

ca = Controlled(Atom(), 'control1')
cca = Controlled(Atom(), 'control2')  # two regs, not flattened

Following #140 , it only works on one composite bloq where each of the components implement the add_my_tensors protocol. We need to make it work recursively, in tandem with decompose_bloq.

From Nick:

The "programmable rotation gate array" is a useful primitive for double-factorized and THC factorized Hamiltonians. See Pg. 45 of the https://arxiv.org/pdf/2007.14460.pdf
This is the core (and most expensive primitive) of the better qubitization algorithms.

This is yet another place where I need to co-develop a protocol and something to test it against. I'm planning on splitting up as:

• Write a classical simulation protocol for bloqs; compositebloq version recurses
• Have a multi-controlled version of And for (simple) testing of the protocol #167
• Support auto-adjoint of multi-control And (and other decomposable bloqs) #168 #172

#158 introduces a TODO which should be fixed once the PR is merged. See #158 (comment) for more details.

Right now bb.add_from will "flatten out" a composite bloq during construction but it does not solve the issue of: given a composite bloq, decompose and flatten parts or all of the suboperations.

This could be useful for #150

The selected majorana gate should apply |n> Y_n Z_{n-1} ... Z_{0} | psi>, I noticed that if I set n to zero and apply the gate to the zero state it produces -1j|1>, rather than 1j|1>. Is this a global phase issue or something else?

Here's an example based on the unit test

import cirq
import numpy as np

import cirq_qubitization as cq
from cirq_qubitization.bit_tools import iter_bits
from cirq_qubitization.cirq_infra import testing as cq_testing

target_gate = cirq.Y
target_bitsize = 4
selection_bitsize = 2

greedy_mm = cq.cirq_infra.GreedyQubitManager(prefix="_a", maximize_reuse=True)
with cq.cirq_infra.memory_management_context(greedy_mm):
    gate = cq.SelectedMajoranaFermionGate(
        selection_bitsize, target_bitsize, target_gate=target_gate
    )
    g = cq_testing.GateHelper(gate)
    assert len(g.all_qubits) <= gate.registers.bitsize + selection_bitsize


sim = cirq.Simulator(dtype=np.complex128)
# Initial qubit values
qubit_vals = {q: 0 for q in g.all_qubits}
# All controls 'on' to activate circuit
qubit_vals |= {c: 1 for c in g.quregs['control']}
# Set selection according to `n`
n = 0
qubit_vals |= zip(g.quregs['selection'], iter_bits(n, selection_bitsize))

initial_state = [qubit_vals[x] for x in g.all_qubits]

result = sim.simulate(
    g.decomposed_circuit, initial_state=initial_state, qubit_order=g.all_qubits
)
sub_initial_state = [qubit_vals[x] for x in g.quregs['target']]
expected_target_state = cirq.Circuit(
    [cirq.Z(q) for q in g.quregs['target'][: n]], # Typo in test where upper limit is set to n - 1 ?
    target_gate(g.quregs['target'][n]),
    [cirq.I(q) for q in g.quregs['target'][n + 1 :]],
).final_state_vector(initial_state=initial_state, qubit_order=g.all_qubits)
print(cirq.dirac_notation(expected_target_state))
print(cirq.dirac_notation(result.final_state_vector))

which prints

1j|1001000000⟩
-1j|1001000100⟩

Also why is the ancilla qubit still set for the unary iteration route? Shouldn't this toggle off again?

We will need to build up the primitives of the library and the associated costs. Here I will keep a running list of primitives I find that are useful and where to find their references. @tanujkhattar

1. Binary Squaring (Appendix G 2105.12767, Lemma 7). Square an n-bit binary number using $n^2 - n$ Toffoli gates.
2. Sum of 3 n-bit numbers (Appendix G 2105.12767, Lemma 8) in cost $3n^2 - n -1$ Tofflis
3. Sum of the squares of k n-bit numbers (Appendix G 2105.12767, Lemma 9) costing $kn^2$ Toffli gates
4. Binary products of one n-bit number and one m-bit number (Appendix G 2105.12767, Lemma 10) costing $2nm - n$ Toffolis where $n \geq m$
5. $n$ -bit adder ( Quantum 2, 74 (2018)) $n$-Toffoli gates (expand on this more)
6. Bitonic Swap network on n-items uses a number of comparators (less than or equal operations written to a bit) that is upper bound by $\rfloor n/2 \lfloor q(q+1)/2$ where $q = \lceil \log(n)\rceil$
7. Comparators between two n-bit numbers costs $4n - 3$ Toffoli (npj Quantum Information volume 4, Article number: 22 (2018), Appendix)
8. Synthesizing an element of SU(2) costs $1.15\log(1/\epsilon) + 9.2$ T-gates on average (Phys. Rev. Lett. 114, 080502 )
9. Uniform superposition over $M = 2^{k}L$ numbers where $L$ is odd. (linear T-paper) $k + 2 \log(L) + O(1)$, which includes $\log(L)$ ancilla, and $2k + 10 \log(L) + \mathcal{O}(\log(1/\epsilon))$ T-gates if the protocol is controlled and $8\log(L) +\mathcal{O}(\log(1/\epsilon))$ T-gates if it is not. if $L=0$ then T-count is zero. If $L=1$ T-count is $2k$. The $\mathcal{O}(\log(1/\epsilon))$ is from circuit synthesis and usually goes as $1.15 \log(1/\epsilon) + 9.2$ on average.

def uniform_prepare_cost(num_items: int, controlled=False, 
                         epsilon_for_rotations=1.0E-8):
    """return T-count for construction of a uniform superposition

    :param int num_items: number of items to generate superposition over
    :param bool controlled: (Default false). Flag if circuit is 
                            controlled or not
    :param epsilon for rotations: Precision for Z-rotations in preparation.
                                  1.0E-8 is about 30 T-gates per rotation.
    :returns: T-count.  ancilla, T-count.
                        Space complexity is k + 2 log(L) + O(1). 
                        The factor of 2 comes from the unary 
                        iteration on log(L), + O(1) is from the

    """
    import numpy as np
    from sympy import factorint
    # get factorization of num_items = 2^{k}L where L is odd
    if num_items % 2 == 1:
        k = 0
        L = num_items
        factors = factorint(num_items)
    else:
        factors = factorint(num_items)
        if 2 in list(sorted(factors.keys())):
            k = factors[2]
            L = num_items // 2**k
    if not np.isclose(2**k * L, num_items) or L % 2 == 0:
        raise ValueError("Factorization of num_items into 2^k L form was unsuccessful")

    precision_rotation_cost = np.ceil(1.15 * np.ceil(np.log(1/epsilon_for_rotations)) + 9.2)
    if L == 1 and not controlled:
        return 0, 0
    elif L == 1 and controlled:
        return 0, 2 * k
    elif controlled and L > 1:
        return np.ceil(np.log2(L)) + 1, 2 * k + 10 * np.ceil(np.log2(L)) + precision_rotation_cost
    elif not controlled and L > 1:
        return np.ceil(np.log2(L)) + 1, 8 * np.ceil(np.log2(L)) + precision_rotation_cost

10. Uniform superposition over unary representation $n$-numbers on $n$-bits (one-hot-encoding), $n$ controlled rotations (not sure the breakdown of cost here) + $k$ CNOT ((npj Quantum Information volume 4, Article number: 22 (2018), Appendix))
11. SelectSWAP where selection register spans integers $[0, k-1]$ in binary and swap is on an $\log(m)$-bit register with a $\log(N)$-bit register costs $k\lceil \log(m)\rceil + k\lceil \log(N) \rceil$
12. MultiControl-X $C^{n}X$ costs $2(n-1)$ Toffoli and $n-1$ ancilla (Mike and Ike Figure 4.10)
13. Decrement a register of size $\log(N)$ by 1 costs $\sum_{x=1}^{\log(n)-1}C^{x}X$ Toffoli. A controlled version is $\sum_{x=1}^{\log(n)-1}C^{x+1}X$ Toffoli

xref #126 (comment)

I prototyped a new Bloq.wire_up(**soq_map) approach to building composite bloqs. Behind the scenes, this hides a reference to the current BloqBuilder in the input soquets.

• we'd need to somehow flush these references after the composite bloq is built or we could leak memory(?)
• we'd maybe (??) need to worry if there are -- like -- two bloq builders going at once
• for purely allocating bloqs (to add) there's no way to pull this trick
• for decomposing a purely allocating bloq there's no way to automaticall hide the bloqbuilder in the initial soquets

Ref #33 #32 : we're probably going to have a variety of things we want to do to our compute graphs.

• Cirq-style "protocols" that leans into Python duck-typing and has the fallback logic inside a top-level free function
  • can be hard to follow the control flow if you're just looking at one type
• object-oriented abstract methods that can call super() to get default behavior
• functional-style pattern matching

Fun reading: https://craftinginterpreters.com/representing-code.html#the-expression-problem

By adding qubit registers and overriding on_registers() method which accepts qubit registers, it will be easy for gates to convey / accept the number of qubits that they expect.

However, Often we have optimized implementations when the gate can accept dirty qubits instead of necessarily needing clean qubits (eg: SelectSwap QROAM defined in Fig1.d) of https://arxiv.org/abs/1812.00954). It would be nice if gates can express whether a register they expect should be "clean" or "dirty" so that a QubitManager / user constructing circuits can inspect this and pass a dirty register instead of passing a clean register to the gate.

At some point in the future, we'll probably want (sub)modules. Loose proposal:

• cirq_qubitization/ aka q.*tran
  • a module for abstractions
    • e.g. gate_with_registers.py
    • e.g. quantum graph #84 stuff
  • algos for all our GateWithRegisters definitions (I like how we currently only have a couple in each python file. Let's stick to that)
    • qubitization submodule - specifically chemistry stuff
    • shor submodule - specifically shor stuff
    • unary_iteration.py - re-usable important concepts
  • static_analysis or something like that -- module for putting protocols. maybe expand to include simulators?
    • jupyter_tools.py
    • t_complexity.py

Keeping our modules (ie python modules) pretty small and focused as we've been doing should make this not as hairy as it otherwise could have been.

I've subconsciously written this in dependency order. The abstractions stand alone, the algos and gates use the abstractions, and the static analysis plugs the two together

@mpharrigan Have you already thought about this problem? Specifically, suppose we have a CompositeBloq and we want to construct a controlled / multiplexed version of the corresponding composite bloq. How do we do it? Can we implement a pattern similar to Cirq where each Bloq would have a controlled_by() method which can be called to generate a controlled version of that bloq?

For implementing select / prepare for chemistry Hamiltonians as described in https://arxiv.org/abs/1805.03662 (eg: Fig 19 for hubbard model), we need to add support for iterating on multiple selection registers, each with a specified iteration length, to the Unary iteration
gate.

In other words, we want to do the following:

for p_x in range(M):
    for p_y in range(M):
        for alpha in range(2):
           // Index target register and apply operations using p_x, p_y and alpha 

and right now, unary iteration only supports doing the following:

for selection in range(iteration_length):
    // Apply `nth_operation` to target register which selection registers stores integer `selection`. 

build_composite_bloq is expected to return a Dict[str, Soquet] where the key is supposed to be value.reg.name (i.e. the name of the register that the soquet in the value is an instance of).

Since we already have the key information stored as part of the value, we can construct the dictionary automatically at the call site using an unordered sequence of soquets that can be returned from the build_composite_bloq method.

So, for example, the TestComposite implementation would change from:

https://github.com/quantumlib/cirq-qubitization/blob/0e54017473471638b6226a9715557bfb5e0473ab/cirq_qubitization/quantum_graph/composite_bloq_test.py#L52-L57

to:

    def build_composite_bloq(
        self, bb: 'CompositeBloqBuilder', q1: 'Soquet', q2: 'Soquet'
    ) -> Tuple[Soquet, ...]:
        q1, q2 = bb.add(TestBloq(), control=q1, target=q2)
        q1, q2 = bb.add(TestBloq(), control=q2, target=q1)
        return (q1, q2)

@mpharrigan Thoughts?

I put up a branch of the start of my subprepare to demonstrate where we need to improve the existing primitives.

SUBPREPARE involves a lot of different primitives where logic is provided by the user. A question about how to allocate the ancilla needed for each step needs to be worked out.

For example, the oracle has 4 main components: 1) Uniform_L, alt_keep_qrom, LessThanEqual, and coherent swap. Generically, the input and output registers size is 2 * logL + 2 mu + 1. But each primitive uses some number of ancilla qubits. Uniform uses 1 ancilla, QROM should use len(select_register) qubits (for the AND), and the LessthanEqual takes some number of ancilla depending on implementation. A naive estimate on maximum number of qubits to take is just the sum of all those ancilla plus the original registers. This will likely blow up the total number of qubits.

For testing this circuit the current settings use mu == 4 select register size =3 and thus the total input/output register is 15 qubits. But counting ancilla I won't be able to even simulate the output of this small example.

We have recently added a bunch of primitives for simulating chemistry Hamiltonian's. However, the ultimate goal is to be able to do resource estimation on circuits constructed using these primitives. Write an analogue of QCTraceSimulator in Q# that can consume Cirq circuits and do resource estimation on those circuits.

Some Potential design considerations for accurate resource estimation by compiling the constructed circuits:

• cirq.estimate_resources(circuit, config = esimation_config, gateset = target_gateset) where target_gateset can be T + Cliffords + Measurement, Toffoli + Cliffords + Measurement etc.
• Implement (hardcoded + analytical) decompositions of known (and unknown) gates into the target gatesets supported above by resource estimation.
• Provide support for different resource estimation configurations (for example: control tradeoff between optimizing for depth vs qubit count).
• Find a way of replacing different implementations of a primitive (eg: AND / Swap / etc.) that have different decompositions optimized for T-count / circuit depth / qubit count etc.

• line-too-long: the code parts are covered by the formatter. Docstrings sometimes are too long but it's annoying to re-wrap by hand (i.e. we should have a tool do this) and there are some places where it would likely make it less readable or parse wrong (latex formulas, markdown links)
• unused-variable: used in various places, particularly multi-return-value unpacking. Readability could be hindered by replacing meaningful names with underscores.

Right now, the bloqs-to-cirq conversion is not well tested, brittle, only is supported by a small number of bloqs, and only works for thru-bloqs. We can use the new cirq qubit allocation stuff to support more bloq-to-cirq conversion. The code can also be cleaned up

• Gates should expect and expose qubit registers and we should make it simpler for users to write new gates which can be decomposed using qubit registers.
• Migrate existing gates / methods to start using the newly added qubit registers.