8
\$\begingroup\$

Reversible computation refers to computation in which little or no information is deleted. Reversible computation a major component of quantum computation, and reversible computation is potentially many times more energy efficient than conventional computation. I want to know how easy it is to compute the conjugacy of transpositions reversibly?

Challenge

Let T5 be the set of all transpositions on the set {1,2,3,4,5}. Let be the conjugacy operation on T5 defined by x * y=xyx^(-1) (here concatenation denotes the symmetric group operation). In other words, the underlying set of T5 consists of all 10 pairs (a,b) of distinct numbers from {1,2,3,4,5} and where we declare (a,b)=(b,a). The operation is the unique operation on the underlying set that satisfies

  • (a,b) * (c,d)=(c,d),
  • (a,b) * (b,c)=(a,c),
  • (a,b) * (a,b)=(a,b)
whenever a,b,c,d are distinct.

What is the simplest n bit input reversible circuit C along with an injective function R:T5->{0,1}^(n/2) such that C(R(x)||R(y))=R(x)||R(x*y) for all x,y in T5?

The gate cost of a reversible circuit shall be the sum of the costs of every individual logic gate in the reversible circuit.

Here is the price chart per logic gate (see this link for a description of the logic gates) along with a description of the reversible gates.

Each SWAP gate (x,y)->(y,x) will have a cost of 0.

Each NOT gate x-> NOT x shall have a cost of 1.

Each CNOT gate (x,y)->(x,x XOR y) shall have a cost of 2.

Each Fredkin gate (x,y,z)->(x,(NOT x AND y) OR (x AND z),(x AND y) OR (NOT x AND z)) shall have a cost of 4 (the Fredkin gate can also be described as the reversible logic gate where (0,x,y)->(0,x,y) and (1,x,y)->(1,y,x)).

Each Toffoli gate (x,y,z)->(x,y,(x AND y) XOR z) shall have a cost of 5.

No other gates are allowed.

Observe that each reversible gate has the same number of inputs as it has outputs (this feature is required for all reversible gates).

The complexity of your circuit will be the product of the gate cost or your circuit with the number n which you choose. The goal of this challenge will be to minimize this measure of complexity.

Format

Complexity: This is your final score. The complexity is the product of the number n with your total gate cost.

Space: State the number n of bits that your circuit C acts on.

Total gate cost: State the sum of the costs of each of the individual gates in your circuit C.

NOT gate count: State the number of NOT gates.

CNOT gate count: State the number of CNOT gates.

Toffoli gate count: How many Toffoli gates are there?

Fredkin gate count: How many Fredkin gates are there?

Legend: Give a description of the function R. For example, you may write

(1,2)->0000;(1,3)->0001;(1,4)->0010;(1,5)->0011;(2,3)->0100; (2,4)->0101;(2,5)->0110;(3,4)->0111;(3,5)->1000;(4,5)->1001 .

Gate list: Here list the gates in the circuit C from first to last. Each gate shall be written in the form [Gate type abbreviation,lines where the gates come from]. For this problem, we shall start with the 0th bit. The following list specifies the abbreviations for the type of gates.

T-Toffoli gate S-Swap gate C-CNOT gate F-Fredkin gate N-Not gate.

For example, [T,1,5,3] would denote a Toffoli gate acting on the 1st bit, the 5th bit, and the 3rd bit. For example, [T,2,4,6] produces the transformation 01101010->01101000 and [C,2,1] produces 011->001,010->010 and [N,3] produces 0101->0100. For example, one could write [S,7,3],[N,2],[T,1,2,3],[F,1,2,5],[C,7,5] for the gate list.

The gates act on the bit string from left to right. For example, the gate list [C,0,1],[C,1,0] will produce the transformation 01->11.

Sample answer format

Complexity: 128

Space: 8

Total gate cost: 16

NOT gate count: 3

CNOT gate count: 2

Toffoli gate count: 1

Fredkin gate count: 1

Legend: (1,2)->0000;(1,3)->0001;(1,4)->0010;(1,5)->0011;(2,3)->0100; (2,4)->0101;(2,5)->0110;(3,4)->0111;(3,5)->1000;(4,5)->1001

Gate list: [N,1],[N,0],[N,3],[S,1,2],[S,2,3],[C,0,1],[C,2,3],[T,3,2,1],[F,2,3,1]

The sample answer format is not a solution to the problem but is a template for the format for a solution.

Improve this question
\$\endgroup\$
14
  • \$\begingroup\$ @user202729 R is just the I/O format. You choose 10 distinct, consistent values for the transpositions. \$\endgroup\$
    – feersum
    Sep 11, 2018 at 14:56
  • \$\begingroup\$ By the way, the post format is way too strict, and not very readable. I guess you have a verifier, in that case can you post that? \$\endgroup\$
    – DELETE_ME
    Sep 11, 2018 at 14:57
  • \$\begingroup\$ I am still working on the verifier. I will post it as soon as possible. \$\endgroup\$
    – Joseph Van Name
    Sep 11, 2018 at 15:21
  • 3
    \$\begingroup\$ I might be mistaken, but isn't the function f((x, y)) = (x, x * y) an involution? f((x, y)) = (x, xyx^(-1)), f(f(x, y)) = (x, x(xyx^(-1))x^(-1)) = (x, x^2yx^(-2)) = (x, y). If so, just have paired elements differ on two bits; have one with 01, and the other with 10, or 00 for elements mapping to them-self. Then you only need a single swap gate. \$\endgroup\$
    – user1502040
    Sep 11, 2018 at 23:05
  • \$\begingroup\$ @user1502040. You are right. I need to edit the question once again. I apologize for my sloppiness. \$\endgroup\$
    – Joseph Van Name
    Sep 12, 2018 at 2:27

1 Answer 1

Reset to default
2
\$\begingroup\$

640 480

Complexity: 480
CSWAP count: 12
Legand: (1,2)->11000, (1,3)->10100, ..., (4,5)->00011
Gate: 
[1,6,7],
[3,6,8],[3,6,7],
[4,6,9],[4,6,7],
[5,6,10],
[SWAP,6,7],
[5,6,10],
[4,6,7],[4,6,9],
[3,6,7],[3,6,8],
[1,6,7]

enter image description here

Use 6 and 7 as a stack to push the two mentioned pairs, then swap them and pop back. the chosen one of 6 or 7 is initially on stack top, if the other isn't

Improve this answer
\$\endgroup\$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.