Dalzell, McArdle, Berta, Bienias, Chen, Gilyén, Hann, Kastoryano, Khabiboulline, Kubica, Salton, Wang, and Brandão have posted a comprehensive assessment of state-of-the-art end-to-end resources needed for many quantum algorithms. Often Dalzell et al. provide qubit counts and T depths needed to implement various algorithms. Their analysis suggests that resources may be quite daunting, especially for algorithms admitting "only" a polynomial speedup.
But, has anyone gamed out roughly how many qubits, and how many gates, are required for Quantum Money from Knots? Do we know how complicated a verification circuit would be, to calculate the knot invariant (Alexander polynomial) and to apply the Markov chain (Reidemeister/Cromwell moves) in superposition?
We only know knot tables up to about 16 or so crossings; perhaps even a modest number of logical qubits (a couple hundred or so) would be of sufficient security. However, the verification circuits do intuitively feel intimidating - calculating Alexander polynomials and especially applying knot moves in superposition seem pretty tough with probably very deep (although polynomial) circuits. I'd guess a depth of several millions or more CCNOT (Toffoli) and CSWAP (Fredkin) gates to calculate the Alexander polynomial of such knot diagrams.
