An algorithm and a logic set for backtracking of conventional digital circuits are described. In this method, the signals flowing through a circuit are not deterministic in logical devices and wires, however they are possible to take overlapping states that are similarly expressed as the quantum state. In order to express the overlapping states, ternary logic is employed in which the third state represents the overlapping state. By using this, an overlapping state constructed with tensor products can be written as one term. A general state is expressed as a sum of such terms. The logical devices including reverse functions are introduced by the ternary-to-ternary logical functions. We applied this method to the prime factorization problem by considering it as backtracking of a logical circuit for multiplication. As an example, factorization of 66-bit composite number (33-bit integer x 33-bit integer) was successfully performed with an ordinary PC.
An algorithm and a logic set for backtracking of conventional digital circuits are described. In this method, the signals flowing through a circuit are not deterministic in logical devices and wires, however they are possible to take overlapping states that are similarly expressed as the quantum state. In order to express the overlapping states, ternary logic is employed in which the third state represents the overlapping state. By using this, an overlapping state constructed with tensor products can be written as one term. A general state is expressed as a sum of such terms. The logical devices including reverse functions are introduced by the ternary-to-ternary logical functions. We applied this method to the prime factorization problem by considering it as backtracking of a logical circuit for multiplication. As an example, factorization of 66-bit composite number (33-bit integer x 33-bit integer) was successfully performed with an ordinary PC.
Optical quantum devices are promoting the development not only of communication but also of quantum computation using optical quantum gates. We will explain how to replace circuits consisting of gates such as NOT and AND used in classical logic calculations with quantum calculation gates. These classical gates can be expressed as NOT and CNOT of quantum computing gates. We show how to express these quantum gates as optical devices using the behavior of the polarization of discrete photons. Next, we describe the backtracking method of quantum circuits utilizing the reversibility of quantum gates. As classical gates are not unitary, we use probabilistic methods that rely on measurements. In a typical classical gate, there are multiple inputs corresponding to a certain output, so backtracking requires tracing multiple states. The quantum bit representation, which can represent superposition states, is suitable for this purpose. As an application example, we explain how to backtrack integer multipliers and perform factorization. In a configuration using quantum gates, one measurement quantum bit is required for each element, resulting in a large number of state bits. However, by reusing bits that are no longer needed, it was possible to construct a circuit with a number of state bits proportional to the number of bits for the integer multiplicand. We simulated an integer multiplier circuit by combining classical gates and backtracked the circuit to derive two factors from a composite number represented by quantum bits. By performing a simulation on a PC, we succeeded in factorizing a 100-bit composite number, subject to the condition that it is a product of two prime numbers close to less than 2m1−1 and 2m2−1, where m1 and m2 are integers. We compare our method with the calculation using satisfiability (SAT) for the factoring problem.
Optical quantum devices are promoting the development not only of communication but also of quantum computation using optical quantum gates. Here, we will explain how to replace circuits consisting of gates such as NOT, AND, etc. used in classical logic calculations with quantum calculation gates. These classical gates can be expressed as NOT and CNOT of quantum computing gates. We show how to express these quantum gates as optical devices using the behavior of the polarization of discrete photons. Next, we describe the backtracking method of quantum circuits utilizing the reversibility of quantum gates. Since classical gates are not unitary, we use probabilistic methods that rely on measurements. In a typical classical gate, there are multiple inputs corresponding to a certain output, so backtracking requires tracing multiple states. The quantum bit representation, which can represent superposition states, is suitable for this purpose. As an application example, we explain how to backtrack integer multipliers and perform factorization. In configuration using quantum gates, one measurement quantum bit is required for each element, resulting in a large number of state bits. However, by reusing bits that are no longer needed, it was possible to construct a circuit with a number of state bits proportional to the number of bits for the integer multiplicand. We simulated an integer multiplier circuit by combining classical gates, and backtrack the circuit to derive two factors from a composite number represented by quantum bits. We performed simulations on a PC and succeeded in factorizing a 100-bit composite number.
Ternary reversible logic functions are generally represented as ternary Galois field sum of products (TGFSOP) expressions and the TGFSOP expressions are mapped to reversible circuits using cascades of Feynman and Toffoli gates. Although a ternary logic function with a large number of variables can be minimized as a TGFSOP expression, the process is computationally expensive and the resulting reversible circuit tends to have a high quantum cost and ancilla inputs. To overcome these limitations, in this work we propose a new method of representing ternary reversible logic functions as Max of Min-terms (Max-Min) expressions, which can be mapped to a reversible circuit using multiple-controlled unary gates requiring lower quantum cost and fewer ancilla inputs. We propose a map-based minimization method for Max-Min expressions of up to four variables focusing on restrictions of the reversible circuit mapping technique.
If we like to make an arbitrary permutation of a large number (say n) objects, where n is a non-prime number (n = pq, with both p and q integer), it is advantageous to arrange the objects in a rectangular p×q matrix. Then the permutation can be performed in three steps: first one applies a permutation where all objects remain in the same row, then one applies a permutation where all objects remain in the same column, and finally one applies a second permutation where all objects remain in the same row. In telecommunication, this remarkable theorem is the basis of so-called Clos networks, where w communication wires have to be permuted, according to one of the w! possible permutations. In binary digital communication, w wires transport one of the 2w possible messages. Reversible computing consists of applying a permutation, not to the w wires but to the 2w possible messages. The Clos approach allows us to build reversible binary computers very efficiently. The approach is somewhat less efficient for multiple-valued reversible logic and, unfortunately, is not applicable at all for arbitrary quantum circuits.
Synthesis of ternary quantum circuits involves basic ternary gates and logic operations in the ternary quantum domain. Works that define ternary algebra and their applications for ternary quantum logic realization, are very few. In this paper, we express a ternary logic function in terms of projection operations including a new one. We demonstrate how to realize a few new multi-qutrit ternary gates in terms of generalized ternary gates and projection operations. We then employ our synthesis method to design ternary adder circuits which have better cost than that obtained by earlier method.
While the role of ternary reversible and quantum computation has been growing, synthesis methodologies for such logic, have been addressed in only a few works. A reversible ternary logic function can be expressed as minterms by using projection operators. In this paper, a novel realization of the projection operators using a minimum number of permutative ternary Muthukrishnan-Stroud (M-S) gates is presented. Next, an efficient method for logic simplification for ternary reversible logic is proposed. This method along with the new construction of projection operators yields significantly lower gate cost of approximately 31% less than that obtained by earlier methodologies, for the synthesis of ternary benchmark circuits.