QIC Abstracts

 Vol.9 No.9&10 September 1, 2009

Review Article:

Topological cluster state quantum computing (pp0721-0738)
A.G. Fowler and K. Goyal
The quantum computing scheme described by 
Raussendorf et. al (2007), when viewed as a cluster state computation, features a 3-D cluster state, novel adjustable strength error correction capable of correcting general errors through the correction of Z errors only, a threshold error rate approaching 1% and low overhead arbitrarily long-range logical gates. In this work, we review the scheme in detail framing the discussion solely in terms of the required 3-D cluster state and its stabilizers.

Research Articles:

 Properties of local quantum operations with shared entanglement (pp0739-0764)
G. Gutoski
Multi-party local quantum operations with shared quantum entanglement or shared classical randomness are studied. The following facts are established:
* There is a ball of local operations with shared randomness lying within the space spanned by the no-signaling operations and centred at the completely noisy channel.
* The existence of the ball of local operations with shared randomness is employed to prove that the weak membership problem for local operations with shared entanglement is strongly NP-hard.
* Local operations with shared entanglement are characterized in terms of linear functionals that are "completely'' positive on a certain cone K of separable Hermitian operators, under a natural notion of complete positivity appropriate to that cone. Local operations with shared randomness (but not entanglement) are also characterized in terms of linear functionals that are merely positive on that same cone K.
* Existing characterizations of no-signaling operations are generalized to the multi-party setting and recast in terms of the Choi-Jamio\l kowski representation for quantum super-operators.
It is noted that the standard nonlocal box is an example of a no-signaling operation that is separable, yet cannot be implemented by local operations with shared entanglement.

Security of quantum secret sharing with two-particle entanglement against individual attacks (pp0765-0772)
S.-J. Qin, F. Gao, Q.-Y. Wen, and F.-C. Zhu
Security is the most important criterion to evaluate cryptography protocols. We investigate the security of one important quantum secret sharing protocol (KKI protocol). By discriminating two mixed states, we derive the optimal relationship between the induced error rate (QBER) and the maximal amount of information gained by a dishonest participant. For a specific amount of eavesdropper's knowledge on the shared secret that we consider, the disturbance on the quantum state in terms of QBER is actually larger for the hybrid protocol than the KKI protocol. Therefore, the hybrid protocol appears to be better able to detect eavesdroppers than the KKI protocol. For this reason, we do not see any reason to employ the KKI protocol against individual attacks.

Exact universality from any entangling gate without inverses (pp0773-0777)
A.W. Harrow
This note proves that arbitrary local gates together with any entangling bipartite gate V are universal. Previously this was known only when access to both V and V^\dag was given, or when approximate universality was demanded.

SLOCC classification for nine families of four-qubits (pp0778-0800)
D.-F. Li, X.-R. Li, H.-T. Huang, and X.-X. Li
In 2000, D\"{u}r, Vidal and Cirac indicated that there are infinitely many SLOCC classes for four qubits. Later, Verstraete, Dehaene, and Verschelde proposed nine families of states corresponding to nine different ways of entangling four qubits. And then in 2007 Lamata et al. reported that there are eight true SLOCC entanglement classes of four qubits up to permutations of the qubits. In this paper, we investigate SLOCC classification of the nine families proposed by Verstraete, Dehaene and Verschelde, and distinguish 49 true SLOCC entanglement classes from them.

Relaxed uncertainty relations and information processing (pp0801-0832)
G. Ver Steeg and S. Wehner
We consider a range of "theories'' that violate the uncertainty relation for anti-commuting observables derived. We first show that Tsirelson's bound for the CHSH inequality can be derived from this uncertainty relation, and that relaxing this relation allows for non-local correlations that are stronger than what can be obtained in quantum mechanics. We continue to construct a hierarchy of related non-signaling theories, and show that on one hand they admit superstrong random access encodings and exponential savings for a particular communication problem, while on the other hand it becomes much harder in these theories to learn a state. We show that the existence of these effects stems from the absence of certain constraints on the expectation values of commuting measurements from our non-signaling theories that are present in quantum theory.

Eigenpath traversal by phase randomization (pp0833-0855)
S. Boixo, E. Knill, and R. Somma
A computation in adiabatic quantum computing is implemented by traversing a path of nondegenerate eigenstates of a continuous family of Hamiltonians. We introduce a method that traverses a discretized form of the path: At each step we apply the instantaneous Hamiltonian for a random time. The resulting decoherence approximates a projective measurement onto the desired eigenstate, achieving a version of the quantum Zeno effect. If negative evolution times can be implemented with constant overhead, then the average absolute evolution time required by our method is $\cO(L^{2} /\Delta)$ for constant error probability, where $L$ is the length of the path of eigenstates and $\Delta$ is the minimum spectral gap of the Hamiltonian. The dependence of the cost on
$\Delta$ is optimal. Making explicit the dependence on the path length is useful for cases where $L$ is much less than the general bound. The complexity of our method has a logarithmic improvement over previous algorithms of this type. The same cost applies to the discrete-time case, where a family of unitary operators is given and each unitary and its inverse can be used. Restriction to positive evolution times incurs an error that decreases exponentially with the cost. Applications of this method to unstructured search and quantum sampling are considered. In particular, we discuss the quantum simulated annealing algorithm for solving combinatorial optimization problems. This algorithm provides a quadratic speed-up in the gap of the stochastic matrix over its classical counterpart implemented via Markov chain Monte Carlo.

Complete characterization of mixing time for the continuous quantum walk on the hypercube with Markovian decoherence model (pp0856-0878)
M. Drezgich, A.P. Hines, M. Sarovar, and S. Sastry
The n-dimensional hypercube quantum random walk (QRW) is a particularily appealing example of a quantum walk because it has a natural implementation on a register on n qubits. However, any real implementation will encounter decoherence effects due to interactions with uncontrollable degrees of freedom. We present a complete characterization of the mixing properties of the hypercube QRW under a physically relevant Markovian decoherence model. In the local decoherence model considered the non-unitary dynamics are modeled as a sum of projections on individual qubits to an arbitrary direction on the Bloch sphere. We prove that there is always classical (asymptotic) mixing in this model and specify the conditions under which instantaneous mixing always exists. And we show that the latter mixing property, as well as the classical mixing time, depend heavily on the exact environmental interaction and its strength. Therefore, algorithmic applications of the QRW on the hypercube, if they intend to employ mixing properties, need to consider both the walk dynamics and the precise decoherence model.

New approach to quantum key distribution via quantum encryption (pp0879-0898)
A. Fahmi
Recently, Zhang, Li and Guo (ZLG) suggested a new approach to quantum key distribution by using a shared Bell state which acts as quantum key in order to encode and decode classical information. Subsequently, others extended ZLG protocol to d-dimensional systems and to quantum secret sharing based on reusable GHZ states. However, Gao et al. have shown that if Eve employs a special strategy to attack, these protocols become insecure. Afterwards, they repair ZLG protocol so that their eavesdropping strategy becomes inefficient. In this paper, we investigate the security of ZLG quantum key distribution protocol and show that it is not secure against Eve's attacks and with probability of one half she gets all of the keys without being detected by the two parties. In this eavesdropping strategy, Eve transforms the previously shared Bell state between Alice and Bob to two Bell states among herself and the parties. Moreover, we briefly show that ZLG's repairing by Gao et al's is not efficient against of our attack and Eve can choose an appropriate rotation angle and measurement bases which help her to do eavesdropping. Afterwards, we discuss generalization of ZLG protocol to d-dimensional systems and show that with probability 1/d, Eve gets all of keys. We show that quantum secret sharing based on reusable GHZ states is also not secure and with probability one half, Eve gets all of keys. We repair them by going to higher dimensional shared EPR or GHZ states. Finally, we compare ZLG protocol with ours and show that the ZLG protocol and its extensions are less robust against the channel noise with respect to ours.

back to QIC online Front page