QIC Abstracts

 Vol.13 No.9&10, September 1, 2013

Research Articles:

The local Hamiltonian problem on a line with eight staes is QMA-complete (pp0721-0750)
Sean Hallgren, Daniel Nagaj, and Sandeep Narayanaswami
The Local Hamiltonian problem is the problem of estimating the least eigenvalue of a local Hamiltonian, and is complete for the class QMA. The 1D problem on a chain of qubits has heuristics which work well, while the 13-state qudit case has been shown to be QMA-complete. We show that this problem remains QMA-complete when the dimensionality of the qudits is brought down to 8.

Entanglement distillation by extendible maps (pp0751-0770)
Lukasz Pankowski, Fernando G.S.L. Brandao, Michal Horodecki, and Graeme Smith
It is known that from entangled states that have positive partial transpose it is not possible to distill maximally entangled states by local operations and classical communication (LOCC). A long-standing open question is whether maximally entangled states can be distilled from every state with a non-positive partial transpose. In this paper we study a possible approach to the question consisting of enlarging the class of operations allowed. Namely, instead of LOCC operations we consider $k$-extendible operations, defined as maps whose Choi-Jamio\l{}kowski  state is $k$-extendible. We find that this class is unexpectedly powerful - e.g. it is capable of distilling EPR pairs even from completely product states. We also perform numerical studies of distillation of Werner states by those maps, which show that if we raise the extension index $k$ simultaneously with the number of copies of the state, then the class of $k$-extendible operations are not that powerful anymore and provide a better approximation to the set of LOCC operations.

Reversible logic synthesis by quantum rotation gates (pp0771-0792)
Afshin Abdollahi, Mehdi Saeedi, and Massoud Pedram
A rotation-based synthesis framework for reversible logic is proposed. We develop a canonical representation based on binary decision diagrams and introduce operators to manipulate the developed representation model. Furthermore, a recursive functional bi-decomposition approach is proposed to automatically synthesize a given function. While Boolean reversible logic is particularly addressed, our framework constructs intermediate quantum states that may be in superposition, hence we combine techniques from reversible Boolean logic and quantum computation. {The proposed approach results in quadratic gate count for multiple-control Toffoli gates without ancillae, linear depth for quantum carry-ripple adder, and $O(n\log^2 n)$ size for quantum multiplexer.

Upper bounds on the rate of low density stabilizer codes for the quantum erasure channel (pp0793-0826)
Nicolas Delfosse and Gilles Zemor
Using combinatorial arguments, we determine an upper bound on achievable rates of stabilizer codes used over the quantum erasure channel. This allows us to recover the no-cloning bound on the capacity of the quantum erasure channel, $R \leq 1-2p$, for stabilizer codes: we also derive an improved upper bound of the form $R \leq 1-2p-D(p)$ with a function $D(p)$ that stays positive for $0<p<1/2$ and for any family of stabilizer codes whose generators have weights bounded from above by a constant -- low density stabilizer codes. We obtain an application to percolation theory for a family of self-dual tilings of the hyperbolic plane. We associate a family of low density stabilizer codes with appropriate finite quotients of these tilings. We then relate the probability of percolation to the probability of a decoding error for these codes on the quantum erasure channel. The application of our upper bound on achievable rates of low density stabilizer codes gives rise to an upper bound on the critical probability for these tilings.

A study of BB84 protocol in a device-independent scenario: from the view of entanglement distillation (pp0827-0832)
Zhen-Qiang Yin, Wei Chen, Shuang Wang, Hong-Wei Li, Guang-Can Guo, and Zheng-Fu Han
For the past few years, the security of practical quantum key distribution systems has attracted a lot of attention. Device-independent quantum key distribution was proposed to design a real-life secure quantum key distribution system with imperfect and untrusted quantum devices. In this paper, we analyzed the security of BB84 protocol in a device-independent scenario based on the entanglement distillation method. Since most of the reported loopholes are in receivers of quantum key distribution systems, we focus on condition that the transmitter of the system is perfectly coincident with the requirement of the BB84 protocol, while the receiver can be controlled by eavesdropper. Finally, the lower bound of the final secret-key rate was proposed and we explained why the secure-key rate is similar to the well-known result for the original entanglement distillation protocol.

Pseudo-telepathy games using graph states (pp0833-0845)
Anurag Anshu and Mehdi Mhalla
We define a family of pseudo-telepathy games using graph states that extends the Mermin games. This family also contains a game used to define a quantum probability distribution that cannot be simulated by any number of nonlocal boxes. We extend this result, proving that the probability distribution obtained by the Paley graph state on 13 vertices (each vertex corresponds to a player) cannot be simulated by any number of 4-partite nonlocal boxes and that the Paley graph states on $k^{2}2^{2k-2}$ vertices provide a probability distribution that cannot be simulated by $k$-partite nonlocal boxes, for any $k$.

Full characterization of quantum correlated equilibria (pp0846-0860)
Zhaohui Wei and Shengyu Zhang
Quantum game theory aims to study interactions of people (or other agents) using quantum devices with possibly conflicting interests. Recently Zhang studied some quantitative questions in general quantum strategic games of growing sizes~\cite{Zha12}. However, a fundamental question not addressed there is the characterization of quantum correlated equilibria (QCE). In this paper, we answer this question by giving a sufficient and necessary condition for an arbitrary state $\rho$ being a QCE. In addition, when the condition fails to hold for some player $i$, we give an explicit positive-operator valued measurement (POVM) for that player to achieve a strictly positive gain of payoff. Finally, we give some upper bounds for the maximum gain by playing quantum strategies over classical ones, and the bounds are tight for some games.

Security of plug-and-play QKD arrangements with finite resources (pp0861-0879)
Pedro J. Salas
The security of a passive plug-and-play QKD arrangement in the case of finite (resources) key lengths is analysed. It is assumed that the eavesdropper has full access to the channel so an unknown and untrusted source is assumed. To take into account the security of the BB84 protocol under collective attacks within the framework of quantum adversaries, a full treatment provides the well-known equations for the secure key rate. A numerical simulation keeping a minimum number of initial parameters constant as the total error sought and the number of pulses is carried out. The remaining parameters are optimized to produce the maximum secure key rate. Two main strategies are addressed: with and without two-decoy-states including the optimization of signal to decoy relationship.

Optimal asymmetric quantum cloning for quantum information and computation (pp0880-0900)
Alastair Kay, Ravishankar Ramanathan, and Dagomir Kaszlikowski
While the no-cloning theorem, which forbids the perfect copying of quantum states, is well-known as one of the defining features of quantum mechanics, the question of how well the theory allows a state to be cloned is yet to be completely solved. In this paper, rigorous solutions to the problem of $M\rightarrow N$ asymmetric cloning of qudits are obtained in a number of interesting cases. The central result is the solution to the $1 \rightarrow N$ universal asymmetric qudit cloning problem for which the exact trade-off in the fidelities of the clones for every $N$ and $d$ is derived. Analogous results are proven for qubits when $M=N-1$. We also consider state-dependent $1 \rightarrow N$ qubit cloning, providing a general parametrization in terms of a Heisenberg star Hamiltonian. In all instances, we determine the feasibility of implementing the cloning economically, i.e., without an ancilla, and determine the dimension of the ancilla when an economic implementation is not possible.

back to QIC online Front page