Nielsens complexity describes the distance of a unitary operator to the identity operator in the manifold of unitaries. It is know to be a lower bounds to the gate complexity, as shown here. How does one read the constants $c_p, T_p$ for concrete examples? They are constants but what is the typical value in order to convert between Nielsens complexity and gate complexity.
1 Answer
$\begingroup$ $\endgroup$
3 They are normalization‑dependent constants that you choose once you fix (i) the cost function/metric and (ii) the “preferred” (typically 1‑ and 2‑local) Hamiltonians you allow. In the standard choices used by Nielsen and coauthors, you can (and they do) normalize things so that
$$ c_P=1,\qquad T_P=\Theta(1)\ \text{(a constant independent of }n\text{)}. $$
With that normalization the geometric (Nielsen) complexity $C(U)$ lower‑bounds gate complexity up to a constant factor:
$$ C(U)\ \le\ c_PT_P\,G(U)=\Theta(G(U)). $$
What $c_P$ and $T_P$ are
Nielsen’s “optimal‑control” formulation (Theorem 1 in Optimal control) defines these two splitting‑dependent constants as follows:
- $c_P \equiv \displaystyle\max_{H\in H_P} c(H)$ is the maximal instantaneous cost of any preferred Hamiltonian.
- $T_P$ is the maximal time required to generate any one‑ or two‑qubit gate using time‑dependent preferred Hamiltonians (i.e., staying within $H_P$).
With these definitions,
$$ C(U)\ \le\ c_P\,T_P\,G(U)\quad\text{(exact synthesis, no ancillas).} $$
- $\begingroup$ The normalisation of $c_p=1$ does not make sense to me, it does not seem to apply to standard gates, like for U = CNOT, H has prefactors $\pi/4$ in the Pauli expansion. $\endgroup$user1577744– user15777442025-08-30 10:31:07 +00:00Commented Aug 30 at 10:31
- $\begingroup$ Maybe the word normalization is somewhat problematic, but in the examples given in the paper it is shown that Cp = 1: this is stated on page 4: it follows immediately from the definitions that Cp = 1 and TP is a constant. Cp is the maximum instantaneous cost of any preferred Hamiltonian under the chosen normalization of the cost of c(H). In the standard setup, one defines the allowed controls so that 𝑐(𝐻)≤1. The familiar 𝜋/4 you see in gates like CNOT is not a value of 𝑐(𝐻) it’s the time‑of‑flight you need along a preferred direction at unit speed. In other words, the 𝜋/4 goes into TP. $\endgroup$Bram– Bram2025-08-30 11:39:49 +00:00Commented Aug 30 at 11:39
- $\begingroup$ I really would need to see both constants worked out explicitly for an example unitary $\endgroup$user1577744– user15777442025-08-30 11:43:22 +00:00Commented Aug 30 at 11:43