Circuit vs Query Complexity

Last updated Feb 2, 2022

• Type note
• Status good
• On quantum computing

Source:: 2022 Introduction to Classical and Quantum Computing

• The most precise way to quantify the complexity of a quantum circuit is to count the least number of Quantum Gates required to implement it, relative to some universal set of quantum gates. This is called its circuit complexity. It is generally hard to find.
• In terms of circuit complexity, an efficient quantum algorithm is one with a polynomial circuit complexity.

• The query complexity of a problem is the number of calls to a function, or queries to an oracle or black box needed to solve the problem. It is significantly easier to find the query complexity of a problem.
• Oracle separation is the improvement or speedup, of a quantum algorithm over classical one, in terms of the number of oracle queries.

• An Oracle is simply a boolean function, meaning a function that acts on bits.
  • It can be defined using a truth table, and it can be constructed using logic gates.
• A quantum oracle needs to be reversible.
  • As we know, we can turn an irreversible circuit into a reversible circuit by XORing its output with an extra bit.
  • So, the quantum oracle $U_f$ acts as $$\ket{x}\ket{y} \overset{U_f}{\longrightarrow} \ket{x}\ket{y \otimes f(x)},$$ where $f(x)$ is the original irreversible function, $\ket{x}$ is the input qubit and $\ket{y}$ is the extra qubit, called an answer qubit or target qubit.

• There is another way to query the quantum oracle that causes the answer qubit $|y⟩$ to remain unchanged while multiplying $|x⟩$ by a phase, unlike previously. This is called a * Phase Oracle* and it is defined as $$\ket{x} \overset{U_f}{\longrightarrow} (-1)^{f(x)}\ket{x}.$$
  Here, the input qubit $\ket{x}$ is multiplied by a phase $(-1)^{f(x)}$ and we drop the answer qubit $\ket{y}$ since it doesn’t change.
  • Detailed derivation can be seen in the book.

• We have two unknown bits $b_0$ and $b_1$, and we want to find the parity of the two bits, i.e. $b_0 \otimes b_1$.
• We are given an oracle $f(x) = b_x$ that takes as input an index $x ∈ {0, 1}$ and returns the corresponding bit, i.e. $$f(0) = b_0, \qquad f(1) = b_1.$$ ^ee56bf

• Classically we need to query the oracle twice as we need to know both bits in order to find $b_0 \otimes b_1$. Hence, the classical query complexity is $2$.

• Quantumly, it only takes $1$ query to find the parity using Deutsch’s Algorithm.

• We can use Deutsch’s Algorithm to find the parity of pairs of bits. Then we can take XOR of all these parities to get the parity of all the bits. This takes $n/2$ queries.

• We have a function $f(x)$ that takes as input a binary number $x = x_{n−1} \dots x_1x_0$ of length $n$ and outputs $0$ or $1$.
• We additionally have the promise that $f$ is constant (always outputs $0$ or always outputs $1$) or balanced (outputs $0$ half the time, and outputs $1$ half the time).
• Our task is to determine if $f$ is constant or balanced. Put another way, $f$ outputs $1$ none of the time, all of the time, or half of the time, and the task is to determine if it is none or all of the time (constant) or half of the time (balanced).

• For a classical computer to determine with certainty whether $f$ is constant or balanced, it needs $2{n−1} + 1$ queries to $f$ in the worst case, which is $O(2^n)$.
• For a probabilistic classical computer to guess the answer with bounded error, it only needs a constant number ($c$) of queries to $f$ , which is $O(1)$.

• A quantum computer using the Deutsch-Jozsa algorithm can determine with certainty whether $f$ is constant or balanced using just $1$ query to $f$.
• This is an exponential speedup over the exact classical algorithm, but no speedup over the bounded-error probabilistic classical algorithm.

• We have a function $f(x)$ that takes as input a binary string of length $n$ and outputs $0$ or $1$.
• Now the promise is that $f(x) = s · x$, where $s$ is some $n$-bit string $s_{n−1}\dots s_1s_0$, and the dot product of $s$ and $x$ is the sum of the products of their elements.
• The problem is to find $s$.

• Since we need to determine all $n$ bits of $s$, the classical solution requires $n$ queries. For example, if $n=4$, then $$\begin{aligned}
  f(0001) &= s_3(0) + s_2(0) + s_1(0) + s_0(1) = s_0, \newline
  f(000) &= s_3(0) + s_2(0) + s_1(1) + s_0(0) = s_1, \newline
  f(0100) &= s_3(0) + s_2(1) + s_1(0) + s_0(0) = s_2, \newline
  f(1000) &= s_3(1) + s_2(0) + s_1(0) + s_0(0) = s_3.
  \end{aligned}$$

• Quantumly, we only need one query using the Bernstein-Vazirani algorithm, which is a polynomial speedup over classical computers.

• The problem of finding a hidden dot product string can be made recursive, meaning we embed the problem in a bigger instance of the problem, which is embedded in a bigger instance of the problem, and so forth.
• If we have $k$ levels, then a classical computer takes $Ω(n^k)$ queries to solve the problem, however, a quantum computer can solve this problem with $2^k$ queries.

• We have a function $f(x)$ that takes as input an $n$-bit string and outputs an $n$-bit string.
• We are promised that $f(x) = f(y)$ if and only if $$x_i = y_i \otimes s_i, \quad \text{and} \quad y_i = x_i \otimes s_i.$$
• The goal is to find the secret $n$-bit string $s$, called a mask, and since it is used to XOR the inputs, it is called an XOR mask.

• Classically, we can find the secret XOR mask $s$ by finding a collision, meaning a pair $x$ and $y$ such that $f$ maps them to the same string, i.e., $f(x) = f(y)$.
• One approach is to trying the inputs one-by-one until we find a collision. The query complexity with this approach is $O(2n−1 + 1)$.
• We can also query $f$ with random inputs, which would result in a query complexity of $O(2^{n/2})$.

• Simon’s algorithm follows the same pattern that we have seen so far in Deutsch’s Algorithm, Deutsch-Jozsa algorithm, and Bernstein-Vazirani algorithm: apply Hadamards, query the oracle, and apply Hadamards again.
  • But now we have $n$ input qubits and $n$ answer qubits, and we start each of the answer qubits in the $|0⟩$ state as opposed to the $\ket{-}$ state.
  • Another difference with Simon’s algorithm is that we will measure all the qubits, not just the input qubits.
• Using the Simon’s algorithm, we can find $s$ with $O(n)$ queries to the oracle.
• #to/process #to/understand

• We have examined several quantum algorithms that all follow the same procedure: apply Hadamards, query the oracle, and apply Hadamards again.
• The following table summarizes the problems, query complexities, and asymptotic quantum speedups
  

• In brute-force searching problem, we have a function $f$ that takes as input a binary string of length $n$ and outputs $0$ or $1$. However, it only outputs $1$ for a single special input $w$.
• This problem is also phrased as searching an unordered database, unstructured searching and inverting a function. Brute-force searching includes trying to solve problems in Class NP by checking each input to see which output is correct.

• Classically, we must query all $N = 2^n$ possible bit strings in the worst case, so the classical runtime is $O(N)$.

• A quantum computer can solve the brute-force searching problem using only $O(\sqrt N)$ queries using Grover’s algorithm, which is a quadratic speedup over the classical computer’s $O(N)$.

• If we want $|s⟩$ to be unchanged, but states perpendicular to $|s⟩$ to be reflected (i.e., take on a minus sign), we can write reflection about $\ket{s}$ $R_s$ as $$R_s = 2\ket{s}\bra{s} - I.$$

• It is proven that a quantum computer cannot solve the brute-force problem faster than $O(\sqrt N)$, so Grover’s algorithm is optimal.
• If it takes a classical computer an exponential number of queries to solve a problem in Class NP, a quantum computer also takes an exponential number of queries (albeit a smaller exponential).
• Thus, quantum computers cannot brute-force solve NP problems by simply checking all the answers in superposition. Quantum computers cannot solve NP problems efficiently.

• Discrete Fourier Transform can be used to analyze music, among many other things.

• Fast Fourier Transform (FFT) is a classical algorithm that is used to calculate Discrete Fourier Transform. It only takes $O(N\log N)$ steps.

• The Quantum Fourier Transform (QFT) is a large Quantum Gate acting on $n$ qubits, whose general state has $N = 2^n$ amplitudes.

• The Inverse Quantum Fourier Transform (IQFT) undoes the QFT. As a quantum circuit, the IQFT can be performed by reversing the order of the gates the QFT and replacing them with their inverses.

• Given a Unitary matrix $U$ and one of its eigenvectors $|v⟩$, find or estimate its Eigenvalue.
• This problem is also called phase estimation, since finding the eigenvalue is equivalent to finding the phase $θ$ , as we know from Linear Algebra, that the eigenvalues of a unitary matrix must have the form $e^{iθ}$ for some real number $θ$.
• When the eigenvector is the state of a quantum system, it is often called an eigenstate. So, $|+⟩$ and $|−⟩$ are eigenstates of the X Gate.

• As we know that multiplying $|v⟩$ by $U$ will result in $|v⟩$ multiplied by $e^{iθ}$, i.e., $$U\ket{v} = e^{i\theta}\ket{v}.$$
• We can find the eigenvalue by solving this equation, i.e. multiplying matrix $U$ with the vector, and then using any row of that to find the value of $e^{i\theta}$. For example, using the first row, the eigenvalue would be $$e^{i\theta} = \frac{U_{11}v_1 + U_{12}v_2 + \dots + U_{1N}v_N}{v_1}.$$
• This takes $N$ multiplications, $N − 1$ additions, and one division, for a total of $2N = O(N)$ elementary arithmetic operations.

• To estimate the eigenvalue to $m$ bits of precision, we need $m$ Hadamard Gates, $m$ controlled-$U^p$ operations, and an IQFT on $m$ qubits that takes $O(m^2)$ gates. Altogether, the number of gates is $O(m^2)$.
• For detailed explanation/derivation, consult the book.

• #to/process

• Modular exponentiation is taking powers of a number modulo some other number. The period or order $r$ of the modular exponential is the length of the repeating sequence.
• The problem is to find the period of modular exponentials.

• Finding a single modular exponent is fast using the repeated squaring method.
• There is no known efficient algorithm for period finding.

• The circuit complexity of the quantum period algorithm is $O(n3)$, which is a polynomial in $n$, so it is efficient.
• For detailed explanation/derivation, consult the book. #to/process

• We are given a number $N$ that is the product of two prime numbers $p$ and $q$.
• The goal is to factor $N$, i.e., to find its factors $p$ and $q$.

• The best known classical algorithm for factoring is the number field sieve. To factor an $n$-bit number, its runtime is roughly $e^{n^{1/3}}$ , which is subexponential.

• An efficient quantum algorithm for factoring was invented by Peter Shor in $1994$.
• To factor $N = pq$, Shor’s algorithm consists of the following three steps:
  1. Pick any number $1 < a < N$, and calculate the $gcd(a, N)$. If the gcd is:
     • $1$ then move to the next step.
     • not $1$ then we have found one of the factors, $p$, and the other can be calculated using $q = N/p$.
  2. Find the period $r$ of $a^x$ mod $N$. Go back to step 1, if
     • period $r$ is odd.
     • $a^{r/2}$ $\text{mod}$ $N = N - 1$
  3. We can calculate factors using $$\begin{aligned}
     p &= \text{gcd}(a^{r/2} - 1, N), \newline
     q &= \text{gcd}(a^{r/2} + 1, N).
     \end{aligned}$$
• The bottleneck for Shor’s algorithm is Step 2, finding the period of the modular exponential. It is efficient on a quantum computer, but there is no known polynomial-time algorithm for a classical computer.

• It is easier to find the query complexity of the algorithms.
• Quantum computers can provide provable exponential speedups in query complexity.
• Quantum computers also provide a quadratic speedup for the general problem of brute-force searching.
• Quantum computers are known to provide speedups in circuit complexity for several problems.