Small note: A circuit of random toffoli gates (without any ancilla 1-bits) always maps all 0s to all 0s and would make the no-coincidence conjecture trivially true. I’m not sure how Gay et al. 2025 constructs random toffoli circuits to avoid this, but they must do it somehow in order for their Theorem 2 to be true.
Small note: A circuit of random toffoli gates (without any ancilla 1-bits) always maps all 0s to all 0s and would make the no-coincidence conjecture trivially true. I’m not sure how Gay et al. 2025 constructs random toffoli circuits to avoid this, but they must do it somehow in order for their Theorem 2 to be true.