Black Hole Entropy


In this text, I review aspects of Black Holes Entropy and Thermodynamics. First, I review the general definition of a black hole and why it is necessary for a black hole to have an entropy. In the next, I review papers that naturally justify the famous formula S=\frac{k_B A}{4 l_p^2} where l_p=\sqrt{\hbar G/c^3} is the Planck’s length, for the entropy of a black hole. Parallely, I discuss the black hole laws and I review the arguments that show the relation between the second law of black holes (Hawking Area Theorem) without quantum mechanics is not straightforward. Next, I review the paper that derives the Einstein’s equations from Bekenstein entropy formula. Finally, I finish with reviewing an argument and a thought-experiment that challenge Bekenstein’s entropy formula for black hole. I will work in the units G=\hbar=c=k_B=1 unless we specifically state the otherwise and our metric convention is g=\text{diag}(-1,1,1,1).

Entropy of Black Holes, KN


Hydrodynamic Excitations from Chiral Kinetic Theory and the Hydrodynamic Frames

Here is our paper by N. Abbasi, K. Naderi, F. Taghinavaz. Any comment is welcome.


The abstract is as following:

In the framework of chiral kinetic theory (CKT), we consider a system of right- and left-handed Weyl fermions out of thermal equilibrium in a homogeneous weak magnetic field. We show that the Lorentz invariance implies a modification in the definition of the momentum current in the phase space, compared to the case in which the system is in global equilibrium. Using this modified momentum current, we derive the linearized conservation equations from the kinetic equation up to second order in the derivative expansion. It turns out that the eigenmodes of these equations, namely the hydrodynamic modes, differ from those obtained from the hydrodynamic in the Landau-Lifshitz (LL) frame at the same order. We show that the modes of the former case may be transformed to the corresponding modes in the latter case by a global boost. The velocity of the boost is proportional to the magnetic field as well as the difference between the right- and left-handed charges susceptibility. We then compute the chiral transport coefficients in a system of non-Abelian chiral fermions in the no-drag frame and by making the above boost, obtain the well-known transport coeffiecients of the system in the LL frame. Finally by using the idea of boost, we reproduce the AdS/CFT result for the chiral drag force exerted on a quark at rest in the rest frame of the fluid, without performing any holographic computations.

Tensor Network, MERA, and holography

Here I want to review some notions of Tensor Network (TN) and a special class of TN called multi-scale entanglement renormalization ansatz (MERA) in order to come up with an outstanding result – computing the geometry of CFT_{2}‘s dual that is AdS_{3}.

Tensor Network (TN) [Ref. 1]

Consider an arbitrary separable Hilbert space H and its dual H^{*}. Assume T:H^{\otimes^n}\bigotimes H^{* \otimes^m}\rightarrow \mathbb{C} is multi-linear. With respect to a complete basis for H and H^{*}, i.e. \{ e_{i} \} and \{ \lambda^{i} \}, we can represent T as: (omitting the tensor product symbol)

T=\sum T^{i_1 \cdot \cdot \cdot i_n}_{j_1 \cdot \cdot \cdot j_m} e_{i_1} \cdot \cdot \cdot e_{i_n} \bigotimes \lambda^{j_1}\cdot \cdot \cdot \lambda^{j_m}

Thus, we can assign T^{i_1 \cdot \cdot \cdot i_n}_{j_1 \cdot \cdot \cdot j_m} to T with respect to the basis. Graphically, we can show a tensor with a box, a triangle or an arbitrary symbol, and to show each of its upper (lower) free indices with a free arm on from the symbol going to the upper (lower) half-plane. For example, look at the below figure which (a) shows \psi=\sum \psi^i e_i.


Some rules:

  • If two or more tensors are represented on a diagram, we call it a Tensor Network.
  • Each tensor in a TN can be connected through their free arm(s) to other tensors. By doing this, we are just tracing over \lambda^i e_i for some i.
  • Each disconnected components of a TN would be tensor multiplied to each other.

Some examples:

  1. For a qubit system, the Levi-Civita tensor is \epsilon=\frac{1}{\sqrt{2}} (\left|01\right>-\left|10\right>).
  2. A quantum circuit can be though of as sub-class of TN. Consider the state \psi and assign a quantum circuit to it using a finite family of quantum gates, i.e. QG_P (see this). It can be seen as a TN since on each gate, a local unitary operator would act and this act can be represented as a tensor contraction in a TN. At the end of the day, you have several tensors with free indices and some contraction on gates. So by this observation, we can assign a complexity to a TN: the complexity of a TN is the number of tensors (gates, inputs, and outputs) in the TN. In this sense, the complexity of the state \psi is the minimum of complexity of TNs that would implement the \psi.

Tensor Renormalization Group (TRG) [Ref. 2]

Consider a lattice \mathcal{L} that has several sites each labeled by s\in\mathcal{L}. We want to compute the partition function of this system. Assume the classical Hamiltonian H is local in the sense that consists of interactions between neighborhoods. If it is the case, write H=\sum_{s\in \mathcal{L}} H_s where s labels different “sites” in the lattice \mathcal{L} and we would like to assume each H_s has the dimension \chi in the sense that it has s possibilities. Our goal is to compute Z=\sum e^{-\beta H} over all possibilities. Let me write U_s=e^{-\beta H_s}. Thus, Z=\sum_{d.o.f} \Pi_{s\in\mathbb{L}} U_s. Since we may write \sum_{\bar{d.o.f}} \Pi_{s\in\mathbb{L}} \sum_{d.o.f for s} U_s and \sum_{d.o.f for s} U_s can only depend on boundary variables since all inner degrees of freedom are traced out, we can associate to site an operator T_s which there are some traces behind these T_s‘s that would end in an expression for the partition function. Now assume \chi=p. In the Ref. 2 it is discussed the T_s can be viewed as an operator from a \chi dimensional vector space to itself with an error like exp(-(const.) (log \chi)^2). Thus, we may associate to T_s a tensor T_s^{i_1\cdot\cdot\cdot i_p} where each i_{n} varies from 1 to \chi. In fact, we have just selected the first \chi eigenstates of the density matrix in the site s. To summarize, the partition function is nothing but a fully contracted TN.

So assume we have a fully contracted TN in a specific lattice, honeycomb lattice. By the symmetry the tensor T_s on each site is a symmetric tensor. It is argued in Ref. 2 that we can find a tensor S using the singular value decomposition of the tensor M_{(ab),(cd)}=T_{abe} T_{cde} in order to:

S_{ace} S_{bde}=T_{abe} T_{cde}

It is equivalent to change the geometry of the TN by this transformation:


After doing this, we can rearrange the TN to coarse-grain the TN in to another TN with smaller number of tensors, however, with higher ranges of indices. In fact, this the part that we need to be careful about assigning a tensor to the operator T_s where the range of all of its indices are constant. Indeed, this method works properly for gapped Hamiltonians. Iterating this procedure leads us with a renormalization group that changes all local operators and tensors and it is possible to compute the partition function. More details are in Ref. 2.


Tensor Network Renormalization (TNR) [Ref. 3]

We want to introduce a coarse-graining transformation on a lattice \mathcal{L}. Consider we have came up with a fully contracted TN and each tensor is on a complex \chi dimensional Hilbert space namely V. What we want to do is computing E=\sum T_{a_1\cdot\cdot\cdot a_p} T_{b_1\cdot\cdot\cdot b_p} \cdot \cdot \cdot. Consider a simple 2D square lattice with the Ising model Hamiltonian. In this case T_{abcd}=e^{\beta{\sigma_a \sigma _b+\sigma_a \sigma _c+\sigma_b \sigma _d+\sigma_c \sigma _d}}. Look at the below figure:


We introduce an operator called a disentangler, i.e. u: V \bigotimes V \rightarrow V \bigotimes V such that u u^{\dagger}=I\bigotimes I. This would not changed the expression E.

Next we introduce an isometry operator like v:V \bigotimes V \rightarrow V such that v^{\dagger} v = I. However, v v^{\dagger} is a projection. So our coarse-graining transformation is not exact. This transformation is show in the below figure.


In fact, the disentangler operator removes short-range correlations. Several advantages of this method over TRG is discussed in Ref. 3.

MERA [Ref. 4]

Consider a D dimensional lattice \mathcal{L} that has N sites. Let H a \chi dimensional Hilbert space assigned to each site. Assume the Hilbert space of \mathcal{L} is H^{\bigotimes^N}. Let \psi \in H^{\bigotimes^N} an arbitrary state and \Omega=\left|0\right>^{\bigotimes^N} the ground state. Consider a quantum circuit associated to the state \psi with local unitary operators in a finite family of quantum gates. Using the second example in the section Tensor Network (TN), we can see this quantum circuit as a TN with additional characteristics. Let \theta specify the steps in this quantum circuit. Using the idea of TNR (previous section) this TN can be viewed as a coarse-graining transformation of the lattice \mathcal{L}. So, \theta can be both viewed as time and scale indicator. Here is a cartoon for D=1.


As it is apparent from the TNR method, at each step there are two types of transformations: disentaglers and isometry operations. The former removes the short-range correlations and the latter combines pairs of nearest neighborhood wires into a single wire. Let the total step in the quantum circuit to be \Theta and introduce \tau=\frac{\Theta-\theta}{2}. Hence, at each \tau step, two operations is done. Both are depicted in the figure. Now let define a MERA. A MERA is a representation of a state \psi \in H^{\bigotimes^N} using the quantum circuit associated to this state from the ground state \Omega. One of the important feature of a MERA is that it has a causal cone with a bound width. Another important characteristic of a MERA is that by the stated feature, local operators remain local.

Just as a reminder, we define the complexity of a MERA as number of tensors in the MERA in compatible with our definition of a complexity of a state with the minimum number of nodes in its quantum circuits.

AdS/CFT correspondence [Ref. 5 and Ref. 6]

Why the spacetime associated to CFT is AdS?

In above, the complexity of a MERA defined. However, the complexity of a state is the complexity of an optimal MERA that implements the state. Thus, in order to minimize this complexity, we have to find an optimal MERA for the state. However, one should ask whether the optimal TN is a MERA; it is an ansatz. In Ref. 5 it is conjectured that changing the geometry and external gauge fields would express this optimization. Namely, to each state \psi assign a functional I_{\psi} where optimizing that would yield the optimized MERA for the state \psi.

The idea is to discretize Euclidean path integrals and changing them into a TN. Consider we have a state \psi and we start with a flat geometry where point are indicated by (z,x) such that z=i t and \epsilon is the lattice cut-off:

ds^2=\frac{1}{\epsilon^2}(dz^2+\sum_{i=1}^{d-1} dx^i dx^i)

After “optimizing” the path integral (which will be discussed.) we will come up with a state \psi_O. The basic idea is that we want \psi_O = c \psi where c is a constant. We assign to each state \psi a functional that minimizing its value results in the optimization. We called this functional I_{\psi}. In CFT_2 there is no coupling that runs with the RG flow so a candidate for such a optimization is the background metric. Thus, we get I_{\psi}[g_{ab}] where g_{ab} is the background metric.

Now we focus on CFT_2. We know every metric in 2D is conformally (diffeomorphism+Weyl) flat, i.e. there exist a \phi such that g_{ab}=e^{2\phi} \delta_{ab}. So the only function that would possibly indicate such a optimization is \phi. It is known changing the background metric with a Weyl transformation would lead to change the measure of the path integral by:



S_L[\phi]=\frac{c}{24\pi}\int_{-\infty}^{\infty} dx \int_{-\epsilon}^{\infty} dz [(\partial_x \phi)^2+(\partial_z \phi)^2+\mu e^{2\phi}+R\phi]

It is called the Liouville action. R is the Ricci scalar of the original space and in our case zero. It is conjectured in Ref. 5 I_{\psi}[\phi]=S_L[\phi]. But the surprising fact is that we can convince ourselves the relation is true by the supporting arguments using developed TN machinery.

We have seen the number of tensor in a MERA associated to the state \psi is a quantity of complexity of that MERA. There are two types of tensors in the MERA: first the original tensors in the MERA, second the isometry tensors that combine two wires into a single wire. Let’s compute the number of tensor in a MERA. The local density of number of initial tensors is e^{2\phi} that is apparent from the below figure.


The second components are isometric tensors. These tensors are in the non-continuous part of the diagram, i.e. green ones in the above figure. So they are related to the jump of \phi. The lowest order rotationally symmetric term that is even in \nabla \phi (because thinking in reverse time should not change the number of isometric layers.) is: (I have to say I don’t understand this point!)

\int dx dz \sqrt{g} g^{ab} \partial_a \phi \partial_b \phi

That is equal to:

\int dx dz (\partial_x \phi)^2+(\partial_z \phi)^2

So now we have to sum a positive multiplication of these two integral and we conclude \mathcal{C}[\phi]=a S_L[\phi] where a is a constant. So indeed we are trying to minimizing the complexity of the state \psi using its MERA correspondences. Up to now, we have conjectured in order to minimize the complexity of the state, we have conjectured we have to minimize the Liouville action. Doing this leads us to the following equation:

4 \partial_{w} \partial_{\bar{w}} \phi=e^{2\phi}

where w=x-iz. We have the boundary condition e^{2\phi(z=\epsilon,x)}=\epsilon^{-2}. One solution is e^{2 \phi}=\frac{4}{(w+\bar{w})^2}=z^{-2}. Thus, the optimized geometry is:


that is a hyperbolic space on \mathbb{H}^2. Moreover, if we compact the x dimension, we can conclude indeed the optimized value for S_L is \frac{c L}{12 \pi \epsilon} where L is the L=\int dx. It is interesting to see the lattice cut-off is somehow a cut-off in quantum complexity.

It is an outstanding result! This paper concluded the geometry in the bulk associated to the vacuum is such that its time slices (we have to argue the additional dimension in the MERA is indeed time and it is discussed in Ref. 6.) have the hyperbolic metric in agreement with the geometry of time slices of AdS_3. For other states in the CFT_2 the same conclusion is discussed in Ref. 5.


  1. Quantum Tensor Networks in a Nutshell, Jacob Biamonte and Ville Bergholm.
  2. Tensor renormalization group approach to 2D classical lattice models, Michael Levin and Cody P. Nave.
  3. Tensor Network Renormalization, G. Evenbly and G. Vidal.
  4. A class of quantum many-body states that can be efficiently simulated, G. Vidal.
  5. Liouville Action as Path-Integral Complexity: From Continuous Tensor Networks to AdS/CFT, Pawel Caputa, Nilay Kundu, Masamichi Miyaji, Tadashi Takayanagi, and Kento Watanabe.
  6. Einstein’s Equations from Varying Complexity, Bartlomiej Czech.

de-Sitter and Anti de-Sitter spaces

Here I want to define the n-dimensional de-Sitter and anti de-Sitter spaces. Before that, I quickly review some subgroups of GL(n,\mathbb{F}) where \mathbb{F}=\mathbb{R},\mathbb{C}.

Groups of matrices

  • \mathbb{M}_n: the group of all n\times n matrices where entries are in the field F.
  • GL(n,\mathbb{F}): the subgroup of \mathbb{M}_n consisting of all injective (thus bijective) matrices.
  • SL(n,\mathbb{F}): the subgroup of \mathbb{M}_n consisting of all injective (thus bijective) matrices with the determinant 1.
  • O(n,\mathbb{F}): the subgroup of \mathbb{M}_n consisting of all matrices where A^{T}A=I.
  • SO(n,\mathbb{F}): O(n,\mathbb{F}) \cap SL(n,\mathbb{F}).
  • O(B): consider a bilinear degenerate form on an n-dimensional vector space V. O(B) is the group (under the composition) of all linear maps from V to itself such that B(Tv,Tw)=B(v,w) for all v,w \in V.

Proposition 1. Consider B a bilinear non-degenerate form on an n-dimensional vector space V. Then if \mathbb{F}=\mathbb{C}, then there are independent vectors like v_1, \cdot\cdot\cdot, v_n such that for each 1\leq i \leq n we have B(v_i,v_i)=1 and all the other B(v_i,v_j)=0. If \mathbb{F}=\mathbb{R}, then there is a p \in \mathbb{N} such that for i \leq p we have B(v_i,v_i)=1 but for i > p we have B(v_i,v_i)=1 and this p only depends on B. We call (p,n-p) the sign of B in the real case.

The idea of a proof: it is not very hard to see we can make B diagonal. The important part is that in the complex field, we can take the square root of all real numbers, however, in the real field we can take the square root of only positive numbers. To show p only depends on B we can look at the subspace of V where B is positive and prove its dimension is p.

  • O(p,q): the subgroup of \mathbb{M}_n consisting of all matrices where A^{T}\eta_{p,q}A=\eta_{p,q} such that \eta_{p,q}=\Big( \begin{smallmatrix} I_{p\times p} & 0 \\ 0 &  -I_{q\times q} \end{smallmatrix} \Big) where n=p+q.

Proposition 2. Consider B a bilinear symmetric non-degenerate form on an n-dimensional vector space V. Then \mu:O(B)\rightarrow O(p,n-p) is an isomorphism where \mu sends each linear transformation to its matrix representation with respect to an arbitrary basis.

  • SO(p,q): O(p,q) \cap SL(p+q,\mathbb{R}).
  • Sp(n,\mathbb{F}): let J=\Big( \begin{smallmatrix} 0 & I_{n\times n} \\ -I_{n\times n} & 0 \end{smallmatrix} \Big). This is the group of all matrices in \mathbb{M}_n where A^{T} J A=J.

Proposition 3. Consider B a bilinear non-degenerate form on an n-dimensional vector space V. Then there are independent vectors like v_1, \cdot\cdot\cdot, v_n such that the matrix representation of B with respect to this basis is [B(v_i,v_j)]=J.

Proposition 4. Consider B a bilinear skew-symmetric (B(v,w)=-B(w,v)) non-degenerate form on an n-dimensional vector space V. Then \mu:O(B)\rightarrow Sp(n,\mathbb{F}) is an isomorphism where \mu sends each linear transformation to its matrix representation with respects to an arbitrary basis.

dS_n and AdS_n

Consider B a symmetric bilinear non-degenerate form on \mathbb{R}^{n+1}. Since B is smooth from \mathbb{R}^{n+1} \times \mathbb{R}^{n+1} to \mathbb{R}, thus each level set of B (all points in \mathbb{R}^{n+1} \times \mathbb{R}^{n+1} such that B is constant on them.) is a properly embedded sub-manifold of \mathbb{R}^{n+1} \times \mathbb{R}^{n+1}. Since we have seen that every symmetric bilinear non-degenerate form can be in a certain sense diagonalized, so we can think of B a smooth function from \mathbb{R}^{n+1} to \mathbb{R}. Moreover, if we get X=(x_1,\cdot\cdot\cdot,x_{n+1})\in\mathbb{R}^{n+1}, then:


Thus, setting the level set constant to c=\pm R^2, we would get different spaces embedded in \mathbb{R}^{n+1}. We call this space \mathcal{M}_{p,c} since it only depends on the sign of B and c. Now we want to take a look on some of these spaces:

  • S^n: get p=n+1 and c=R^2. The symmetry group of S^n those are the group where does not change the quadratic form on \mathbb{R}^{n+1} with the sign (n+1,0). By the definition, this is the group SO(n+1,\mathbb{R}). Looking more closely, we have to get a metric for the space \mathbb{R}^{n+1}. If we get the metric to be equal to the matrix representation of this bilinear form (that is identity) then the group of Killing vectors of S^n would be exactly SO(n+1,\mathbb{R}).
  • \mathbb{H}^n: get p=n and c=-1. This space on the upper half-plane \mathbb{H}^n is called the hyperbolic space. The symmetry group of \mathbb{H}^n those are the group where does not change the quadratic form on \mathbb{R}^{n+1} with the sign (n,1), however, it is based on the fact that the metric is equal to the matrix representation of this bilinear form (that is the Lorentz matrix, \eta_{n,1}.). Thus, the group of Killing vectors of \mathbb{H}^n is exactly the group SO(n,1).
  • dS_n: get p=n and c=R^2. The symmetry group of dS_n those are the group where does not change the quadratic form on \mathbb{R}^{n+1} with the sign (n,1), however, it is based on the fact that the metric is equal to the matrix representation of this bilinear form (that is the Lorentz matrix, \eta_{n,1}.). Thus, the group of Killing vectors of dS_n is exactly the group SO(n,1).
  • AdS_n: get p=n-1 and c=-R^2. The symmetry group of AdS_n those are the group where does not change the quadratic form on \mathbb{R}^{n+1} with the sign (n-1,2), however, it is based on the fact that the metric is equal to the matrix representation of this bilinear form (that is the Lorentz matrix, \eta_{n-1,2}.). Thus, the group of Killing vectors of AdS_n is exactly the group SO(n-1,2).

Remark 1. It is worth to mention the size of |SO(p,q)|=\frac{k(k-1)}{2} where k=p+q. Thus, all the above spaces (S^n, dS_n, and AdS_n) are maximally symmetric in the sense that in \mathbb{R}^{n+1} has \frac{n(n+1)}{2} Killing vectors. Moreover, de-Sitter and anti de-Sitter spaces have constant negative curvature.

Remark 2. It is almost straightforward to see the pullback metric on dS_n and AdS_n are metrics with Lorentz signature. To see this, just eliminate the dx_{n+1} and compute the metric. (It is the recipe of computing the pullback.)

Topology of dS_n and AdS_n:

  • dS_n: the de-Sitter space is described by this equation:


with the metric dx_1^2+\cdot\cdot\cdot+dx_n^2-dx_{n+1}^2. So we can assign x_1^2+\cdot\cdot\cdot+x_n^2 to a S^{n-1} with the radius \rho. Thus, the topology of dS_n is S^{n-1}\times \mathbb{R}.

  • AdS_n: the anti de-Sitter space is described by this equation:


with the metric dx_1^2+\cdot\cdot\cdot+dx_{n-1}^2-dx_{n}^2-dx_{n+1}^2. So we can assign x_{n}^2+x_{n+1}^2 to a S^{1} with the radius \rho. Thus, the topology of AdS_n is \mathbb{R}^{n-1}\times S^{1}.

Remark. In n=2 both de-Sitter and anti de-Sitter have the same topology, S^{1}\times\mathbb{R}.



  1. ANTI-DE SITTER SPACE, Ingemar Bengtsson, Fall 1998

Classical and Quantum Circuit Complexity

Classical complexity:

Definition 1. Boolean circuits: for every n,m \in \mathbb{N} consider an acyclic graph (a graph that does not have any loop.) that has n inputs and m outputs. Input nodes only have output edges and output nodes only have input edges. All other nodes are called gates. Each gate does an operation on its input(s) that is AND, OR, or NOT and pass one or more output. The fanin of a gate is the number of incoming edges to the gate. For instance, the fanin of an AND node is 2. The size of a Boolean circuit is the number of nodes (gates, inputs, and outputs) in it. A Boolean circuit is called a Boolean formulae if every node has at most one output edge.

Claim. Every Boolean circuit is a function from \{ 0,1 \}^n \rightarrow \{ 0,1 \}^m. Although intuitively it is right but it is not trivial. See the reference for a proof.

Proposition. For every function such that f:\{ 0,1 \}^n \rightarrow \{ 0,1 \}^m there is a Boolean circuit (indeed a Boolean formulae) that implements the function f. This property is called the universality. We call the AND, OR, and NOT gates the G_p gate.

Sketch of proof. It is sufficient to prove the proposition for m=1 since if there was a Boolean circuit that implements the act of f on the i-th component of \{ 0,1 \}^m then by gluing these circuits together we could implement the function f. So assume m=1. For every u \in \{ 0,1 \}^n there is a clause, let’s say C_u:\{ 0,1 \}^n \rightarrow \{ 0,1 \}, such that C_u(v)=0 if and only if v = u. (Consider u=(0,1,...,1) and get C_u=\pi_1 \wedge \bar{\pi_2}\wedge\cdot\cdot\cdot \wedge \bar{\pi_n}.)

Now consider every u \in \{ 0,1 \}^n such that f(u)=0 and make the AND of all C_u‘s of them and make a Boolean circuit from this. Then if f(u)=0 then the Boolean circuit value is zero too. If f(u)=1, so all of C_v(u)=1 and so the Boolean circuit’s value is either 1. (Why there is a Boolean formulae for each such function?)

Definition 3. A local gate is a gate that its fanin is one or two.

Definition 4. Consider a set of gates, i.e. G. We say it is universal if the set G has the universality property.

Definition 5. A family \{ C_n\}_{n\in\mathbb{N}} of Boolean-circuits are called T-sized where T:\mathbb{N}\rightarrow\mathbb{N} if |C_n|\leq T(n) for each n\in\mathbb{N}.

Definition 6. Consider G is a set of local and universal gates. The G_n-complexity of a function f:\{ 0,1 \}^n \rightarrow \{ 0,1 \} is the minimum number of gates that is needed in order to implement the function f.

Theorem 1. Let \epsilon>0, f:\{ 0,1 \}^* \rightarrow \{ 0,1 \} arbitrary, and two sets of local and universal gates called G,G^\prime. Then there is an N\in\mathbb{N} and q\in \mathbb{Q} such that for each n\geq N, G_n-complexity of f over q times G^\prime_n-complexity of f minus 1 is less than \epsilon.

Definition 7. The complexity of a function f:\{ 0,1 \}^* \rightarrow \{ 0,1 \} is called T-complex if the circuit family that implements f using G_p for each n\in\mathbb{N} is T-sized.

Remark. By the Theorem 1. the Definition 7. is unambiguous up to a multiplication by a rational constant.

Quantum complexity:

Definition 1. A qubit is a vector in the two-dimensional vector space spanned by \left|0\right>,\left|1\right>, call H_Q.

Definition 2. An n-qubit system is the system \bigotimes_{i=1}^{n} H_Q. A basis for this space is the set of all \left|x\right>‘s where x \in \{0,1\}^n. So an n-qubit is a vector in \bigotimes_{i=1}^{n} H_Q. A k-qubit operator is a operator which acts non-trivially only on k coordinates of the n-qubit.

Definition 3. A local unitary operator is an operator from an n-qubit system to itself that is one- or two- qubit operator.

Definition 4. A quantum gate is a local unitary operator.

Definition 5. A quantum circuit is a circuit such that their inputs, outputs, and gates are quantum ones.

Example 1. Hadamard gate is the unitary operator I \bigotimes \cdot\cdot\cdot \bigotimes H \bigotimes \cdot\cdot\cdot \bigotimes I where H=\frac{1}{\sqrt{2}}\Big( \begin{smallmatrix} 1 & 1 \\ 1 & -1 \end{smallmatrix} \Big).

Example 2. Controlled-Not (C-NOT) gate is defined on H_Q \bigotimes H_Q such that for each x,y\in \{0,1\}, it maps \left|x,y\right> \rightarrow \left|x,x \oplus y\right> where x\oplus y is the parity (0 for oddness) of the number \bar{xy}.

Example 3. Controlled-U gate is defined on H_Q \bigotimes H_Q such that it maps \left|0,x\right>\rightarrow\left|0,x\right> and \left|1,x\right>\rightarrow\left|1,U x\right> for all x\in\{0,1\} and U is a unitary map from H_Q to itself. As a consequence, C-NOT gate is a Controlled-U gate with U=\Big( \begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix} \Big).

Remark. The set of all unitary operators from H_Q to itself is uncountable. So it is a contradiction if there were a finite sets of gates that had the universality property, it means that every unitary operator from H_Q to itself could be decomposed to implementations of these finite set of gates. However, if the C-NOT gates as well as all unitary one-qubit gates are available then any k-qubit unitary operation can be simulated with O(4^k k) such gates. Moreover, let V=\Big( \begin{smallmatrix} 1 & 0 \\ 0 & i \end{smallmatrix} \Big). Here is a related theorem:


Definition 6. Consider a finite set of quantum gates. We say it is approximately universal if the property in the above theorem holds for the operators in the set.

Definition 7. We call the set of quantum gates H and Controlled-V by QG_p. QG_p is local and approximately universal.

Definition 8. Let U a unitary operator from \bigotimes_{i=1}^{*} H_Q to itself and G a finite set of quantum gates that is local and approximately universal. The \epsilon-G_n-complexity of U is the minimum number of gates in G that is needed to approximate U on \bigotimes_{i=1}^{n} H_Q with the accuracy \epsilon.

Theorem 1. Let \epsilon>0, U an arbitrary unitary operator from \bigotimes_{i=1}^{*} H_Q to itself, and two sets of local and universal quantum gates called G,G^\prime. Then for n\geq N, any quantum circuit using n gates in G can be simulated with accuracy \epsilon by at most C n [log(\frac{n}{\epsilon})]^d gates in G^{\prime} where C and d are constants.

Definition 9. A family \{ C_n\}_{n\in\mathbb{N}} of quantum circuits are called T-sized where T:\mathbb{N}\rightarrow\mathbb{N} if |C_n|\leq T(n) for each n\in\mathbb{N}.

Definition 10. The complexity of U an arbitrary unitary operator from \bigotimes_{i=1}^{*} H_Q to itself is called \epsilon-T-complex if the quantum circuit family that implements f with accuracy \epsilon using the quantum gates in QG_p for each n\in\mathbb{N} is T-sized.

Remark. By the Theorem 1. the Definition 10. is unambiguous up to a multiplication by a polylogarithmic function.

Final Remark. In both classical and quantum cases, we could simply avoid this ambiguity by letting our T-functions vary over specific type of spaces. For instance, in classical case let \mathcal{C}(\mathbb{N}) the space of all function from \mathbb{N} to itself. Define the equivalence relation \sim on \mathcal{C}(\mathbb{N}) by this relation: f \sim g if and only if there exist a q\in\mathbb{Q} such that for every \epsilon>0 there is an N\in\mathbb{N} for each n\geq N, |q \frac{f(n)}{g(n)}-1|<\epsilon.


  1. An Introduction to Quantum Complexity Theory, Richard Cleve, arXiv:quant-ph/9906111v1
  2. Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak

Nothing out of simple fancy quantum mechanics!

Consider a free particle with the Hamiltonian H=\frac{P^2}{2m} where m is its mass and the dimension of the space is D. What are the Hamiltonian’s eigenstates? Any \left|p\right\rangle is an eigenstate for P^2. Is there any other eigenstate for P^2 that is not  \left|p\right\rangle? Of course \left|-p\right\rangle is one of them. In order to find the all eigenstates of H, consider f:L(\Phi)\rightarrow L(\Phi) is a linear operator on the space \Phi that is in the polynomials’s closure which acts separately on each coordinate. What are the eigenvectors of f(A) where A is self-adjoint and the eigenstates of A form a basis for \Phi? Consider f(A)=\sum_{i=1}^{D} f(A_i) where A_i acts only on the i-th coordinate. Assume f(A)\left|v\right\rangle=\lambda\left|v\right\rangle where \left|v\right\rangle\neq 0. We would have \langle b|f(A)\left|v\right\rangle=f(b) \langle b|v \rangle=\lambda \langle b|v \rangle. Since all \left|a\right\rangle (eigenstates of A) form a basis for \Phi and \left|v\right\rangle\neq0 there is at least a \left|b\right\rangle such that \langle b|v \rangle\neq0 and so \lambda=f(b). \langle b|v \rangle=0 if f(a)\neq f(b) unless \lambda would be equal to f(a). Conversely, if f(a)=f(b)=\lambda, then f(A)\left|v\right\rangle=\lambda\left|v\right\rangle. Hence, \left|v\right\rangle is equal to:

\left|v_b\right\rangle=\sum_{a:f(a)=f(b)} \alpha(a) \left|a\right\rangle – (1)

where \lambda=f(b), b varies over \mathbb{R}^D, and \alpha is a real valued function from \mathbb{R}^D.
Now assume f is one-to-one. So \left|v_b\right\rangle=\left|b\right\rangle and \lambda=f(b). Let f(B)=e^{\frac{-i}{\hbar}B}. If the Hamiltonian is time-independent then f(H) is the time evolution operator, say U, and since f(x)=e^{\frac{-i}{\hbar}x} is invertible, the eigenstates of U is exactly those of the Hamiltonian. Now let f(P)=P^2. Equation (1) indicates the wavefunction of the Hamiltonian should be equal to \psi(x)=\frac{1}{(2\pi\hbar)^{\frac{D}{2}}}\int_{p:p^2=q^2} dp \alpha(p)e^{ip\cdot x} where \int_{p:p^2=q^2} \left|\alpha(p)\right|^2 =1.

If D=1 then \left|v_q\right\rangle=\alpha\left|q\right\rangle+\beta\left|-q\right\rangle and \left|\alpha\right|^2+\left|\beta\right|^2=1. So for each q two vectors \left|v_1\right\rangle=\frac{\left|q\right\rangle+\left|-q\right\rangle}{\sqrt{2}} and \left|v_2\right\rangle=\frac{\left|q\right\rangle-\left|-q\right\rangle}{\sqrt{2}} are a basis for the eigenstates of \lambda=q^2. So a free particle could be in the state \left|v_1\right\rangle where its expected value of momentum is zero, however, its variance and the expected value of the Hamiltonian are non-zero. If we shift our zero point of energy, then \left|v_1\right\rangle indicates a free particle where its mean value of energy and momentum are zero but it does exist and fluctuate!