Costs for frequently used primitives

[ncrubin]

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. [x] Binary Squaring (Appendix G 2105.12767, Lemma 7). Square an n-bit binary number using $n^2 - n$ Toffoli gates.
2. [x] Sum of 3 n-bit numbers (Appendix G 2105.12767, Lemma 8) in cost $3n^2 - n -1$ Tofflis
3. [x] Sum of the squares of k n-bit numbers (Appendix G 2105.12767, Lemma 9) costing $kn^2$ Toffli gates
4. [x] 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. [x] $n$ -bit adder ( Quantum 2, 74 (2018)) $n$-Toffoli gates (expand on this more)
6. [x] 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. [x] Comparators between two n-bit numbers costs $4n - 3$ Toffoli (npj Quantum Information volume 4, Article number: 22 (2018), Appendix)
8. [x] Synthesizing an element of SU(2) costs $1.15\log(1/\epsilon) + 9.2$ T-gates on average (Phys. Rev. Lett. 114, 080502 )
9. [x] 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. [x] 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. [x] 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

[fdmalone]

I can start implementing these.

[tanujkhattar]

MultiControl-X $C^{n}X$ costs $2(n-1)$ Toffoli and $n-1$ ancilla (Mike and Ike Figure 4.10)

There is a spectrum of constant factors that you can achieve depending upon the number and type of ancilla qubits available. Specifically,

• n - 2 (burnable) clean ancillas: ~n Toffoli's (using And gate + measurement based uncomputation)
• n - 2 (non-burnable) clean ancillas: ~2n Toffoli's (uncomputation using toffoli's, as given in Mike and Ike)
• n - 2 dirty ancillas: ~4n Toffoli's (2 V chains of ~2n each)
• 1 (burnable) clean ancilla: ~4n Toffoli's (2 - $C^{n/2}$ chains using dirty borrowable qubits)
• 1 (non-burnable) clean ancilla: ~6n Toffoli's (3 - $C^{n/2}$ chains using dirty borrowable qubits)
• 1 dirty ancilla: ~8n (4 - $C^{n/2}$ chains using dirty borrowable qubits)

A good summary and relevant constructions can be found in https://algassert.com/circuits/2015/06/05/Constructing-Large-Controlled-Nots.html

[fdmalone]

SelectSwap and MultiControl-X are implemented in #220