Chapter 6

Exercises are from QUANTUM COMPUTING: A GENTLE INTRODUCTION, by Eleanor Rieffel and Wolfgang Polak, published by The MIT Press.

$\def\abs#1{|#1|}\def\i{\mathbf {i}}\def\ket#1{|{#1}\rangle}\def\bra#1{\langle{#1}|}\def\braket#1#2{\langle{#1}|{#2}\rangle}\mathbf{Exercise\ 6.1}$

Show that it is impossible to perform a reversible 'and' operation with only two bits.


$\mathbf{Exercise\ 6.2}$

a) Construct a classical boolean circuit with three input bits and two output bits that computes as a two-bit binary number the number of $1$ bits in the input.

b) Convert your circuit into a classical reversible one.

c) Give an equivalent quantum circuit.


$\mathbf{Exercise\ 6.3}$

Given two-qubit registers $\ket c$ and $\ket a$ and three-qubit register $\ket b$, construct the quantum circuit that computes $\mathit{Add}\;\ket{c}\;\ket{a}\;\ket{b}$.


$\mathbf{Exercise\ 6.4}$

a) Define a quantum algorithm that computes the maximum of two $n$-qubit registers.

b) Explain why such an algorithm requires one additional qubit that cannot be reused, i.e., the algorithm will have to have $2n+1$ input and output qubits.


$\mathbf{Exercise\ 6.5}$

Show how to construct an efficient reversible circuit for every classical circuit along the lines of the construction of section 6.2.2 but without the assumption that $t$ is a power of $2$. Give the time and space bounds for your construction.