QIC Abstracts

 Vol.15 No.5&6, April 1, 2015

Research Articles:

The Trotter step size required for accurate quantum simulation of quantum chemistry 361 (pp0361-0384)
          
David Poulin, M. B. Hastings, D. Wecker, N. Wiebe, Andrew C. Doberty, and M. Troyer
The simulation of molecules is a widely anticipated application of quantum computers. However, recent studies \cite{WBCH13a,HWBT14a} have cast a shadow on this hope by revealing that the complexity in gate count of such simulations increases with the number of spin orbitals $N$ as $N^8$, which becomes prohibitive even for molecules of modest size $N\sim 100$. This study was partly based on a scaling analysis of the Trotter step required for an ensemble of random artificial molecules. Here, we revisit this analysis and find instead that the scaling is closer to $N^6$ in worst case for real model molecules we have studied, indicating that the random ensemble fails to accurately capture the statistical properties of real-world molecules. Actual scaling may be significantly better than this due to averaging effects. We then present an alternative simulation scheme and show that it can sometimes outperform existing schemes, but that this possibility depends crucially on the details of the simulated molecule. We obtain further improvements using a version of the coalescing scheme of \cite{WBCH13a}; this scheme is based on using different Trotter steps for different terms. The method we use to bound the complexity of simulating a given molecule is efficient, in contrast to the approach of \cite{WBCH13a,HWBT14a} which relied on exponentially costly classical exact simulation.

Some classes of concatenated quantum codes: constructions and lower bounds (pp0385-0405)
          
Hachiro Fujita
In classical coding theory code concatenation is successfully used to construct good error-correcting codes and most of the asymptotically good codes known so far are based on concatenation. In this paper we present some classes of asymptotically good concatenated quantum codes, which are a quantum analogue of classical concatenated codes, and derive lower bounds on the minimum distance and the rate of the codes. Our bounds improve on the best lower bound of Ashikhmin--Litsyn--Tsfasman and Matsumoto for rates smaller than about one half. We also give a polynomial-time decoding algorithm for the codes that can decode up to one fourth of the lower bound on the minimum distance of the codes.

Limit theorems of a 3-state quantum walk and its application for discrete uniform measures (pp0406-0418)
          
Takuya Machida
We present two long-time limit theorems of a 3-state quantum walk on the line when the walker starts from the origin. One is a limit measure which is obtained from the probability distribution of the walk at a long-time limit, and the other is a convergence in distribution for the walker's position in a rescaled space by time. In addition, as an application of the walk, we obtain discrete uniform limit measures from the 3-state walk with a delocalized initial state.

High performance information reconciliation for QKD with CASCADE (pp0419-0434)
          
Thomas Brochmann Pedersen and Mustafa Toyran
 It is widely accepted in the quantum cryptography community that interactive information reconciliation protocols, such as \cascade{}, are inefficient due to the communication overhead. Instead, non-interactive information reconciliation protocols based on i.e. LDPC codes or, more recently, polar codes have been proposed. In this work, we argue that interactive protocols should be taken into consideration in modern quantum key distribution systems. In particular, we demonstrate how to improve the performance of \cascade{} by proper implementation and use. Our implementation of \cascade{} reaches a throughput above 80~Mbps under realistic conditions. This is more than twice the throughput previously demonstrated in any information reconciliation protocol.

Exact quantum algorithms have advantage for almost all Boolean functions (pp0435-0452)
          
Andris Ambainis, Jozef Gruska, and Shenggen Zheng
It has been proved that almost all $n$-bit Boolean functions have exact classical query complexity} $n$. However, the situation seemed to be very different when we deal with  exact quantum query complexity. In this paper, we prove that almost all $n$-bit Boolean functions can be computed by an exact quantum algorithm with less than $n$ queries. More exactly, we prove that $\mbox{AND}_n$ is the only $n$-bit Boolean function, up to isomorphism, that requires $n$ queries.

Demystifying the information reconciliation protocol cascade (pp0453-0477)
          
Jesus Martinez-Mateo, Christoph Pacher, Momtchil Peev, Alex Ciurana, and Vicente Martin
\Cascade is an information reconciliation protocol proposed in the context of secret key agreement in quantum cryptography. This protocol allows removing discrepancies in two partially correlated sequences that belong to distant parties, connected through a public noiseless channel. It is highly interactive, thus requiring a large number of channel communications between the parties to proceed and, although its efficiency is not optimal, it has become the de-facto standard for practical implementations of information reconciliation in quantum key distribution. The aim of this work is to analyze the performance of \Cascade, to discuss its strengths, weaknesses and optimization possibilities, comparing with some of the modified versions that have been proposed in the literature. When looking at all design trade-offs, a new view emerges that allows to put forward a number of guidelines and propose near optimal parameters for the practical implementation of \Cascade improving performance significantly in comparison with all previous proposals.

Indecomposability of entanglement witnesses (pp0478-0488)
          
Xiao-Fei Qi and Jin-Chuan Hou
We present a way to construct indecomposable entanglement witnesses from any permutation $\pi$ with $\pi^2\not=$id for any finite dimensional bipartite systems. Some new bounded entangled states are also found, which can be detected by such witnesses while cannot be distinguished by PPT criterion, realignment criterion, etc.

Analysis of circuit imperfections in BosonSampling (pp0489-0512)
          
Anthony Leverrier, Raul Garcia-Patron
BosonSampling is a problem where a quantum computer offers a provable speedup over classical computers. Its main feature is that it can be solved with current linear optics technology, without the need for a full quantum computer. In this work, we investigate whether an experimentally realistic BosonSampler can really solve BosonSampling without any fault-tolerance mechanism. More precisely, we study how the unavoidable errors linked to an imperfect calibration of the optical elements affect the final result of the computation. We show that the fidelity of each optical element must be at least $1 - O(1/n^2)$, where $n$ refers to the number of single photons in the scheme. Such a requirement seems to be achievable with state-of-the-art equipment.

Locally restricted measurements on a multipartite quantum system: data hiding is generic  (pp0513-0540)
          
Guillaume Aubrun and Cecilia Lancien
We study the distinguishability norms associated to families of locally restricted POVMs on multipartite systems. These norms (introduced by Matthews, Wehner and Winter) quantify how quantum measurements, subject to locality constraints, perform in the task of discriminating two multipartite quantum states. We mainly address the following question regarding the behaviour of these distinguishability norms in the high-dimensional regime: On a bipartite space, what are the relative strengths of standard classes of locally restricted measurements? We show that the class of PPT measurements typically performs almost as well as the class of all measurements whereas restricting to local measurements and classical communication, or even just to separable measurements, implies a substantial loss. We also provide examples of state pairs which can be perfectly distinguished by local measurements if (one-way) classical communication is allowed between the parties, but very poorly without it. Finally, we study how many POVMs are needed to distinguish almost perfectly any pair of states on ${\mathbf{C}}^d$, showing that the answer is $\exp(\Theta(d^2))$.

back to QIC online Front page