109 Page 4 of 20 Eur. Phys. J. C (2019) 79 :109
(
ˆ
O
1
ˆ
O
2
)|ψ:=
ˆ
O
1
(
ˆ
O
2
|ψ), ∀|ψ . (2.4)
By the definition of realizable operators, it can be shown that
ˆ
O
1
ˆ
O
2
is realizable if
ˆ
O
1
and
ˆ
O
2
are both realizable operators.
Thus, O forms a monoid (semigroup with identity).
If we restrict physical processes to quantum mechanical
processes, Eq. (2.1) implies that realizable operators are all
unitary rather than Hermitian. In other words, our target is a
property of the physical process rather than a direct observ-
able. As quantum circuits are quantum mechanical processes
and Solovay–Kitaev theorem [31] says that all the unitary
operators can be approximated by some quantum circuits
with any nonzero tolerance, we can conclude that the realiz-
able operators set is the set of unitary operators. As unitary
operators are invertible, the realizable operators set O forms
a (finite dimensional or infinite dimensional) unitary group.
2
2.2 Definitions and axioms
Intuitively speaking, the circuit complexity (or computa-
tional complexity) of a target operator ( or computational
task) is defined by the minimal number of required funda-
mental gates ( or fundamental steps) to simulate the target
operator ( or finish the computational task). Based on this
intuitive concept of the complexity in quantum circuits and
computations, we propose that the complexity defined in
an arbitrary monoid O should satisfy the following three
axioms. We denote a complexity of an operator ˆx in an oper-
ators set O by C( ˆx).
G1 [Nonnegativity]
∀ˆx ∈ O, C( ˆx) ≥ 0 and the equality holds iff ˆx is the
identity.
G2 [Series decomposition rule (triangle inequality)]
∀ˆx, ˆy ∈ O, C( ˆx ˆy) ≤ C( ˆx) + C( ˆy).
G3 [Parallel decomposition rule]
∀( ˆx
1
, ˆx
2
) ∈ N = O
1
× O
2
⊆ O, C
( ˆx
1
, ˆx
2
)
=
C
( ˆx
1
,
ˆ
I
2
)
+ C
(
ˆ
I
1
, ˆx
2
)
.
Here, in G2, it is possible that the operator ˆx ˆy is decom-
posed in different ways, say ˆx
ˆy
. In this case, G2 can
read also as C( ˆx ˆy) = C( ˆx
ˆy
) ≤ C( ˆx
) + C( ˆy
).InG3,
we consider the case that there is a sub-monoid N ⊆ O
which can be decomposed into the Cartesian product of two
monoids, i.e., N = O
1
× O
2
.
ˆ
I
1
and
ˆ
I
2
are the identi-
ties of O
1
and O
2
. The Cartesian product of two monoids
implies that ( ˆx
1
, ˆx
2
)( ˆy
1
, ˆy
2
) = ( ˆx
1
ˆy
1
, ˆx
2
ˆy
2
) for arbitrary
( ˆx
1
, ˆx
2
), ( ˆy
1
, ˆy
2
) ∈ N .
2
Hermit operators, which correspond to observable quantities and are
not unitary in general, cannot be approximated by quantum circuits if
the tolerance is small enough.
# gates of
2
ˆ
x
+
# gates of # gates of
1
ˆ
x
2
ˆ
x
1
ˆ
1
ˆ
x
2
ˆ
Fig. 2 Schematic diagram for the complexity of the Cartesian prod-
uct and parallel decomposition rule. As two operators ˆx
1
and ˆx
2
are
simulated independently, the minimally required gates for ( ˆx
1
, ˆx
2
) is
the sum of the minimally required gates for ˆx
1
and ˆx
2
.Thus,wehave
C(( ˆx
1
, ˆx
2
)) = C(( ˆx
1
,
ˆ
I
2
)) + C((
ˆ
I
1
, ˆx
2
))
The axiom G1 is obvious by definition. We call the axiom
G2 “series decomposition rule” because the decomposition
of the operator
ˆ
O =ˆx ˆy to ˆx and ˆy is similar to the decompo-
sition of a big circuit into a series of small circuits. Reversely,
the ‘product’ of two operators corresponds to a serial con-
nection of two circuits. The axiom G2 answers a basic ques-
tion: what is the relationship between the complexities of two
operators and the complexity of their products? Because the
complexity is a kind of “minimal”, we require the inequality
in G2.
3
This G2 will lead to the familiar “triangle inequality”
in the concept of distance (see F3 in the Sect. 3)soitisalso
called “triangle inequality”.
In contrast to G2 (series decomposition rule), we call the
axiom G3 “parallel decomposition rule”, which is chosen
as one of the most basic axioms in defining complexity for
the first time in this paper.
4
It comes from the following
fundamental question: if an operator (task)
ˆ
O contains two
totally independent sub-operators (sub-tasks) ˆx
1
and ˆx
2
, what
should be the relationship between the total complexity and
the complexities of two sub-operators (sub-tasks)? Here, the
totally independent means that: (a)
ˆ
O accepts two inputs and
yields two outputs through ˆx
1
and ˆx
2
, and (b) the inputs for
ˆx
1
(or ˆx
2
) will never affect the outputs of ˆx
2
(or x
1
). See Fig. 2
for this explanation.
Mathematically, the construction of a bigger operator
ˆ
O
by ˆx
1
and ˆx
2
under two requirements (a) and (b) corresponds
to the Cartesian product denoted by
ˆ
O = ( ˆx
1
, ˆx
2
). Note that
3
The reason for axiom G2 has been explained clearly also in the Niel-
son’ works [20–22].
4
In some cases, the parallel decomposition may be impossible. How-
ever, in local computations/gates, the parallel decomposition is permit-
ted, for example see Ref. [32]. Our axiom G3 does not talk about the
possibility of the parallel decomposition, but says what will happen to
the complexity if the parallel decomposition is permitted.
123