QIC Abstracts

 Vol.7 No.5&6 July 1, 2007

Research Articles: 
Matrix product state representations (pp401-430)
          D. Perez-Garcia, F. Verstraete, M.M. Wolf, and J.I. Cirac
This work gives a detailed investigation of matrix product state (MPS) representations for pure multipartite quantum states. We determine the freedom in representations with and without translation symmetry, derive respective canonical forms and provide efficient methods for obtaining them. Results on frustration free Hamiltonians and the generation of MPS are extended, and the use of the MPS-representation for classical simulations of quantum systems is discussed.

Security of quantum key distribution using weak coherent states with nonrandom phases (pp431-458)
          H.-K. Lo and J. Preskill 
We prove the security of the Bennett-Brassard (BB84) quantum key distribution protocol in the case where the key information is encoded in the relative phase of a coherent-state reference pulse and a weak coherent-state signal pulse, as in some practical implementations of the protocol. In contrast to previous work, our proof applies even if the eavesdropper knows the phase of the reference pulse, provided that this phase is not modulated by the source, and even if the reference pulse is bright. The proof also applies to the case where the key is encoded in the photon polarization of a weak coherent-state pulse with a known phase, but only if the phases of the four BB84 signal states are judiciously chosen. The achievable key generation rate scales quadratically with the transmission in the channel, just as for BB84 with phase-randomized weak coherent-state signals (when decoy states are not used). For the case where the phase of the reference pulse is strongly modulated by the source, we exhibit an explicit attack that allows the eavesdropper to learn every key bit in a parameter regime where a protocol using phase-randomized signals is provably secure.

Evolution from entanglement to decoherence (pp459-468)
          T. Yu and J.H. Eberly 
We examine a class of bipartite mixed states which we call X states and report several analytic results related to the occurrence of early-stage decoherence or so-called entanglement sudden death (ESD) under time evolution in the presence of common types of environmental noise. Avoidance of sudden death by application of purely local operations is shown to be feasible in some cases.

Controllable Subsystems of  Quantum Dynamical Systems (pp469-478)
          M. Zhang,  H.-Y. Dai, G.-H. Dong, H.-W. Xie, and D.-W. Hu 
This paper proposes the concept of subsystem controllability for both closed and open quantum dynamical systems, and the existence conditions of controllable subsystems are derived accordingly. It is demonstrated that a controllable subsystem may exist for a closed quantum dynamical system even if the overall system is not controllable. Furthermore, we also demonstrate that, for a class of decoherence-free subsystems of Markovian open quantum dynamical
systems, the subsystems are controllable under open-loop coherent control if the initial states of the open systems are factorized. To a certain extent, this paper gives an alternative control theoretical interpretation on why decoherence-free subsystems are useful for quantum computation.

Quantum automata, braid group and link polynomials (pp479-503)
          S. Garnerone, A. Marzuoli, and M. Rasetti
The spin--network quantum simulator model, which essentially encodes
the (quantum deformed) $SU(2)$ Racah--Wigner tensor algebra, is particularly suitable to address problems arising in low dimensional topology and group theory. In this combinatorial framework we implement families of finite--states and discrete--time quantum automata capable of accepting the language generated by the braid group, and whose transition amplitudes are colored Jones polynomials. The automaton calculation of the polynomial of (the plat closure of) a link $L$ on $2N$ strands at any fixed root of unity is shown to be bounded from above by a linear function of the number of crossings of the link, on the one hand, and polynomially bounded in terms of the braid index $2N$, on the other. The growth rate of the time complexity function in terms of the integer $k$ appearing in the root of unity $q$ can be estimated to be (polynomially) bounded by resorting to the field theoretical background given by the Chern--Simons theory.

On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems (pp504-521)
          A.M. Childs and P. Wocjan
We consider an approach to deciding isomorphism of rigid n-vertex graphs (and related isomorphism problems) by solving a nonabelian hidden shift problem on a quantum computer using the standard method. Such an approach is arguably more natural than viewing the problem as a hidden subgroup problem. We prove that the hidden shift approach to rigid graph isomorphism is hard in two senses. First, we prove that \Omega(n) copies of the hidden shift states are necessary to solve the problem (whereas O(n\log n) copies are sufficient). Second, we prove that if one is restricted to single-register measurements, an exponential number of hidden shift states are required.

Probability estimates for Shor's algorithm (pp522-550)
          P.S. Bourdon and H.T. Williams
Let N be a (large) positive integer, let b be an integer satisfying 1< b < N that is relatively prime to N, and let r be the order of b modulo N. Finally, let QC be a quantum computer whose input register has the size specified in Shor's original description of his order-finding algorithm. In this paper, we analyze the probability that a single run of the quantum component of the algorithm yields useful information---a nontrivial divisor of the order sought. We prove that when Shor's algorithm is implemented on QC, then the probability P of obtaining a (nontrivial) divisor of $r$ exceeds $.7$ whenever N \ge 2^{11} and r\ge 40, and we establish that $.7736$ is an asymptotic lower bound for $P$. When $N$ is not a power of an odd prime, Gerjuoy has shown that $P$ exceeds 90 percent for $N$ and $r$ sufficiently large. We give easily checked conditions on N and r for this 90 percent threshold to hold, and we establish an asymptotic lower bound for $P$ of 2\Si(4\pi)/\pi ~0.9499 in this situation. More generally, for any nonnegative integer $q$, we show that when QC(q) is a quantum computer whose input register has $q$ more qubits than does QC, and Shor's algorithm is run on QC(q), then an asymptotic lower bound on P is 2\Si(2^{q+2}\pi)/\pi (if N is not a power of an odd prime). Our arguments are elementary and our lower bounds on P are carefully justified.

Quantum cloning of identical mixed qubits (pp551-558)
          H. Fan, B.-Y. Liu, and K.-J. Shi
Quantum cloning of two identical mixed qubits $\rho \otimes \rho$ is studied. We propose the quantum cloning transformations not only for the triplet (symmetric) states but also for the singlet (antisymmetric) state. We can copy these two identical mixed qubits to $M$ ($M\ge 2$) copies. This quantum cloning machine is optimal in the sense that the shrinking factor between the input and the output single qubit achieves the upper bound. The result shows that we can copy two identical mixed qubits with the same quality as that of two identical pure states.

Efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups (pp559-570)
          Y. Inui and F. Le Gall
In this paper, we consider the hidden subgroup problem (HSP) over the class of semi-direct product groups $\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_q$, for $p$ and $q$ prime. We first present a classification of these groups in five classes. Then, we describe a polynomial-time quantum algorithm solving the HSP over all the groups of one of these classes: the groups of the form $\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_p$, where $p$ is an odd prime. Our algorithm works even in the most general case where the group is presented as a black-box group with not necessarily unique encoding. Finally, we extend this result and present an efficient algorithm solving the HSP over the groups $\mathbb{Z}^m_{p^r}\rtimes\mathbb{Z}_p$.

Book Review: 
On “Protecting information: from classical error correction to quantum cryptography (authored by S. Loepp and W. Wootters)” (pp571-572)
          G.J. Milburn

back to QIC online Front page