The modular multiplication map as a quantum circuit. Let mZ2,N[2m] with N2, and a[N] with gcd(a,N)=1. Define the modular multiplication function fa:[2m][2m] for all x[2m] by fa(x)={axremNxifx[N]ifx/[N]. (a) Let a1[N] be the inverse of a modulo N and let j be a nonnegative integer. Show that fa1=fa1 and fa2j=fa2j rem N. (b) Outline a (2m+w)-qubit quantum circuit SfaC22m+w22m+w consisting of extensions of O(m2) at-most-three-qubit gates and w=O(m2) work qubits such that Sfax0m0w=xfa(x)0w for all x[2m]. (c) Present an (m+w)-qubit quantum circuit UfaC2m+w2m+w consisting of extensions of O(m2) at-most-three-qubit gates and w=O(m2) work qubits such that Ufax0w=fa(x)0w for all x[2m]. Hints: Part (a) is immediate. For part (b), start with a Boolean circuit, transform to a reversible circuit, observe that the transformation yzyyz is invertible, where yz denotes the bitwise exclusive or of the vectors y,z{0,1}m, and apply uncomputation to reset the w work bits. For part (c), use Sfa to compute and Sfa1 together with yzyyz to uncompute. You may also find Problem 1(a) useful