QIC Abstracts

 Vol.12 No.5&6, May 1, 2012

Research Articles:

Constant-optimized quantum circuits for modular multiplication and exponentiation (pp0361-0394)
Igor L. Markov and Mehdi Saeedi
Reversible circuits for modular multiplication $Cx\%M$ with $x<M$ arise as components of modular exponentiation in Shor's quantum number-factoring algorithm. However, existing generic constructions focus on asymptotic gate count and circuit depth rather than actual values, producing fairly large circuits not optimized for specific $C$ and $M$ values. In this work, we develop such optimizations in a bottom-up fashion, starting with most convenient $C$ values. When zero-initialized ancilla registers are available, we reduce the search for compact circuits to a shortest-path problem. Some of our modular-multiplication circuits are asymptotically smaller than previous constructions, but worst-case bounds and average sizes remain $\Theta(n^2)$. In the context of modular exponentiation, we offer several constant-factor improvements, as well as an improvement by a constant additive term that is significant for few-qubit circuits arising in ongoing laboratory experiments with Shor's algorithm.

Encryption with weakly random keys using quantum ciphertext (pp0395-0403)
Jan Bouda, Matej Pivoluska, and Martin Plesch
The lack of perfect randomness can cause significant problems in securing communication between two parties. McInnes and Pinkas \cite{McInnesPinkas-ImpossibilityofPrivate-1991} proved that unconditionally secure encryption is impossible when the key is sampled from a weak random source. The adversary can always gain some information about the plaintext, regardless of the cryptosystem design. Most notably, the adversary can obtain full information about the plaintext if he has access to just two bits of information about the source (irrespective on length of the key). In this paper we show that for every weak random source there is a cryptosystem with a classical plaintext, a classical key, and a quantum ciphertext that bounds the adversary's probability $p$ to guess correctly the plaintext strictly under the McInnes-Pinkas bound, except for a single case, where it coincides with the bound. In addition, regardless of the source of randomness, the adversary's probability $p$ is strictly smaller than $1$ as long as there is some uncertainty in the key (Shannon/min-entropy is non-zero). These results are another demonstration that quantum information processing can solve cryptographic tasks with strictly higher security than classical information processing.

The monomial representations of the Clifford group (pp0404-0431)
D. Markus Appleby, Ingemar Bengtsson, Stephen Brierley, Markus Grassl, David Gross, and Jan-Ake Larsson
We show that the Clifford group---the normaliser of the Weyl-Heisenberg group---can be represented by monomial phase-permutation matrices if and only if the dimension is a square number. This simplifies expressions for SIC vectors, and has other applications to SICs and to Mutually Unbiased Bases. Exact solutions for SICs in dimension 16 are presented for the first time.

An intuitive proof of the data processing inequality (pp0432-0441)
Normand J. Beaudry and Renato Renner
The data processing inequality (DPI) is a fundamental feature of information theory. Informally it states that you cannot increase the information content of a quantum system by acting on it with a local physical operation. When the smooth min-entropy is used as the relevant information measure, then the DPI follows immediately from the definition of the entropy. The DPI for the von Neumann entropy is then obtained by specializing the DPI for the smooth min-entropy by using the quantum asymptotic equipartition property (QAEP). We provide a short proof of the QAEP and therefore obtain a self-contained proof of the DPI for the von Neumann entropy.

Optimal estimation of quantum processes using incomplete information: variational quantum process tomography (pp0442-0447)
Thiago O. Maciel and Reinaldo O. Vianna
We develop a quantum process tomography method, which variationally reconstruct the map of a process, using noisy and incomplete information about the dynamics. The new method encompasses the most common quantum process tomography schemes. It is based on the variational quantum tomography method (VQT) proposed by Maciel \emph{et al.} in arXiv:1001.1793[quant-ph] \cite{VQT}.

Long distance two-party quantum crypto made simple (pp0448-0460)
Iordanis Kerenidis and Stephanie Wehner
Any two-party cryptographic primitive can be implemented using quantum communication under the assumption that it is difficult to store a large number of quantum states perfectly. However, achieving reliable quantum communication over long distances remains a difficult problem. Here, we consider a large network of nodes with only neighboring quantum links. We exploit properties of this cloud of nodes to enable any two nodes to achieve security even if they are not directly connected. Our results are based on techniques from classical cryptography and do not resort to technologically difficult procedures like entanglement swapping. More precisely, we show that oblivious transfer can be achieved in such a network if and only if there exists a path in the network between the sender and the receiver along which all nodes are honest. Finally, we show that useful notions of security can still be achieved when we relax the assumption of an honest path. For example, we show that we can combine our protocol for oblivious transfer with computational assumptions such that we obtain security if either there exists an honest path, or, as a backup, at least the adversary cannot solve a computational problem.

Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems (pp0461-0471)
Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura

This paper proves that classical-witness quantum Merlin-Arthur proof systems can achieve perfect completeness. That is, ${\QCMA = \QCMA_1}$. This holds under any gate set with which the Hadamard and arbitrary classical reversible transformations can be exactly implemented, \emph{e.g.}, ${\{\textrm{Hadamard, Toffoli, NOT}\}}$. The proof is quantumly nonrelativizing, and uses a simple but novel quantum technique that \emph{additively} adjusts the success probability, which may be of independent interest.

Matrices of fidelities for ensembles of quantum states and the Holevo quantity (pp0472-0489)
Mark Fannes, Fernando de Melo, Wojciech Roga, and Karol Zyczkowski

The entropy of the Gram matrix of a joint purification of an ensemble of $K$ mixed states yields an upper bound for the Holevo information $\chi$ of the ensemble. In this work we combine geometrical and probabilistic aspects of the ensemble in order to obtain meaningful bounds for $\chi$. This is done by constructing various correlation matrices involving fidelities between every pair of states from the ensemble. For $K=3$ quantum states we design a matrix of root fidelities that is positive and the entropy of which is conjectured to upper bound $\chi$. Slightly weaker bounds are established for arbitrary ensembles. Finally, we investigate correlation matrices involving multi-state correlations in relation to the Holevo quantity.

Semi-loss-tolerant strong coin flipping protocol using EPR pairs (pp0490-0501)
Jia-Jun Ma, Fen-Zhuo Guo, Qian Yang, Yan-Bing Li, and Qiao-Yan Wen
In this paper, we present a quantum strong coin flipping protocol. In this protocol, an EPR pair and a quantum memory storage are made use of, and losses in the quantum communication channel and quantum memory storage are all analyzed. We obtain the bias in the fair scenario as a function of $p$, where $p$ is the probability that the particle in Bob's quantum memory storage is lost, which means our bias varies as the degree of losses in the quantum memory storage changes. Therefore we call our protocol semi-loss-tolerant. We also show that the bias decreases with decreasing $p$. When $p$ approaches $0$, the bias approaches 0.3536, which is less than that of all the previous loss-tolerant protocols. Details of both parties' optimal cheating strategies are also given and analyzed. What's more, experimental feasibility is discussed and demonstrated. Compared with previous qubit-based loss-tolerant SCF protocols, we introduce the EPR pair to keep our protocol loss-tolerant while trying to push down the bias. In addition, a quantum memory storage is used and the losses in it has been taken into account. We obtain the bias in the fair scenario as a function of $p$, where $p$ is the probability that the particle in Bob's quantum memory storage is lost, which means our bias varies as the degree of losses in the quantum memory storage changes. We also show that the bias decreases with decreasing $p$. When $p$ approaches $0$, the bias approaches 0.3536, which is less than that of all the previous loss-tolerant protocols. Details of both parties' optimal cheating strategies are also given and analyzed. Besides, experimental feasibility is discussed and demonstrated.

Distribution of entanglement in networks of bi-partite full-rank mixed states (pp0502-0534)
G John Lapeyre Jr., Sébastien Perseguers, Maciej Lewenstein, and Antonio Acín
We study quantum entanglement distribution on networks with full-rank bi-partite mixed states linking qubits on nodes. In particular, we use entanglement swapping and purification to partially entangle widely separated nodes. The simplest method consists of performing entanglement swappings along the shortest chain of links connecting the two nodes. However, we show that this method may be improved upon by choosing a protocol with a specific ordering of swappings and purifications. A priori, the design that produces optimal improvement is not clear. However, we parameterize the choices and find that the optimal values depend strongly on the desired measure of improvement. As an initial application, we apply the new improved protocols to the Erd\"os--R\'enyi network and obtain results including low density limits and an exact calculation of the average entanglement gained at the critical point.

back to QIC online Front page