QIC Abstracts

 Vol.20 No.1&12, February 1, 2020

Research Articles:

Some considerations on quantum computing at sub-atomic scales and its impact in the future of Moore's law (pp1-13)
          
Nicolas F. Lori, Jos Neves, Alex H. Blin, and Victor Alves
The contemporary development of Quantum Computers has opened new possibilities for computation improvements, but the limits of Moore's law validity are starting to show. We analyze here the possibility that miniaturization will continue to be the source of Moore's law validity in the near future, and our conclusion is that miniaturization is no longer a reliable answer for the future development of computer science, but instead we suggest that lateralization is the correct approach. By lateralization, we mean the use of biology as the correct format for the implementation of ubiquitous computerized systems, a format that might in many circumstances eschew miniaturization as an overly expensive useless advantage whereas in other cases miniaturization might play a key role. Thus, the future of computer science is not towards a miniaturization that goes from the atom-scale (its present application scale) towards the nucleus-scale, but rather in developing more integrated circuits at the micrometer to nanometer scale, so as to better mimic and interact with biological systems. We analyze some "almost sci-fi" approaches to the development of better computer systems near the Bekenstein bound limit, and unsurprisingly they fail to have any realistic feasibility. Then, we use the difference between the classical vs. quantum version of the Hammerstein-Clifford theorem to explain why biological systems eschewed quantum computation to represent the world but have chosen classical computation instead. Finally, we analyze examples of recent work which indicate future possibilities of integration between computers and biological systems. As a corollary of that choice by the biological systems, we propose that the predicted lateralization-driven evolution in computer science will not be based in quantum computers, but rather in classical computers.

Quantum algorithm for matrix functions by Cauchy's integral formula (pp14-36)
          
Souichi Takahira, Asuka Ohashi, Tomohiro Sogabe, and Tsuyoshi S. Usuda
For matrix $A$, vector $\vec{b}$ and function $f$, the computation of vector $f(A)\vec{b}$ arises in many scientific computing applications. We consider the problem of obtaining quantum state $\ket{f}$ corresponding to vector $f(A)\vec{b}$. There is a quantum algorithm to compute state $\ket{f}$ using eigenvalue estimation that uses phase estimation and Hamiltonian simulation $\e^{\im A t}$. However, the algorithm based on eigenvalue estimation needs $\poly(1/\epsilon)$ runtime, where $\epsilon$ is the desired accuracy of the output state. Moreover, if matrix $A$ is not Hermitian, $\e^{\im A t}$ is not unitary and we cannot run eigenvalue estimation. In this paper, we propose a quantum algorithm that uses Cauchy's integral formula and the trapezoidal rule as an approach that avoids eigenvalue estimation. We show that the runtime of the algorithm is $\poly(\log(1/\epsilon))$ and the algorithm outputs state $\ket{f}$ even if $A$ is not Hermitian.

Quantum entanglement, supersymmetry, and the generalized Yang-Baxter equation (pp37-64)
          
Pramod Padmanabhan, Fumihiko Sugino, and Diego Trancanelli
Entangled states, such as the Bell and GHZ states, are generated from separable states using matrices known to satisfy the Yang-Baxter equation and its generalization. This remarkable fact hints at the possibility of using braiding operators as quantum entanglers, and is part of a larger speculated connection between topological and quantum entanglement. We push the analysis of this connection forward, by showing that supersymmetry algebras can be used to construct large families of solutions of the spectral parameter-dependent generalized Yang-Baxter equation. We present a number of explicit examples and outline a general algorithm for arbitrary numbers of qubits. The operators we obtain produce, in turn, all the entangled states in a multi-qubit system classified by the Stochastic Local Operations and Classical Communication protocol introduced in quantum information theory.

Quantum period finding based on the Bernstein-Vazirani algorithm (pp65-84)
          
Xuexuan Hao, Fengrong Zhang, Yongzhuang Wei, and Yong Zhou
Quantum period finding algorithms have been used to analyze symmetric cryptography. For instance, the 3-round Feistel construction and the Even-Mansour construction could be broken in polynomial time by using quantum period finding algorithms. In this paper, we firstly provide a new algorithm for finding the nonzero period of a vectorial function with $O(n)$ quantum queries, which uses the Bernstein-Vazirani algorithm as one step of the subroutine. Afterwards, we compare our algorithm with Simon's algorithm. In some scenarios, such as the Even-Mansour construction and the function satisfying Simon's promise, etc, our algorithm is more efficient than Simon's algorithm with respect to the tradeoff between quantum memory and time. On the other hand, we combine our algorithm with Grover's algorithm for the key-recovery attack on the FX construction. Compared with the Grover-Meets-Simon algorithm proposed by Leander and May at Asiacrypt 2017, the new algorithm could save the quantum memory.

back to QIC online Front page