QIC Abstracts

 Vol.10 No.1&2 January 1, 2010

Research Articles:

Random quantum satisfiability (pp0001-0015)
C.R. Laumann, R. Moessner, A. Scarddichio, and S.L. Sondhi
Alongside the effort underway to build quantum computers, it is important to better understand which classes of problems they will find easy and which others even they will find intractable. We study random ensembles of the QMA$_1$-complete quantum satisfiability (QSAT) problem introduced by Bravyi \cite{Bravyi:2006p4315}. QSAT appropriately generalizes the NP-complete classical satisfiability (SAT) problem. We show that, as the density of clauses/projectors is varied, the ensembles exhibit quantum phase transitions between phases that are satisfiable and unsatisfiable. Remarkably, almost all instances of QSAT for \emph{any} hypergraph exhibit the same dimension of the satisfying manifold. This establishes the QSAT decision problem as equivalent to a, potentially new, graph theoretic problem and that the hardest typical instances are likely to be localized in a bounded range of clause density.

Efficient universal quantum circuits (pp0016-0027)
D. Bera, S. Fenner, F. Green, and S. Homer
Universal circuits can be viewed as general-purpose simulators for central classes of circuits and can be used to capture the computational power of the circuit class being simulated. We define and construct quantum universal circuits which are efficient and has very little overhead in simulation. For depth we construct universal circuits whose depth is the same order as the circuits being simulated. For size, there is a log factor blow-up in the universal circuits constructed here which is nearly optimal.

Single qubit quantum secret sharing with improved security (pp0028-0040)
          G.P. He and Z.D. Wang
Analyzing carefully an experimentally feasible non-entangled single qubit quantum secret sharing protocol and its modified version [Phys. Rev. Lett. 95, 230505 (2005); \textit{ibid}. 98, 028902 (2007)], it is found that both versions are insecure against coherent attacks though the original idea is so remarkable. To overcome this fatal flaw, here we propose a protocol with a distinct security checking strategy, which still involves single qubit operations only, making it possible to achieve better security of quantum secret sharing with current technology.

C_3, semi-Clifford and genralized semi-Clifford operations (pp0041-0059)
S. Beigi and P.W. Shor
Fault-tolerant quantum computation is a basic problem in quantum computation, and teleportation is one of the main techniques in this theory. Using teleportation on stabilizer codes, the most well-known quantum codes, Pauli gates and Clifford operators can be applied fault-tolerantly. Indeed, this technique can be generalized for an extended set of gates, the so called ${\mathcal{C}}_k$ hierarchy gates, introduced by Gottesman and Chuang (Nature, 402, 390-392). ${\mathcal{C}}_k$ gates are a generalization of Clifford operators, but our knowledge of these sets is not as rich as our knowledge of Clifford gates. Zeng et al. in (Phys. Rev. A 77, 042313) raise the question of the relation between ${\mathcal{C}}_k$ hierarchy and the set of semi-Clifford and generalized semi-Clifford operators. They conjecture that any ${\mathcal{C}}_k$ gate is a generalized semi-Clifford operator. In this paper, we prove this conjecture for $k=3$. Using the techniques that we develop, we obtain more insight on how to characterize ${\mathcal{C}}_3$ gates. Indeed, the more we understand ${\mathcal{C}}_3$, the more intuition we have on ${\mathcal{C}}_k$, $k\geq 4$, and then we have a way of attacking the conjecture for larger $k$.

Security of quantum key distribution with bit and basis dependent detector flaws (pp0060-0076)
L. Lydersen and J. Skaar
We consider the security of the Bennett-Brassard 1984 (BB84) protocol for Quantum Key Distribution (QKD), in the presence of bit and basis dependent detector flaws. We suggest a powerful attack that can be used in systems with detector efficiency mismatch, even if the detector assignments are chosen randomly by Bob. A security proof is provided, valid for any basis dependent, possibly lossy, linear optical imperfections in the channel/receiver/detectors. The proof does not assume the so-called squashing detector model.

On the complexity of approximating the diamond norm (pp0077-0086)
A. Ben-Aroya and A. Ta-Shma
The diamond norm is a norm defined over the space of quantum transformations. This norm has a natural operational interpretation: it measures how well one can distinguish between two transformations by applying them to a state of arbitrarily large dimension. This interpretation makes this norm useful in the study of quantum interactive proof systems. In this note we exhibit an efficient algorithm for computing this norm using convex programming. Independently of us, Watrous recently showed a different algorithm to compute this norm. An immediate corollary of this algorithm is a slight simplification of the argument of Kitaev and Watrous that QIP \subseteq \EXP.

Quantum universality by state distillationIndirect quantum control for finite-dimensional coupled systems (pp0087-0096)
J. Nie, H.C. Fu, and X.X. Yi
We present a new analysis on the quantum control for a quantum system coupled to a quantum probe. This analysis is based on the coherent control for the quantum system and a hypothesis that the probe can be prepared in specified initial states. The results show that a quantum system can be manipulated by probe state-dependent coherent control. In this sense, the present analysis provides a new control scheme which combines the coherent control and state preparation technology.

The LU-LC conjecture is false (pp0097-0108)
Z.-F. Ji, J.-X. Chen, Z.-H. Wei, and M.-S. :Ying
The LU-LC conjecture is an important open problem concerning the structure of entanglement of states described in the stabilizer formalism. It states that two local unitary equivalent stabilizer states are also local Clifford equivalent. If this conjecture were true, the local equivalence of stabilizer states would be extremely easy to characterize. Unfortunately, however, based on the recent progress made by Gross and Van den Nest, we find that the conjecture is false.

The role of symmetries in adiabatic quantum algorithms (pp0109-0140)
G. Schaller and R. Schutzhold
Exploiting the similarity between adiabatic quantum algorithms and quantum phase transitions, we argue that second-order transitions -- typically associated with broken or restored symmetries -- should be advantageous in comparison to first-order transitions.
Guided by simple examples we construct an alternative adiabatic algorithm for the NP-complete problem {\em Exact Cover 3}. We show numerically that its average performance (for the considered cases up to $\ord\{20\}$ qubits) is better than that of the conventional scheme. The run-time of adiabatic algorithms is not just determined by the minimum value of the fundamental energy gap (between the ground state and the exited states), but also by its curvature at the critical point. The proposed symmetry-restoring adiabatic quantum algorithm only contains contributions linear and quadratic in the Pauli matrices and can be generalized to other problem Hamiltonians which are decomposed of terms involving one and two qubits. We show how the factoring problem can be cast into such a quadratic form. These findings suggest that adiabatic quantum algorithms can solve a large class of NP problems much faster than the Grover search routine (which corresponds to a first-order transition and yields a quadratic enhancement only).

NP vs QMA_\log(2) (pp0141-0151)
S. Beigi
Although it is believed unlikely that $\NP$-hard problems admit efficient quantum algorithms, it has been shown that a quantum verifier can solve NP-complete problems given a "short" quantum proof; more precisely, NP\subseteq QMA_{\log}(2) where QMA_{\log}(2) denotes the class of quantum Merlin-Arthur games in which there are two unentangled provers who send two logarithmic size quantum witnesses to the verifier. The inclusion NP\subseteq QMA_{\log}(2) has been proved by Blier and Tapp by stating a quantum Merlin-Arthur protocol for 3-coloring with perfect completeness and gap 1/24n^6. Moreover, Aaronson et al. have shown the above inclusion with a constant gap by considering $\widetilde{O}(\sqrt{n})$ witnesses of logarithmic size. However, we still do not know if QMA_{\log}(2) with a constant gap contains NP. In this paper, we show that 3-SAT admits a QMA_{\log}(2) protocol with the gap 1/n^{3+\epsilon}} for every constant \epsilon>0.

A non-distillability criterion for secret correlations (pp0152-0159)
L. Masanes and A. Winter
Within entanglement theory there are criteria which certify that some quantum states cannot be distilled into pure entanglement. An example is the positive partial transposition criterion. Here we present, for the first time, the analogous thing for secret correlations. We introduce a computable criterion which certifies that a probability distribution between two honest parties and an eavesdropper cannot be (asymptotically) distilled into a secret key. The existence of non-distillable correlations with positive secrecy cost, also known as bound information, is an open question. This criterion may be the key for finding bound information. However, if it turns out that this criterion does not detect bound information, then, a very interesting consequence follows: any distribution with positive secrecy cost can increase the secrecy content of another distribution. In other words, all correlations with positive secrecy cost constitute a useful resource.

Ancilla-assisted discrimination of quantum gates (pp160-0177)
J.-X. Chen and M.-S. Ying
The intrinsic idea of superdense coding is to find as many gates as possible such that they can be perfectly discriminated. In this paper, we consider a basic scheme of discrimination of quantum gates, called ancilla-assisted discrimination, in which a set of quantum gates on a d-dimensional system are perfectly discriminated with assistance from an r-dimensional ancilla system. The main contribution of the present paper is two-fold: (1) The number of quantum gates that can be discriminated in this scheme is evaluated. We prove that any rd+1 quantum gates cannot be perfectly discriminated with assistance from the ancilla, and there exist rd quantum gates which can be perfectly discriminated with assistance from the ancilla. (2) The dimensionality of the minimal ancilla system is estimated. We prove that there exists a constant positive number c such that for any k\leq cr quantum gates, if they are d-assisted discriminable, then they are also r-assisted discriminable, and there are c^{\prime}rc^{\prime}>c different quantum gates which can be discriminated with a d-dimensional ancilla, but they cannot be discriminated if the ancilla is reduced to an r-dimensional system. Thus, the order O(r) of the number of quantum gates that can be discriminated with assistance from an r-dimensional ancilla is optimal. The results reported in this paper represent a preliminary step toward understanding the role ancilla system plays in discrimination of quantum gates as well as the power and limit of superdense coding.

back to QIC online Front page