Background Image
Previous Page  3 / 14 Next Page
Information
Show Menu
Previous Page 3 / 14 Next Page
Page Background

Let us consider an arbitrary even permutation

h

A

(

Z

n

2

)

that defines

f

h

:

Z

n

2

Z

n

2

Boolean transformation. Let us introduce definitions of

reversible circuits, implementing

f

h

transformation either with or without

additional inputs.

Definition 1

.

Reversible circuit

S

g

implements transformation

f

h

without the use of extra inputs (extra memory), if it has precisely n

inputs, in addition there exists such permutation

π

S

(

Z

n

)

, that Boolean

transformation

g

:

Z

n

2

Z

n

2

defined by this circuit fulfils

ψ

π

n,n

(

g

(x)) =

=

f

h

(x)

,

(x)

Z

n

2

condition.

Definition 2

.

Reversible circuit

S

g

implements transformation

f

h

using

k >

0

extra inputs (extra memory) if it has

n

+

k

inputs; in addition

there is such permutation

π

S

(

Z

n

+

k

)

, that Boolean transformation

g

:

Z

n

+

k

2

Z

n

+

k

2

defined by this circuit fulfils

ψ

π

n

+

k,n

(

g

(

ϕ

n,n

+

k

(x))) =

=

f

h

(x)

,

(x)

Z

n

2

condition.

Let us note that a reversible circuit

S

g

defines transformation

f

h

when

g

(x) =

f

h

(x)

.

We recall some notions from the mathematical analysis [2]. If

f

(

n

)

and

g

(

n

)

are real-valued positive functions of natural variable

n

, then:

f

(

n

)

&

g

(

n

)

, if for any

ε >

0

there is

N

=

N

(

ε

)

,

then for any

n

>

N

inequation

(1

ε

)

g

(

n

)

6

f

(

n

)

(function

f

(

n

)

asymptotically exceeds or is

equal to

g

(

n

)

function) is true;

f

(

n

)

g

(

n

)

, if

f

(

n

)

&

g

(

n

)

and

g

(

n

)

&

f

(

n

)

(

f

(

n

)

and

g

(

n

)

functions are

asymptotically equal or equivalent

), then

lim

n

→∞

f

(

n

)

/g

(

n

) = 1

;

f

(

n

)

g

(

n

)

if

0

< c

1

< f

(

n

)

/g

(

n

)

< c

2

(

f

(

n

)

and

g

(

n

)

functions

are equivalent with the order accuracy

).

Now we can proceed to the estimation of the gate complexity of a

reversible circuit, composed of gates NOT, CNOT and 2-CNOT, defining

even permutation

h

A

(

Z

n

2

)

.

Asymptotic lower bound.

Let us introduce a set of reversible gates

named

Ω

m

n

, that includes all NOT and

k

-CNOT gates,

k

6

m

, each has

exactly

n

inputs.

There are total

(

n

k

)

k

n

different

k

-CNOT gates having

n

inputs.

We are interested in

Ω

2

n

set that consists of all possible NOT, CNOT and

2-CNOT gates with

n

inputs. The size of this set is equal to

|

Ω

2

n

|

=

2

X

k

=0

(

n

k

)

k

n

=

n

+

n

(

n

1)+

n

(

n

1)(

n

2)

2

=

O

(

n

3

)

.

(1)

In the reversible circuit model in question this situation is possible,

when rearrangement of two adjacent gates produces the equivalent circuit

ISSN 0236-3933. HERALD of the BMSTU. Series “Instrument Engineering”. 2015. No. 1 69