n-bit quantum gate accomplished by two-bit quantum gates

Jing Mang Xu, Shou Zhang, 연규황 +1 more

Kai-Wen Cheng, Chien‐Cheng Tseng

The designs of quantum full adder (QFA) and quantum full subtractor (QFS) are investigated. First, the 1-bit QFA and 1-bit QFS are designed according to the classical truth tables. The adder and subtractor for two n-bits numbers are then separately constructed from n 1-bit QFAs and QFSs. The number of elementary quantum gates to accomplish the design of n-bits adder and subtractor are 4n and 8n, respectively.

Claudio Chamon, Eduardo R. Mucciolo

We propose a form of parallel computing on classical computers that is based on matrix product states. The virtual parallelization is accomplished by representing bits with matrices and by evolving these matrices from an initial product state that encodes multiple inputs. Matrix evolution follows from the sequential application of gates, as in a logical circuit. The action by classical probabilistic one-bit and deterministic two-bit gates such as NAND are implemented in terms of matrix operations and, as opposed to quantum computing, it is possible to copy bits. We present a way to explore this method of computation to solve search problems and count the number of solutions. We argue that if the classical computational cost of testing solutions (witnesses) requires less than O(n2) local two-bit gates acting on n bits, the search problem can be fully solved in subexponential time. Therefore, for this restricted type of search problem, the virtual parallelization scheme is faster than Grover's quantum algorithm.

Bettina Just

Noriaki Horiuchi

Klemens Hammerer, Guifré Vidal, J. I. Cirac

A nonlocal unitary transformation of two-qubits occurs when some Hamiltonian interaction couples them. Here we characterize the amount, as measured by time, of interaction required to perform two-qubit gates, when also arbitrarily fast, local unitary transformations can be applied on each qubit. The minimal required time of interaction, or interaction cost, defines an operational notion of the degree of nonlocality of gates. We characterize a partial order structure based on this notion. We also investigate the interaction cost of several communication tasks, and determine which gates are able to accomplish them. This classifies two-qubit gates into four categories, differing in their capability to transmit classical, as well as quantum, bits of information.