Vol.20 No.3&4, March 5, 2020

Research Articles:

Rational proofs for quantum computing (pp181-193)
          Tomoyuki Morimae and Harumichi Nishimura
It is an open problem whether a classical client can delegate quantum computing to an efficient remote quantum server in such a way that the correctness of quantum computing is somehow guaranteed. Several protocols for verifiable delegated quantum computing have been proposed, but the client is not completely free from any quantum technology: the client has to generate or measure single-qubit states. In this paper, we show that the client can be completely classical if the server is rational (i.e., economically motivated), following the ``rational proofs" framework of Azar and Micali. More precisely, we consider the following protocol. The server first sends the client a message allegedly equal to the solution of the problem that the client wants to solve. The client then gives the server a monetary reward whose amount is calculated in classical probabilistic polynomial-time by using the server's message as an input. The reward function is constructed in such a way that the expectation value of the reward (the expectation over the client's probabilistic computing) is maximum when the server's message is the correct solution to the problem. The rational server who wants to maximize his/her profit therefore has to send the correct solution to the client.

A method of mapping and nearest neighbor optimization for 2-D quantum circuits (pp194-212)
          Yuxin Zhang, Zhijin. Guan, Longyong Ji, Qin Fang Luan and Yizhen Wang
In some practical quantum physical architectures, the qubits need to be distributed on 2-dimensional (2-D) grid structure to implement quantum computation. In order to map an 1-dimensional  (1-D) quantum circuit into a 2-D grid structure and satisfy the nearest neighbor constraint of qubit interaction in the grid structure, a mapping method from 1-D quantum circuit to 2-D grid structure is proposed in this paper. This method firstly determines the order of placing qubits, and then presents the layout strategy of qubits in 2-D grid.  We also proposed an algorithm for establishing interaction paths between non-adjacent qubits in 2-D grid structure, which can satisfy the physical constraints of the interaction of quantum bits in the grid in the process of mapping an 1-D quantum circuit to a 2-D grid structure. For some benchmark circuits, after using the method of this paper to place qubits, it is possible to make every 2-qubit gate in the circuit have a nearest neighbor, so that there is no need to use SWAP gate to establish channel routing. Compared with the latest available methods, the average optimization rate is 82.38\%.

A local model of quantum Turing machines (pp213-229)
          Dong-Sheng Wang
The model of local Turing machines is introduced, including classical and quantum ones, in the framework of matrix-product states. The locality refers to the fact that at any instance of the computation the heads of a Turing machine have definite locations. The local Turing machines are shown to be equivalent to the corresponding circuit models and standard models of Turing machines by simulation methods. This work reveals the fundamental connection between tensor-network states and information processing.

Quantum walks as mathematical foundation for quantum gates (pp230-258)
          Dmitry Solenov
It is demonstrated that in gate-based quantum computing architectures quantum walk is a natural mathematical description of quantum gates. It originates from field-matter interaction driving the system, but is not attached to specific qubit designs and can be formulated for very general field-matter interactions. It is shown that, most generally, gates are described by a set of coined quantum walks. Rotating wave and resonant approximations for field-matter interaction simplify the walks, factorizing the coin, and leading to pure continuous time quantum walk description. The walks reside on a graph formed by the Hilbert space of all involved qubits and auxiliary states, if present. Physical interactions between different parts of the system necessary to propagate entanglement through such graph---quantum network---enter via reduction of symmetries in graph edges. Description for several single- and two-qubit gates are given as examples.

back to QIC online Front page