Circuit Complexity
Discuss the concept of circuit complexity, the number of elementary operations used to compile a circuit.
Table of Contents
1. Quantum Circuit Complexity
- Quantum Circuit Complexity
- is the (minimum) number of elementary operations required to compile a quantum circuit. Say, if expressing a quantum circuit \(C\) requires \(N\) elementary circuit, i.e., \(C=e_{1}e_{2}\dots e_{N}\), then the circuit complexity is \(N\).
From the definition, we can see that quantum circuit complexity simply models the length of the sequence consisting of elementary circuits.
2. Query Complexity
Sometimes, we use query complexity to further abstract quantum circuit complexity and form a pure mathematical model.
To do this, we abstract like this: suppose we want to know the properties of an unknown function \(f\), and we an oracle that produces an \(f(x)\) for each query \(x\). Then, the whole process of solving the properties can be decomposed into how many queries we have made and the complexity of one single query. The term query complexity tells how many queries we need to learn the properties of that function; the counter part is modeled as complexity belonging to the oracle. Therefore, roughly speaking,
\[ \text{Circuit Complexity} = \text{Query Complexity} \times \text{Oracle Complexity} \]
Here, we only care about query complexity, since oracle complexity is more related to hardware implementation.
2.1. Oracle Model and Ancilla Qubits
We want to accelerate using quantum computing. However, quantum computing requires gates to be unitary (therefore reversible). To make any classic function \(f:\{0,1,\dots,M-1\}\mapsto\{0,1,\dots,N-1\}\) reversible, we introduce ancilla qubit \(\ket{q}\) to model the oracle1 \(O_{f}\)
\[ O_{f}: \ket{x}\ket{q} \mapsto \ket{x}\ket{q \oplus f(x)} \]
where \(q \oplus f(x) := q + f(x) \mod N\) denotes modulo-add. Note the tensor products, this ensures the one-to-one property, and thus reversible.
3. Deutsch-Jozsa Algorithm
The Deutsch Game
Suppose a function \(f:\{0,1,\dots,2^{n}-1\}\mapsto\{0,1\}\) is either balanced or constant. Constant means \(f(x)=a\) for all \(x\) and for a fixed \(a=0,1\); while balanced means, for half of the inputs \(f\) yields \(0\) and for the rest, \(f\) yields \(1\).
The player is given an unknown \(f\) which is guaranteed to be either constant or balanced. The task is to determine whether \(f\) is balanced or constant with as few queries as possible.
In classic settings, the above problems requires \(2^{n-1}+1\) queries in worst case. However, using quantum computing, we can answer this in just 1 query.
3.1. The Phase Kick-Back Trick
First, let’s introduce the phase kick-base trick. We initialize the ancilla qubit \(\ket{q}\) to \(\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})\). And by expanding, we know that
\[\begin{aligned} O_{f}\ket{x}\ket{-} &= \frac{1}{\sqrt{2}} \left( O_{f}\ket{x}\ket{0} - O_{f}\ket{x}\ket{1} \right) \\ &= \frac{1}{\sqrt{2}} (\ket{x}\ket{0} - \ket{x}\ket{1\oplus f(x)}) \end{aligned}\]
Then, we evaluate \(f(x)=1\) and \(f(x)=0\):
- If \(f(x)=0\), then it evaluates to \(\ket{x}\ket{-}\)
- If \(f(x)=1\), then it evaluates to \(-\ket{x}\ket{-}\)
Which can be unified
\[ O_{f}\ket{x}\ket{-} = (-1)^{f(x)}\ket{x}\ket{-} \]
Therefore, the observable is independent from the ancilla qubit \(\ket{q}\): we don’t need to measure the ancilla qubit; we only need to measure the main \(\ket{x}\), since the information of \(f(x)\) is now reflected on the outcome.
3.2. The Algorithm
- We first initialize all \(n\) qubits to \(\ket{0}^{\otimes n}\)2.
- Apply \(H\) Hadamard transform to all qubits. This step creates a superposition state3 that contains all \(2^{n}\) possible inputs.
- Apply \(O_{f}\) on all qubits.
- Apply \(H\) again on all qubits.
- Measure in the computational basis.
Then, output constant if the amplitude of \(\ket{00\dots 0}\) is \(1\), otherwise balanced (and in this case, the amplitude must be \(0\)).
How it works?