QIC Abstracts

 Vol.15 No.7&8, May 1, 2015

Research Articles:

Jordan-Wigner formalism for arbitrary 2-input 2-output matchgates and their classical simulation (pp0541-0556)
Richard Jozsa, Akimasa Miyake, and Sergii Strelchuk
In Valiant's matchgate theory, 2-input 2-output matchgates are $4\times 4$ matrices that satisfy ten so-called matchgate identities. We prove that the set of all such matchgates (including non-unitary and non-invertible ones) coincides with the topological closure of the set of all matrices obtained as exponentials of linear combinations of the 2-qubit Jordan-Wigner (JW) operators and their quadratic products, extending a previous result of Knill. In Valiant's theory, outputs of matchgate circuits can be classically computed in poly-time. Via the JW formalism, Terhal \& DiVincenzo and Knill established a relation of a unitary class of these circuits to the efficient simulation of non-interacting fermions. We describe how the JW formalism may be used to give an efficient simulation for all cases in Valiant's simulation theorem, which in particular includes the case of non-interacting fermions generalised to allow arbitrary 1-qubit gates on the first line at any stage in the circuit. Finally we give an exposition of how these simulation results can be alternatively understood from some basic Lie algebra theory, in terms of a formalism introduced by Somma et al. 

A note on the quantum collision and set equality problems (pp0557-0567)
Mark Zhandry
A collision for a function $f$ is two distinct inputs $x_1\neq x_2$ such that $f$ outputs the same value on both inputs: $f(x_1)=f(x_2)$. The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be $\Theta(N^{1/3})$; however, these results do not apply to random functions. The issues are two-fold. First, the $\Omega(N^{1/3})$ lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to $r$-to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of $\Theta(N^{1/3})$ holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal $\Omega(M^{1/3})$ lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions. 

Improving the quality of noisy spatial quantum channels (pp0568-0581)
Ning Tang, Zi-Long Fan, and Hao-Sheng Zeng

We show, for the non-Markovian or time-dependent Markovian model of noise, by breaking the noisy spatial quantum channel (SQC) into a series of periodically arranged sub-components, that the quality of information transmission described by the purity, fidelity and concurrence of the output states can be improved. The physical mechanism and possible implementation of the idea have been discussed. 

Quantum state transfer in disordered spin chains: How much engineering is reasonable? (pp0582-0600)
Analia Zwick, Gonzalo A. Alvarez, Joachim Stolze, and Omar Osenda
The transmission of quantum states through spin chains is an important element in the implementation of quantum information technologies. Speed and fidelity of transfer are the main objectives which have to be achieved by the devices even in the presence of imperfections which are unavoidable in any manufacturing process. To reach these goals, several kinds of spin chains have been suggested, which differ in the degree of fine-tuning, or engineering, of the system parameters. In this work we present a systematic study of two important classes of such chains. In one class only the spin couplings at the ends of the chain have to be adjusted to a value different from the bulk coupling constant, while in the other class every coupling has to have a specific value. We demonstrate that configurations from the two different classes may perform similarly when subjected to the same kind of disorder in spite of the large difference in the engineering effort necessary to prepare the system. We identify the system features responsible for these similarities and we perform a detailed study of the transfer fidelity as a function of chain length and disorder strength, yielding empirical scaling laws for the fidelity which are similar for all kinds of chain and all disorder models. These results are helpful in identifying the optimal spin chain for a given quantum information transfer task. In particular, they help in judging whether it is worthwhile to engineer all couplings in the chain as compared to adjusting only the boundary couplings.  

Momentum switches 601 (pp0601-0621)
Andrew M. Childs, David Gosset, Daniel Nagaj, Mouktik Raha, and Zak Webb
Certain continuous-time quantum walks can be viewed as scattering processes. These processes can perform quantum computations, but it is challenging to design graphs with desired scattering behavior. In this paper, we study and construct momentum switches, graphs that route particles depending on their momenta. We also give an example where there is no exact momentum switch, although we construct an arbitrarily good approximation. 

There is entanglement in the primes (pp0622-0659)
Jose I. Latorre and German Sierra
Large series of prime numbers can be superposed on a single quantum register and then analyzed in full parallelism. The construction of this Prime state is efficient, as it hinges on the use of a quantum version of any efficient primality test. We show that the Prime state turns out to be very entangled as shown by the scaling properties of purity, Renyi entropy and von Neumann entropy. An analytical approximation to these measures of entanglement can be obtained from the detailed analysis of the entanglement spectrum of the Prime state, which in turn produces new insights in the Hardy-Littlewood conjecture for the pairwise distribution of primes. The extension of these ideas to a Twin Prime state shows that this new state is even more entangled than the Prime state, obeying majorization relations. We further discuss the construction of quantum states that encompass relevant series of numbers and opens the possibility of applying quantum computation to Arithmetics in novel ways. 

Quantum relay cooperative communication via space-time transmission (pp0660-0676)
Jinjing Shi, Ronghua Shi, Xiaoqi Peng, Ying Guo, and Moon Ho Lee
Two novel quantum relay cooperative communication schemes $1S2R1D$ and $2S2R2D$ are proposed by applying the wireless communication technique in the quantum system. The orthogonal quantum signals in consecutive quantum sequences are prepared to avoid mutual interference and they are firstly transmitted to the quantum relay node and then to the destination node with space-time transmission. Moreover, quantum operations and transformations are implemented on the relay node and the destination node to maximize the correct information transmission. The fidelity between original and final received signals, the security, the quantum bit error rate and the lower bound on the capacity of quantum relay channels are analyzed. Especially it provides a valuable application prospect in long distance reliable quantum communications. 

W-like states are not necessary for totally correct quantum anonymous leader election (pp0677-0684)
Alexander Norton
I show that $W$-like entangled quantum states are not a necessary quantum resource for totally correct anonymous leader election protocols. This is proven by defining a symmetric quantum state that is $n$-partite SLOCC inequivalent to the $W$ state, and then constructing a totally correct anonymous leader election protocol using this state. This result, which contradicts the previous necessity result of D'Hondt and Panangaden, furthers our understanding of how non-local quantum states can be used as a resource for distributed computation. 

Solution to time-energy costs of quantum channels (pp0685-0693)
Chi-Hang F. Fung, H. F. Chau, Chi-Kwong Li, and Nung-Sing Sze
We derive a formula for the time-energy costs of general quantum channels proposed in [Phys. Rev. A {\bf 88}, 012307 (2013)]. This formula allows us to numerically find the time-energy cost of any quantum channel using positive semidefinite programming. We also derive a lower bound to the time-energy cost for any channels and the exact the time-energy cost for a class of channels which includes the qudit depolarizing channels and projector channels as special cases. 

Is absolute separability determined by the partial transpose? (pp0694-0720)
Srinivasan Arunachalam, Nathaniel Johnston, and Vincent Russo
The absolute separability problem asks for a characterization of the quantum states $\rho \in M_m\otimes M_n$ with the property that $U\rho U^\dagger$ is separable for all unitary matrices $U$. We investigate whether or not it is the case that $\rho$ is absolutely separable if and only if $U\rho U^\dagger$ has positive partial transpose for all unitary matrices $U$. In particular, we develop an easy-to-use method for showing that an entanglement witness or positive map is unable to detect entanglement in any such state, and we apply our method to many well-known separability criteria, including the range criterion, the realignment criterion, the Choi map and its generalizations, and the Breuer--Hall map. We also show that these two properties coincide for the family of isotropic states, and several eigenvalue results for entanglement witnesses are proved along the way that are of independent interest. 

back to QIC online Front page