Custom adjoint for QROM / SelectSwapQROM?

[fdmalone]

In appendix C an algorithm is described for uncomputing table lookups. The THC paper also quotes a lower cost for inverting regular old qrom on page 15 cf. listing 2 and 5

[fdmalone]

xref #368

[fdmalone]

Comparison between QROAM and SelectSwapQROM, both should scale like d^{1/2}.

[fdmalone]

code:

import matplotlib.pyplot as plt
import numpy as np
from qualtran.bloqs.basic_gates import TGate
from qualtran.bloqs.chemistry.black_boxes import QROAM
from qualtran.bloqs.chemistry.chem_tutorials import plot_linear_log_log
from qualtran.bloqs.select_swap_qrom import SelectSwapQROM

if __name__ == "__main__":
    values = np.zeros((9, 5))
    for i, num_spin_orb in enumerate(range(10, 100, 10)):
        num_mu = 4 * num_spin_orb
        d = num_mu * (num_mu + 1) // 2
        nmu = num_mu.bit_length()
        qroam = QROAM(data_size=d, target_bitsize=sum((1, 1, nmu, nmu, 20)))
        sel = SelectSwapQROM(
            [int(x) for x in np.random.randint(0, 10, d)],
            target_bitsizes=(sum((1, 1, nmu, nmu, 20)),),
        )
        t_qroam = qroam.call_graph()[1][TGate()] // 4
        t_sel_swap = sel.call_graph()[1][TGate()] // 4
        t_qroam_adj = qroam.adjoint().call_graph()[1][TGate()] // 4
        t_sel_swap_adj = sel.adjoint().call_graph()[1][TGate()] // 4
        values[i] = [d, t_sel_swap, t_qroam, t_sel_swap_adj, t_qroam_adj]

    fig, ax = plt.subplots(1, 1)
    plot_linear_log_log(ax, values[:, 0], values[:, 1], label='SelectSwapQROM', color='C0')
    plot_linear_log_log(ax, values[:, 0], values[:, 2], label='QROAM', color='C1')
    plt.xlabel('$x$')
    plt.ylabel('Toffolis')
    plt.savefig('scaling.pdf')
    plt.cla()
    plt.title('Adjoint')
    plot_linear_log_log(ax, values[:, 0], values[:, 3], label='SelectSwapQROM', color='C0')
    plot_linear_log_log(ax, values[:, 0], values[:, 4], label='QROAM', color='C1')
    plt.xlabel('$x$')
    plt.ylabel('Toffolis')
    plt.savefig('scaling_adjoint.pdf')
    plt.cla()