\documentclass[12pt]{article}

\usepackage{hyperref}

\usepackage{amssymb, amsmath, lineno, amsthm, pdfsync, bbm, graphicx}
\usepackage{MnSymbol,wasysym}


\tolerance=2000
\textwidth 6.55in
\textheight 9.0in
\oddsidemargin 0.001in
\evensidemargin 0.001in
\topmargin -0.4in

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{theoremnonum}{Theorem} 
\newtheorem{definition}{Definition}[section] 
\newtheorem{lemma}[theorem]{Lemma} 
\newtheorem{corollary}[theorem]{Corollary} 
\newtheorem{claimnonum}{Claim} 
\newtheorem{mycomment}{comment}[section] 
\newtheorem{conjecture}[theorem]{Conjecture} 
\newtheorem{problem}{Problem} 
\newcommand{\finishproof}{~$\Box$}
\newtheorem{remark}{Remark} 


\newcommand{\AND}{\; \wedge \;}

\newcommand{\SAT}{{\sf SAT}}
\newcommand{\DTIME}{{\sf DTIME}}
\newcommand{\NTIME}{{\sf NTIME}}
\newcommand{\DSPACE}{{\sf DSPACE}}
\newcommand{\NSPACE}{{\sf NSPACE}}
\newcommand{\EE}{{\sf E}}
\newcommand{\EXP}{{\sf EXP}}
\newcommand{\NEXP}{{\sf NEXP}}
\newcommand{\PSPACE}{{\sf PSPACE}}
\newcommand{\eL}{{\sf L}}
\newcommand{\NL}{{\sf NL}}
\newcommand{\LOGSPACE}{{\sf LOGSPACE}}
\newcommand{\Pe}{{\sf P}}
\newcommand{\NP}{{\sf NP}}
\newcommand{\coNP}{{\sf coNP}}
\newcommand{\FP}{{\sf FP}}
\newcommand{\PH}{{\sf PH}}
\newcommand{\CH}{{\sf CH}}
\newcommand{\PP}{{\sf PP}}
\newcommand{\num}{{\sf\#}}
\newcommand{\numP}{{\sf\#\Pe}}
\newcommand{\ParP}{{\mbox{$\oplus$\Pe}}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}} 
\newcommand{\C}{\mathbb{C}}
\newcommand{\R}{\mathbb{R}} 
\newcommand{\ket}[1]{{|{#1} \rangle}} 
\newcommand{\bra}[1]{{\langle {#1}|}}
\newcommand{\bracket}[2]{{\langle {#1} | {#2} \rangle}}
\newcommand{\nb}{{\bf {\sf n}}} 
\newcommand{\Xb}{{\bf {\sf X}}}
\newcommand{\Xbi}{{\Xb}_i}
\newcommand{\Xbj}{{\Xb}_j}
\newcommand{\nbt}{{\tilde{\nb}}}
\newcommand{\nbi}{{\nb_i}}
\newcommand{\nbj}{{\nb_j}}
\newcommand{\nbti}{{\tilde{\nb}_i}}
\newcommand{\nbtj}{{\tilde{\nb}_j}}
\newcommand{\Sb}{{{\bf{\sf S}}}}
\newcommand{\Cb}{{\bf {\sf C}}}
\newcommand{\Zb}{{\bf {\sf Z}}}
\newcommand{\Yb}{{\bf {\sf Y}}}
\newcommand{\Hb}{{\bf {\sf H}}}
\newcommand{\Ub}{{\bf {\sf U}}}
\newcommand{\Ufb}{{\bf {\sf U}}_f}

\sloppy
 
\begin{document}
\thispagestyle{empty}
% The paper really starts here.

\noindent {\bf Assignment 3}\\
\noindent DUE: Tuesday, beginning of lecture 3/14/2023 (FIRM!!!), work individually.\\[-0.2in]

\begin{enumerate}
\item Some generalizations of our study of the Bloch sphere:
\begin{enumerate}
\item As we saw, modulo overall phase\footnote{Which is to say, {\it ignoring} the overall phase, treating any such factor as though it were $1$.}, we can write any qubit as
$\ket{\psi} = \cos(\theta/2)\ket{0} + e^{i\varphi}\sin(\theta/2)\ket{1}$,
where $0 \le \theta \le \pi$ and $0 \le \varphi \le 2\pi$.
Determine, again modulo overall phase, the unique qubit $\ket{\psi^{\perp}}$ that is orthogonal
to $\ket{\psi}$ (i.e., such that $\bracket{\psi^\perp}{\psi^\perp} = 1$ and $\bracket{{\psi^\perp}}{\psi} = 0$), written in terms of $\theta$ and $\varphi$.
\item Using your answer of part (a), show that $\ket{\psi}$ and $\ket{{\psi}^\perp}$
are antipodal\footnote{I.e., on opposite sides of the sphere, similar to the north and south pole. E.g., Augusta, Australia is the closest city to the antipodal point of Boston.} points on the Bloch sphere.
\item Prove, conversely, that any two antipodal points on the Bloch sphere correspond
to orthogonal qubits.
\item Recall from linear algebra that two orthonormal vectors span a 2D vector space (of which the space of qubits is one example, in which we have been using $\ket{0}$ and
$\ket{1}$ as a basis). Thus we ought to be able to write any qubit as
$\gamma\ket{\psi} + \delta{\ket{\psi^\perp}}$ where $|\gamma|^2 + |\delta|^2 = 1$. Indeed,
one may speak of ``measuring in the $\ket{\psi},\ket{\psi^\perp}$ basis\footnote{A technique often used in quantum computing, although we likely will not encounter it this semester.}," which essentially
 means a $|\gamma|^2$ probability of winding up
in the state $\ket{\psi}$ and a $|\delta|^2$ probability of winding up in the state
$\ket{\psi^\perp}$. Recall the geometric picture we had for these probabilities for
qubits in the computational basis (where $\ket{\psi} = \ket{0}$ and
$\ket{\psi^\perp} = \ket{1}$. Show that the same geometric prescription works for
probabilities when measuring in the $\ket{\psi},\ket{\psi^\perp}$ basis.
\end{enumerate}
\item One can generalize the Deutsch Algorithm to accept arbitrary two-bit inputs (rather than just 0 in the first bit and 1 in the second). The generalized relation is,
\begin{eqnarray}\label{eqn:more-general}
   (\Hb\otimes\Hb)\Ufb(\Hb\otimes\Hb)\ket{x,y} = (-1)^{yf(0)}\ket{x\oplus(y\cdot(f(0)\oplus f(1))), y}.
\end{eqnarray}

Or, written as a circuit:

\centerline{ \input{deutsch.pdf_t}}

Of course, if you plug in $x = 0$ and $y=1$, you obtain the relation proved in class, namely, $(\Hb\otimes\Hb)\Ufb(\Hb\otimes\Hb)\ket{0,1} = (-1)^{f(0)}\ket{f(0)\oplus f(1), 1}$.

By carefully tracing through the proof of the latter as given in class, but now including
the Boolean variables $x, y$, prove Eq.~(\ref{eqn:more-general}) as given above.


\item In the Deutsch-Jozsa algorithm, we are promised that the function $f:\{0,1\}^n \rightarrow \{0,1\}$ is either balanced or constant. Explain what happens to the algorithm if $f$ is neither balanced nor constant.

\item In Deutsch/Josza and elsewhere we're dealing a lot with $\Hb^{\otimes n}$ and have, perhaps, lost track
of the fact that it can be represented as a $2^n \times 2^n$ matrix of $\pm 1$'s
(and it is these that are generally known as Hadamard matrices, not just the 
$2 \times 2$ version). 
Let us index each row and column by $n$ bits, i.e., a row is determined by $r$ where
$r$ is a string of $n$ bits, and similarly for column $c$. Prove, by induction on
$n$, that the $(r,c)$ element of $\Hb^{\otimes n}$ is $\frac{1}{2^{n/2}}(-1)^{r \cdot c}$, where
the ``$\cdot$" denotes inner product (that is,
$\sum_{i=0}^{n-1}r_ic_i$). Use this to prove that any two rows and
any two columns of $\Hb^{\otimes n}$ are orthonormal. 

\item Here are a couple of exercises to better acquaint yourself with the arguments regarding how the tail end of Simon's algorithm works.
\begin{enumerate}
\item Use Gaussian elimination (over $\Z_2$) to find the unique solution of the set of equations $a\cdot y^{(i)} \equiv 0\pmod{2}$, such that $a \not = 0$, given
by the following set of bit vectors $y^{(i)}$:
\begin{eqnarray*}
y^{(1)} & = & 1~0~1~0~1~1~0\\
y^{(2)} & = & 0~0~1~0~0~0~1\\
y^{(3)} & = & 1~1~0~0~1~0~1\\
y^{(4)} & = & 0~0~1~1~0~1~1\\
y^{(5)} & = & 0~1~0~1~0~0~1\\
y^{(6)} & = & 0~1~1~0~1~1~1
\end{eqnarray*}
(HINT: Regard this as a matrix equation $Ya = 0$, where the rows of $Y$
are the $y^{(i)}$. You can reduce the matrix to row echelon form by adding rows,
remembering that over $\Z_2$, we have $1 + 1 = 0$.)
\item Note in part (a) there were 6 equations in 7 unknowns, yielding a unique solution 
for $a$. Generally, in Simon's algorithm, we are content with $n-1$ linearly independent bit vectors $y$ obeying $y\cdot a \equiv 0\pmod{2}$ to determine all $n$ bits of $a$. But 
we may tend to think that $n$ equations are required to uniquely determine $n$ values. Why, in this circumstance, do $n-1$ equations suffice? Explain as precisely as you can. (You are welcome and encouraged to use any notions from linear algebra. If your answer relies on a particular theorem, state (no need to prove!) what theorem you are using.)

\end{enumerate}
\end{enumerate}

\end{document}
