Linear Equations

Introduction

Solving a system of linear equations is non-trivial. The problem can be formulated as:

$A \vec x = \vec b$

where $A$ is given as a matrix of coefficients, $\vec x$ represents the variables to be solved and $\vec b$ is given as the values to be used in the solution. Rearranging the terms:

$\vec x = A^{-1} \vec b$

The problem now becomes one of finding the inverse of the $A$ matrix. It can be shown that the complexity of this operation is $O(n^3)$. If $A$ is sparse, the complexity can be shown to be proportional to $O(N log N)$.

Seth, Lloyd and his colleagues at MIT had presented a Quantum algorithm with a complexity proportional to $O(logN)$. The complete presentation can be viewed at https://arxiv.org/pdf/1302.1210.pdf.

My attempt is to unravel the important aspects of the algorithm.

The algorithm

Let

$|\psi_0> = {\sqrt {2 \over T}} {\sum_{\tau = 0}^{T-1}} sin { {{\pi} (\tau + {1 \over 2})} \over T}|\tau>$

where T is an integer > 0

Apply ${\sum_{\tau = 0}^{T-1}}|\tau>|<\tau|^C ⊗{e^{iA\tau t_o} \over T} on |\psi_0>^C⊗|b_i>$

The above operation will generate eigen values and eigen vector using quantum phase transformation described at https://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm.

Fourier transforming the first register (there are 2 registers in the quantum phase transformation article above) gives the state

${\sum_{j=1}^N}{\sum_{k=0}^{T-1}} \alpha_{kj} \beta_j |k>|{u_j>}$

where |k> are the Fourier basis states.

Define:

${\vec \lambda_k} = {{2 \pi k} \over {t_0}}$

${\sum_{j=1}^N}{\sum_{k=0}^{T-1}} {\alpha_{kj}} {\beta_j} |{\vec \lambda_k}>|{u_j}>$

Adding an ancillary qubit and rotating conditioned on $|\vec \lambda_k>$ gives:

${\sum_{j=1}^N}{\sum_{k=0}^{T-1}} {\alpha_{kj}} {\beta_j} {|{\vec \lambda_k}>} {|u_j>} ( {\sqrt {1 - {C^2 \over {\vec \lambda_k^2}}}} |0> + {C \over {\vec \lambda_k}} |1>)$

If the quantum phase estimation is correct:

$\alpha_{kj} = 1$ if ${\vec \lambda_k|} = {\lambda_j}$ and $\alpha_{kj}=0$ otherwise

${\sum_{j=1}^N} {\beta_j}|u_j>( {\sqrt {1 - {C^2 \over {\vec \lambda_j^2}}}} |0> + {C \over {\vec \lambda_j}} |1>)$

The probability of the |1> qubit corresponds to the solution |x>

${\sqrt { 1 \over {{\sum_{j=1}^N}{C^2|{\beta_j|^2}/{|\lambda_j|^2}}}}}{\sum_{j=1}^N} {\beta_j}{C \over {\lambda_j}} |u_j>$

Since lambdas are eigen values, the inversion is assumed as solution which is the case when the matrix is diagnoal and sparse

For a discussion of this work and some circuits see https://quantumcomputing.stackexchange.com/questions/2439/quantum-algorithm-for-linear-systems-of-equations-hhl09-step-2-preparation

Grover's Algorithm

Introduction

Quantum computing has been a fascinating journey for me. Among all the algorithms I have studied Grover's algorithm (see his on-line article at https://arxiv.org/pdf/quant-ph/9605043.pdf) is the most fascinating one because it motivates quantum computer enthusiasts to use search in an unordered list, such as database entries, as a way to approach many of the complex computations involved in such problems as traveling salesman, decryption of cryptographic text, and password guessing.

At the core of quantum computing there is what is called a Qubit. A qubit is a super-position of a fundamental particle's, such as an electron's, spin states. For example: an electron's spin states are described as either up or down. In classical computers, the analogy is binary 0/1 number. Unlike classical bits, a qubit can be both 0 and 1 at the same time. This is given by the following representation:

$\psi = \alpha |1> + \beta |0>$

where $\alpha$ and $\beta$ are the amplitudes. The probabilities are given as:

$P_1 = {|\alpha|^2 \over {|\alpha|^2 + |\beta|^2}}$ and $P_0 = {|\beta|^2 \over {|\alpha|^2 + |\beta|^2}}$

This state persists, until one makes a measurement (see below), which upon measurement collapses to either 0 or 1. The super-position and what is known as the phase of the spin, gives several degrees of freedom that enable qubits to simultaneously represent exponential states.

At the moment most people simulate quantum computing on classical computers. I recommend reading https://www.codeproject.com/Articles/1131573/Grovers-Search-Algorithm-explained for a glimpse of java code and a worked out example. However, there seems to be evidence to suggest that at this time about 50 qubit quantum computing has been achieved in the laboratories across the world.

Condensed from https://people.cs.umass.edu/~strubell/doc/quantum_tutorial.pdf: Along with the superposition of states, Grover’s algorithm, and more generally the family of quantum algorithms that use what is known as amplitude amplification, exploit the qualities of quantum amplitudes that differentiate those amplitudes from simple probabilities. The key to these algorithms is the selective shifting of the phase of one state of a quantum system, one that satisfies some condition, at each iteration. Performing a phase shift of $\pi$ is equivalent to multiplying the amplitude of that state by −1: the amplitude for that state changes, but the probability--which is defined as the norm-square of amplitude-- of being in that state remains the same (since the probability disregards the sign of the amplitude). However, subsequent transformations performed on the system take advantage of that difference in amplitude to single out that state of differing phase and to ultimately increase the probability of the system being in that state. Such sequences of operations would not be possible if the amplitudes did not hold that extra information regarding the phase of the state in addition to the probability. These amplitude amplification algorithms are unique to quantum computing because of this quality of amplitudes that has no analog in classical probabilities.

Knowing quantum mechanics a little bit, I was curious to know how the amplitude of an elementary particle, such as a an electron, in a superposition state could be measured. Apparently there is such an instrument called Stern-Gerlach. https://en.wikipedia.org/wiki/Stern%E2%80%93Gerlach_experiment

Read on to appreciate the prospect of quantum computing that will make all of our complex tasks trifle easy one day.

Grover’s Algorithm

Quantum search

Grover’s algorithm performs a search over an unordered set of $N = 2^n$ items to find the unique element that satisfies some condition. While the best classical algorithm for a search over unordered data requires $O(N)$ time, Grover’s algorithm performs the search on a quantum computer in only $O(\sqrt N)$ operations, a quadratic speedup.

In order to achieve such a speedup, Grover relies on the quantum superposition of states. Like many quantum algorithms, Grover’s begins by putting the machine into an equal superposition of all possible $2^n$ states of the n-qubit register. Remember that means there is an equal amplitude of $1 \over {\sqrt {2^n}}$ associated with every possible configuration of qubits in the system, and an equal probability of $1 \over 2^n$ that the system will be in any of the $2^n$ states. All of these possible states correspond to all the possible entries in Grover’s database (he originally wanted his algorithm to lookup names in a database of phone numbers), and so starting with equal amplitudes assigned to each element in the search space, every element can be considered at once in a quantum superposition, and amplitudes can be manipulated from there to produce the correct entry in the database with a probability of “at least” 1/2.

Also note that in the following sections an Oracle is used to match the state with the expected value to determine if a solution has been found. The Oracle cannot affect the amplitude but can affect only the phase. So even though the Oracle "knows" the expected value, it cannot increase the amplitude to increase the probability.

Grover’s algorithm: How it works

Grover’s algorithm begins with a quantum register of n qubits, where n is the number of qubits necessary to represent the search space of size $2^n = N$, all initialized to |0>

$|0>^{⊗n} = |0>$

Note: ⊗ is the notation for vector cross-product

The first step is to put the system into an equal superposition of states, achieved by applying the Hadamard transform (https://en.wikipedia.org/wiki/Hadamard_transform) $H^{⊗n}$, which requires $O(log N) = O(log 2^n) = O(n)$ operations, n applications of the elementary Hadamard gate:

$|\psi> = H^{⊗n}|0>^{⊗n} ={1 \over {\sqrt {2^n}}} \sum_{x=0}^{2^{n}-1}|x>$

The next series of transformations is often referred to as the Grover iteration, and performs the amplitude amplification mentioned earlier, the bulk of the algorithm. The Grover iteration will be repeated $\pi \over {4 {\sqrt {2^n}}}$ times. According to Grover, in order to achieve optimal probability that the state that we ultimately observe is the correct one, we want the overall rotation of the phase to be $\pi \over 4$ radians, which will occur on average after $\pi \over {4 \sqrt {2^n}}$ iterations.

The Oracle ($\omega$)

The first step in the Grover iteration is a call to a quantum oracle, $\omega$, that will modify the system depending on whether it is in the configuration we are searching for. An oracle is basically a black-box function, and this quantum oracle is a quantum black-box, meaning it can observe and modify the system without collapsing it to a classical state, that will recognize if the system is in the correct state. If the system is indeed in the correct state, then the oracle will rotate the phase by $\pi$ radians, otherwise it will do nothing, effectively marking the correct state for further modification by subsequent operations. Remember that such a phase shift leaves the probability of the system being correct state the same, although the amplitude is negated. Quantum oracle implementations will often use an extra scratch qubit, but in this implementation the extra qubit is unnecessary, so the oracle’s effect on $|x>$ may be written simply:

$|x> \rightarrow (−1)^{f(x)}|x>$

Where f(x) = 1 if x is the correct state, and f(x) = 0 otherwise. The exact implementation of f(x) is dependent on the particular search problem.

Grover refers to the next part of the iteration as the diffusion transform, which performs inversion about the average, transforming the amplitude of each state so that it is as far above the average as it was below the average prior to the transformation, and vice versa. This diffusion transform consists of another application of the Hadamard transform $H^{⊗n}$, followed by a conditional phase shift that shifts every state except $|0>$ by −1, followed by yet another Hadamard transform. The conditional phase shift can be represented by the unitary operator $2|0><0| − I$:

$[2|0><0| − I] |0> = 2 |0> <0|0> − I = |0>[2 |0> <0| − I] |x> = 2 |0> <0|x> − I = − |x>$

Giving the entire diffusion transform, using the notation $\psi$:

$H^{⊗n}[2 |0> <0| − I] H^{⊗n} = 2 H^{⊗n}|0> <0| H^{⊗n} − I = 2 |\psi> <\psi| − I$

And the entire Grover iteration:

$[2 |\psi><\psi| − I] \omega $

In considering the runtime of the Grover iteration, the exact runtime of the oracle depends on the specific problem and implementation, so a call to $\omega$ is viewed as one elementary operation. The total runtime, then, of a single Grover iteration is $O (2^n)$, from the two Hadamard transforms, plus the cost of applying $O(n)$ gates to perform the conditional phase shift, is $O(n)$. It follows that the runtime of Grover’s entire algorithm, performing $O(\sqrt N) = O(\sqrt {2^n}) = O(2^{n \over 2})$ iterations each with a runtime of $O(n)$, is $O(2^{n \over 2})$.

Once the Grover iteration has been performed an adequate number of times, a classical measurement is performed to determine the result, which will be correct with probability $O(1)$ completing the execution of the algorithm.

Grover’s algorithm is summarized as follows:

Input:

• A quantum oracle $\omega$ which performs the operation $\omega|x>= (−1)^{f(x)}|x>$, where f(x) = 0 for all 0 ≤ x < 2n except $x_0$, for which $f(x_0)$ = 1.
• n qubits initialized to the state |0>

Output: $x_0$

Runtime: $O(\sqrt 2^n)$ operations, with O(1) probability of success.

Procedure:

1. $|0>^{⊗n} \rightarrow$ initial state
2. $H^{⊗n}|0>^{⊗n} = {1 \over {\sqrt 2^n}} \sum_{x=0}^{2^n - 1} |x> = |\psi> \rightarrow $apply the Hadamard transform to all qubits
3. $[(2 |\psi><\psi| − I)O]^R |\psi> \approx |x0> \rightarrow$ apply the Grover iteration $R ≈ {\pi \over 4 \sqrt {2^n}}$ times
4. $x_0 \rightarrow$ measure the register

Grover’s algorithm: Worked example

Consider a system consisting of N = 8 = $2^3$ states, and the state we are searching for, $x_0$, is represented by the bit string 011. To describe this system, n = 3 qubits are required, represented as:

$|x> = \alpha_0 |000> + \alpha_1 |001> + \alpha_2 |010> + \alpha_3 |011> + \alpha_4 |100> + \alpha_5 |101> + \alpha_6 |110> + \alpha_7 |111>$

where $\alpha_i$ is the amplitude of the state |i>. Grover’s algorithm begins with a system initialized to 0:

1 |000>

and then apply the Hadamard transformation to obtain equal amplitudes associated with each state of $ {1 \over {\sqrt N}} = {1 \over \sqrt 8} = {1 \over {2 \sqrt 2}}$, and thus also equal probability of being in any of the 8 possible states:

${H^3|000>} = {1 \over 2 \sqrt 2} |000> + {1 \over 2 \sqrt 2} |001> + . . . + {1 \over 2 \sqrt 2} |111> = {1 \over 2 \sqrt 2} \sum_{x=0}^7 |x> = |\psi>$

The first step is to call the quantum oracle $\omega$, then perform inversion about the average, or the diffusion transform. The oracle query will negate the amplitude of the state $|x_0>$, in this case |011>, giving the configuration:

$|x> = \alpha_0 |000> + \alpha_1 |001> + \alpha_2 |010> - \alpha_3 |011> + \alpha_4 |100> + \alpha_5 |101> + \alpha_6 |110> + \alpha_7 |111>$

Now, perform the diffusion transform $2 |\psi> <\psi| − I$, which will increase the amplitudes by their difference from the average, decreasing if the difference is negative:

${[2 |\psi><\psi| − I] |x>}= {[2 |\psi> <\psi| − I] [|\psi>} − {2 \over {2 \sqrt 2}}|011> = 2 |\psi><\psi|\psi> − |\psi> − {2 \over \sqrt 2} |\psi> <\psi|011> + {1 \over \sqrt 2} |011>$ Note that $<\psi|\psi> = 8 {1 \over 2 \sqrt 2}{1 \over 2 \sqrt 2}$ Additionally, since |011> is one of the basis vectors, we can use the identity $<\psi|011> = <011|\psi> = {1 \over {2 \sqrt 2}}$ :

$= {2 |\psi> − |\psi>} − {2 \over {\sqrt 2}}({1 \over {2 \sqrt 2}}) |\psi> + {1 \over \sqrt 2} |011> = |\psi> − {1 \over 2} |\psi> + {1 \over {\sqrt 2} }|011> = {1 \over 2} |\psi> + {1 \over {\sqrt 2}} |011>$

Substituting gives:

$= {1 \over 2} [{1 \over {2 \sqrt 2}}\sum_{x=0}^7 |x>] + {1 \over {\sqrt 2} }|011> ={1 \over {4 \sqrt 2}} \sum_{x=0, x \neq 3}^7|x> + {1 \over {4 \sqrt 2} }|011> + {1 \over {\sqrt 2}} |011> = {1 \over {4 \sqrt 2} }\sum_{x=0, x \neq 3}^7|x> + {5 \over {4 \sqrt 2} }|011>$

In the notation used earlier: ${|x>} = {1 \over {4 \sqrt 2}} |000> + {1 \over {4 \sqrt 2}} |001> + {1 \over {4 \sqrt 2}} |010> + {5 \over {4 \sqrt 2}} |011> + . . . + {1 \over {4 \sqrt 2}} |111>$

Now when the system is observed, the probability that the state representative of the correct solution, |011>, will be measured is $|{5 \over {4 \sqrt 2}}|^2$.

Although Grover’s algorithm is probabilistic, the error truly becomes negligible as N grows large.