Useless Solutions Call for Useless Problems

Useless Solutions Call for Useless Problems

Consider a toy problem wherein we’re given a black box function called $f$ which operates on four 1-bit inputs we’ll label $b_1, b_2, b_3$ and $a$. $f$ is stateful, and perhaps better interpreted as a “circuit” with the following behavior:

The catch is that any subset of those cases might be ignored, deleted, faulty, flipped by a gamma ray¹, etc. E.g., we might receive an $f$ with the second case “deleted” resembling:

For an instance of this problem with $n$ inputs, there are $2^{n-1}$ possible subsets of “missing” statements which can be interpreted as toggles acting on our accumulator. ($2^{n-1}$ since we discount the $a$ which accumulates the effect of the other inputs).

We can consider the set of all possible configurations of this black box function $f$ with 4 arguments (3 input bits and one accumulator bit):

Where the subscripts correspond to which cases are present in the function. The problem statement is: given some unknown function $f \in F_n$, we want to determine which $f$ we’re dealing with in as few invocations or “queries” to $f$ as possible.

An initial naive approach might be to select an arbitrary initial binary string, say $\bar 0$, flip the first bit, pass it to $f$ and observe what happens. For $f \in F_3$ this might look like:

This tells us that the first case (toggling $a$ contingent on toggling $b_1$ is present in our given $f$). Not that this logarithmically eliminates fully half of the $2^3$ possible $f$s (the ones where $b_1$ is absent, deleted, corrupted, etc.):

We can repeat with another input string to target the behavior of another of the cases, say:

which tells us that the case for $b_2$ is missing since $a$ was not toggled. So we can eliminate another half of the remaining possibilities:

And, finally, we isolate the behavior of the $b_3$ branch:

So we know that our given function must be $f_{b_1,b_3}$, but that took $n=3$ total invocations for a mystery function with 3 inputs. Can we do better? We might experiment with more “sophisticated” input string combinations, but we’ll quickly find that regardless of our input to $f$, we can never eliminate more than half the possible remaining answers at any iteration of this sluethy procedure.

To prove this, let’s consider what information we gain by sampling $f$. Or, donning our Shannon deerstalker, perhaps a better question to ask is: how much information do we gain?

The answer is –perhaps obviously from the framing of the problem statement thus far– precisely 1 bit of information which gets encoded in the last bit of the output $a$. So, the answer is, with classical computing techniques: … no, we cannot do better than $n$ queries to $f$.

Suppose that there did exist a procedure which lets us identify the $f \in F_3$ with only two invocations. We would have at our disposal 2 bits of information:

Leaving us with four possible combination of $a_1, a_2$:

But there are still eight possible choices for $f \in F_3$ and 2 bits of information still only inform on four of those possibilites, so we can conclude that any such procedure which claims perfect accuracy is WRONG since there’s simply not enough information. Not with classical computing techniques, that is. With quantum computing, we can get the number of invocations of $f$ down to one singular sample for any naturally numbered $n$ by leveraging some sick linear algebra on the properties of qubits.

Quantum

A qubit is the fundamental data type in quantum computing. Typically denoted $|\psi\rangle$, with the bracket notation indicating that the value of $x$ can exist somewhere in between the two basic states: $|0\rangle$ and $|1\rangle$. The measure of a qubit’s propinquity to each basic state is denoted as an amplitude:

And we can omit the amplitude’s subscript when the basic state being referenced is unambiguous.

Crucially, we don’t need a concrete implementation of a device which can replicate superposition (though this is more achievable than we might initially assume) in order to reason about quantum quantities.

Properties of Qubits

Measuring a qubit’s amplitude collapses it to one of its basic states depending on the amplitude. The exact rule governing which basic state is observed when a qubit collapses is given by the amplitude of that basic state squared:

E.g. for a qubit $|x\rangle$ with amplitude $\alpha_{|0\rangle} = 0.8$, and since we know that the probability of observing one of the two possible basic states must sum to one, we have:

Note that this also allows for negative amplitudes, e.g. this is an equally valid quantum state for $|x\rangle$ to be in:

Since $\alpha_{|0\rangle}^2 + \alpha_{|1\rangle}^2 = 1$.

Similarly to classical bits, for $n$ qubits, there are $2^n$ possible measurements which are the $2^n$ possible basic state configuration after measuring each of the qubits’ amplitudes. However, collections of qubits form quantum systems, the constituents of which cannot be meaningfully considered in isolation.

E.g. For $n=2$ qubits, we have a system of 4 basic states:

With some amplitude on each of the basic states where the sum of the squares of said amplitudes is one:

While it may seem natural to assume that each qubit on its own has distinct amplitudes on each of its basic states, this is not the case. Together, the $n$ qubits jointly have amplitudes on each of their $2^n$ basic states. This property is called quantum entanglement and is precisely what gives rise to the clever solutions found in quantum programming which are not possible with conventional approaches.

Quantum Programming

A quantum program takes as input $n$ qubits in some valid superposition of the $2^n$ basic states and takes them to some other (excluding the identity QP, I guess) valid super positions. In other words, a quantum program is any set of operations which satisfies the pre- and post-condition:

Where $i$ is expressed in base 10 [footnote, this is a base joke. Base two]. A quantum operation we might be interested in to solve the problem from earlier would be qubit negation on $n$ qubits. This can be achieved by “swapping” amplitudes of corresponding basic states. The operation can be visualized on a $n-$dimensional cube. E.g., for $n=3$:

The “toggle” or negation operation swaps a corner on the face of the cube where $q_i = 0$ with The corner where $q_i = 1$, and $i \in \{1, 2, …, n\}$

This operation is one of three named for Mathematician Pauli, and is denoted $X$ or $\sigma_x$. We’ll cover the other two operations in a following section. Note that, without even knowing how to quantitatively represent this negation operation, we know that it is a valid one since it doesn’t violate the pre- and post-condition of squared amplitude summation to one.

To avoid have to bother validation summations for each quantum operation we might want to define, we can institute an abstraction constraint that these operations only define how each of the basic states are transformed in terms of one another rather than modifying amplitudes directly. This opens many direct analogs to linear algebra that might already be showing around the cracks of this ELI25AIDKALA² explanation.

This abstraction constraint begs the question, though, what about non-basic states? E.g. what if we composed a 1-bit probabilistic operator with our negation “gate” which toggles the a qubit of a basic state with $p = 2/3$ and does nothing the rest of the time:

We can again visualize this behavior as a tree without having to worry our pretty little brains with any quantitative conception of what the hell we’re talking about (pictures r fun):

We can see that the probability of observing any of the basic states of this system is just the product of the probabilities of descending down any branch $\pi$ of this amplitude tree that results in that basic state $|01\rangle$:

Quantum program analysis is almost identical, the only difference being that quantum instructions operate on amplitudes which can be negative whereas a classical stochastic decision tree operates on probabilities on the unit interval. Conveniently for us, this means that some of the amplitudes might cancel each other out, whereas in the classical context, probabilities are strictly additive (in the monotonically increasing sense of the word).

So far the two operations we’ve defined so far, $\sigma_x$ and simple conditionals, don’t offer any further utility than those gates which are already available in classical circuitry as evidenced by their amplitude trees which don’t introduce any quantum branching:

It’s now time to introduce non-trivial non-basic qubit states. Let’s define a unary function: $Rotate(q): |\psi\rangle \rightarrow |\psi\rangle$ with the following amplitude tree:

We can easily verify that it’s a valid quantum operation since it maps valid quantum states to other valid quantum states. Now suppose we have another operation $f$ which takes some qubit in the zero state and transforms it to a qubit with some amplitudes $x,y$ on each of its basic states s.t. $x^2 + y^2 = 1$. We can (non-rigorously) check that $Rotate$ is valid by passing $f(q)$ as its input and examining the resultant amplitude tree:

Collapsing the amplitudes to measure the distribution over basic states, we get:

So, $Rotate$ is valid $\blacksquare$. An example of an invalid operation might be assignment. Yes, that most basic of instructions we might expect to see in a program:

Verboten! We can develop some intuition about this by subjecting assignment to the same procedural treatment as $Rotate$:

Now, for a non-trivial quantum operation, and perhaps the most important (? depends who u ask, where my Hadamard truthers at), the Hadamard [Link to other mentions throughout the blog]:

Let’s observe how it behaves with some of our other operations:

And we can go a step further by enumerating the amplitudes on each of the basis states at each of the six steps of the program:

Note that – even though the $+0.5$ amplitude appears on the $|011\rangle$ basic state, the final amplitude on this state is zero because both of the branches where it appears have inverse amplitudes which cancel each other out. And herein lies the crux of quantum programming: designing algorithms where the amplitude of undesirable quantum states cancel out:

This isn’t always feasible, however. Sometimes the best we can do is leaving a subset of ”undesirable” output states with a minimal amount of amplitude and then relying on probabilistic correctness over a series of trials.

Designing Quantum Programs

Since the state of $n$ qubits can be fully described by a collection of $2^n$ amplitudes, it’s natural to model $n$ qubits as $2^n$-dimensional vectors containing amplitudes on each of the basic states:

With a vector spanning eight dimensions (1 for each basis) corresponding to each of the basic states, we can easily visualize up to three of those dimensions. And, per the sum-squared amplitudes theorem, we can geometrically represent the state of the qubits as a point on the $2^n$-dimensional unit sphere. This is fun to say, but for any number of qubits greater than 1, we need at least 4-dimensional space which is more than you might be able to visualize.³ Before getting bogged down with $n$-dimensional visualizations, let’s play with our linear algebraic interpretation of qubit state for $n=1$ which is nicely represented on the plane:

We can describe quantum instructions operating on qubits as matrices of transition amplitudes multiplied by the state vector.

Now, back to the harsh realities of $n > 3$-dimensional space, suppose we have two qubits $q_1, q_2$ and we want to compute the Hadamard matrix for this system: $H^{\otimes 2}$.

For $H_{q_1}$, we can just fill in transition amplitude entries in the matrix for basis state pairs where $q_2$ doesn't change:

And, similarly we can compute $H_{q_2}$ for values where $q_1$ doesn't change:

Furthermore, we can compose them via normal matrix multiplication to compute $H^{\otimes 2} = H_{q_1}\otimes H_{q_2}$ – and order actually doesn't matter for these operations since they modify different qubits by construction:

and we can further simplify the notation since the magnitude of all the entries are equivalent, and all we really care about is the sign.

Note as well that the "convolution" of $H^{\otimes 2}$ is itself composed of $H$:

Mystery Toggles Revisited

Finally, we can return to our mystery problem on $n$ toggles and leverage the Hadamard to improve upon our $O(n)$ classical solution.

Our solution is as follows:

1. initialize $n+1$ qubits, 1 for each possible toggle as well as an accumulator,
2. Toggle the accumulator
3. Apply $H^{\otimes n - 1}$
4. Invoke the oracle $f$ on our input string
5. Apply $H^{\otimes n - 1}$ again
6. Measure the amplitudes of the system to identify which cases are absent from $f$

To understand how and why this works, let's trace it for $n = 3$, with $f = f_{b_2}$ (only the second toggle is present).

First, we create our $2^n = 8$ dimensional state vector representing all combinations of $b_1b_2a$ with all of the amplitude on the zero state:

Next, we toggle the accumulator bit, transferring all the amplitude from $|000\rangle \rightarrow |001\rangle$.

Then, we apply $H^{\otimes 3}$ to the state vector:

and recall that matrix multiplication with a vector with a single entry of 1 essentially acts as a select on that column s.t. our resultant product is the second row of our Hadamard matrix as a column vector:

Then, we invoke $f$ on the quantum state which –if we remember that far back– toggles the accumulator iff $b_2$ in the input string is set. This has the effect of applying $f$ to each entry in the vector, examining the middle bit of each basis state:

Note that, prior to this step, all states where the accumulator bit was 1 had negative amplitude, and all states where the accumulator bit was 0 had positive amplitude. When we invoke the oracle $f$, the basis states where the accumulator doesn't change still have positive amplitude if the accumulator bit is unset and negative if it is set, just like before – but those basis states where the accumulator did get toggled now have the inverse amplitude pattern ($-$ if $a = 0$, and $+$ if $a = 1$) which encodes a sort of truth table for $f$ where positive amplitudes correspond to TODO: ???

In other words, taking the basis state $|010\rangle$ which has negative amplitude implies that if $b_1 =0, b_2 = 1, a =0$, then $a$ will be $1$ after $f$ is called. Conversely, in $|100\rangle$ the accumulator bit is unset since it has positive amplitude.

Now we run into another problem: if we were to try to measure the qubits now, the amplitudes would collapse to pure noise since all the magnitudes would cancel each other out and we'd effectively get a random 3-bit binary string as out output. To account for this, we just plop in another $H^{\otimes 3}$ and, curiously, the purpose of this operation is completely different to the columnal selection from earlier since our state vector is no longer of the correct form to pick a single entry.

Again, it's useful to visualize what happens when we perform this multiplication:

As we can see, as we compute the matrix multiplication all the amplitude values gradually accumulate on the $|011\rangle$ basic state such that when we measure all the qubits, we learn the configuration of the mystery $f \in F_3$ that we were given with $p = 1$. The proof that this program is correct for fixed $n$ is trivial via programmatically enumerating all variations of $f$.

If this seems like too convenient or mystically clever of a solution it's because this sequence of operations was discovered prior to the declaration of the problem statement. The problem of "mystery $f$" was retconned as a problem to motivate this demonstration of a quantum system offering constant time solution to a problem with linear complexity by classic means. This problem is known as the Bernstein-Vazirani problem, and is one of many similarly contrived examples of "quantum supremacy."

Formally, the Bernstein-Vazirani⁴ problem is posed: given an oracle $f: \{0, 1\}^n \rightarrow \{0, 1\}$ where all that's known of $f$ is that it's output is the dot product between the input vector and a secret string $s \in \{0, 1\}^n$ modulo 2, we're tasked with finding $s$ s.t.

More Math

Now that the gloves are off in terms of the linear algebra, let's revisit some of the earlier handwavey definitions of qubits and quantum gates.

Qubits as vectors

A qubit can be expressed as a linear combination of the amplitudes and the system's basis states:

where $a, b \in \mathbb C$, though we can largely ignore the complex components of pretty much all the systems and gates we'll cover (for explanations of the global phase described by complex components, ur gonna need an ELI35). As a linear combination, quantum states are easily expressed as vectors:

The basis states of a quantum state vector span the 2D Hilbert Space which is just a well-defined complex vector space where the inner product exists.

Normalization Condition

The aforementioned "validity" rule for quantum states is known as the normalization condition:

For an $n$-dimensional system, we sum over the squares of the amplitudes of all basic states:

Quantum Operations

Operations on single cubits can be expressed as 2x2 unitary and hermitian matrices. Unitary to ensure the conservation of amplitude, and Hermitian to ensure that the eigenvalues (measurable quantities which need to correspond to real world things) are real valued.⁵

A matrix $U$ is said to be unitary if its inverse equals its transpose conjugate (also known as the hermitian adjoint) $U^{\dagger}$:

The hermitian adjoint operation is a linear map which transposes an $m\times n$ complex matrix and conjugates each entry (negating the complex component).

For real matrices, the hermitian adjoint is just the transpose.

Bloch Sphere

Quantum operations on singular qubits can be visualized as maps between points on the unit sphere. As mentioned earlier, this also holds for systems of multiple qubits on hyper spheres but the utility of the Bloch sphere diminishes proportionately to one's ability to visualize higher dimensions and rotations therein.

Here, $\theta, \phi$ are the usual polar and azimuthal angles in spherical coordinate representation. The Pauli gates, then, are just rotations about these axes by $\pi$ radians. E.g.

again we drop the complex component since we're ignoring global phase of the quantum system, and just rotate dat boi about the x-axis (as observed in the planar example):

Similarly, this process yields a geometrically intuitive conception of the other two Pauli operations:

Note that each of these are involutory, meaning that their squares are equal to the identity matrix. From these Pauli matrices, we can also generalize to arbitrary rotation operations:

It should be clear(er) now that all qubit operations acting on an $n$-dimensional quantum system map a point on the hypersphere to another point, which can always be achieved via some rotation, e.g.

so the Hadamard is just a rotation about the diagonal on the xz-plane of the Bloch sphere. Two applications of a rotation by $\pi$ will complete a full revolution about the sphere, returning to the original point.

Multi-qubit Systems

Recall that singular qubits occupy 2D Hilbert Spaces:

The state vector of a composite system of two qubits is given by the tensor product of the two constituent state vectors being combined, where the tensor product $|\Psi\rangle$ is defined as follows:

In other words, the basis vectors of a 2 qubit system in $\mathcal H_{AB}$ are comprehensively enumerated:

In general, the tensor product of two matrices is given by:

And since the tensor product is distributive, we can also write a combination of operations in such a way is explicates the fact that each quantum operator is acting independently on the composite state space:

With this representation of multi-qubit systems, we can introduce some multi-qubit operations.

Multi-qubit Operations

Thus far, we've only defined single-qubit gates/operations, but we can also perform some actions on multiple qubits at a time, with a few crucial distinctions from classical logic gates. For starters, quantum gates must be reversible. Whereas it's entirely common for classical logic gates to map multiple inputs to a single binary output, since quantum systems model state changes in physical systems, the modifications made to each of the inputs must also be expressed in the output. The above description is phrased as a constraint, but it's really just a natural conclusion from the prior definitions about quantum operations being unitary & hermitian – which lets us simply apply the adjoint of an operation to "undo" it.

It should be straightforward to convince yourself that the input vector to these gates is not definitively knowable given the output bit/vector.

CNOT

The Controlled-NOT gate is analogous to the the classical XOR which can be thought of as addition $\mod 2$ given by the following truth table:

Observe that, for a 2 qubit system, $q_1$ remains unchanged, and the state vectors of $q_2 \in \mathcal H_{AB}$ are swapped:

Algebraically, we can express this as the matrix:

We can use CNOT to swap the states of two qubits the same way we might swap two classical variables' values without introducing a tmp value with three XORs: