QIC Abstracts

 Vol.14 No.15&16, November 1, 2014

Research Articles:

An algorithm for the T-countAn algorithm for the T-count (pp1261-1276)
          
David Gosset, Vadym Kliuchnikov, Michele Mosca, and Vincent Russo

We consider quantum circuits composed of Clifford and $T$ gates. In this context the $T$ gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an $n$-qubit unitary $U$ we are interested in computing a circuit that implements it using the minimum possible number of $T$ gates (called the $T$-count of $U$). A related task is to decide if the $T$-count of $U$ is less than or equal to $m$; we consider this problem as a function of $N=2^n$ and $m$. We provide a classical algorithm which solves it using time and space both upper bounded as $\mathcal{O}(N^m \text{poly}(m,N))$. We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 $T$ gates. This implies that the known 7 $T$ gate circuits for these gates are $T$-optimal. We also provide a simple expression for the $T$-count of single-qubit unitaries.

Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries (pp1277-1301)
          
Adam Paetznick and Krysta M. Svore
We present a decomposition technique that uses non-deterministic circuits to approximate an arbitrary single-qubit unitary to within distance $\epsilon$ and requires significantly fewer non-Clifford gates than existing techniques. We develop ``Repeat-Until-Success" (RUS) circuits and characterize unitaries that can be exactly represented as an RUS circuit. Our RUS circuits operate by conditioning on a given measurement outcome and using only a small number of non-Clifford gates and ancilla qubits. We construct an algorithm based on RUS circuits that approximates an arbitrary single-qubit $Z$-axis rotation to within distance $\epsilon$, where the number of $T$ gates scales as $1.26\log_2(1/\epsilon) - 3.53$, an improvement of roughly three-fold over state-of-the-art techniques. We then extend our algorithm and show that a scaling of $2.4\log_2(1/\epsilon) - 3.28$ can be achieved for arbitrary unitaries and a small range of $\epsilon$, which is roughly twice as good as optimal deterministic decomposition methods.

Strong equivalence of reversible circuits is coNP-complete (pp1302-1307)
          
Stephen P. Jordan

It is well-known that deciding equivalence of logic circuits is a coNP-complete problem. As a corollary, the problem of deciding weak equivalence of reversible circuits, \emph{i.e.} allowing initialized ancilla bits in the input and ignoring ``garbage'' ancilla bits in the output, is also coNP-complete. The complexity of deciding strong equivalence, including the ancilla bits, is less obvious and may depend on gate set. Here we use Barrington's theorem to show that deciding strong equivalence of reversible circuits built from the Fredkin gate is coNP-complete. This implies coNP-completeness of deciding strong equivalence for other commonly used universal reversible gate sets, including any gate set that includes the Toffoli or Fredkin gate.

Separability for weakly irreducible matrices (pp1308-1337)
          
Daniel Cariello
This paper is devoted to the study of the separability problem in the field of Quantum information theory. We focus on the bipartite finite dimensional case and on two types of matrices: SPC and PPT matrices (see definitions 32 and 33). We prove that many results hold for both types. If these matrices have specific Hermitian Schmidt decompositions then they are separable in a very strong sense (see theorem 38 and corollary 39). We prove that both types have what we call \textbf{split decompositions} (see theorems 41 and 42). We also define the notion of weakly irreducible matrix (see definition 43), based on the concept of irreducible state defined recently in \cite{chen1}, \cite{chen} and \cite{chen2}.}{These split decomposition theorems imply that every SPC $($PPT$)$ matrix can be decomposed into a sum of $s+1$ SPC $($PPT$)$ matrices of which the first $s$ are weakly irreducible, by theorem 48, and the last one has a further split decomposition of lower tensor rank, by corollary 49. Thus the SPC $($PPT$)$ matrix is decomposed in a finite number of steps into a sum of weakly irreducible matrices. Different components of this sum have support on orthogonal local Hilbert spaces, therefore the matrix is separable if and only if each component is separable. This reduces the separability problem for SPC $($PPT$)$ matrices to the case of weakly irreducible SPC $($PPT$)$ matrices. We also provide a complete description of weakly irreducible matrices of both types (see theorem 46).}{Using the fact that every positive semidefinite Hermitian matrix with tensor rank 2 is separable (see theorem 58), we found sharp inequalites providing separability for both types (see theorems 61 and 62).

Fault-Tolerant quantum computation with constant overhead (pp1338-1371)
          
Daniel Gottesman
What is the minimum number of extra qubits needed to perform a large fault-tolerant quantum circuit? Working in a common model of fault-tolerance, I show that in the asymptotic limit of large circuits, the ratio of physical qubits to logical qubits can be a constant. The construction makes use of quantum low-density parity check codes, and the asymptotic overhead of the protocol is equal to that of the family of quantum error-correcting codes underlying the fault-tolerant protocol.

Generation of quantum correlation in quantum dots by Lyapunov control methods (pp1372-1382)
          
Da-Wei Luo and Jing-Bo Xu
We present a scheme to generate steady-state quantum correlations in quantum dots. The shape of the control field is obtained by using the Lyapunov control method, and the controlled state is found to approach the target state monotonically. We also explore the possibility of replacing the continuous control field with a train of discreet rectangular pulses, which is much easier to implement experimentally. The discretized control field is found to be still able to drive the initial state to the target state with very small errors, which suggests that the Lyapunov based control is still effective under practical limitations.

BosonSampling is far from uniform (pp1383-1423)
          
Scott Aaronson and Alex Arkhipov
BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. \ In a recent manuscript, Gogolin et al.\ claimed that even an ideal BosonSampling device's output would be operationally indistinguishable\textquotedblright\ from a uniform random outcome, at least \textquotedblleft without detailed a priori knowledge; or at any rate, that telling the two apart might itself be a hard problem. We first answer these claims---explaining why the first is based on a definition of a priori knowledge such that, were it adopted, almost no quantum algorithm could be distinguished from a pure random-number source; while the second is neither new nor a practical obstacle to interesting BosonSampling experiments.However, we then go further, and address some interesting research questions inspired by Gogolin et al.'s arguments. We prove that, with high probability over a Haar-random matrix $A$, the BosonSampling distribution induced by $A$ is far from the uniform distribution in total variation distance. More surprisingly, and counter to Gogolin et al., we give an efficient algorithm that distinguishes these two distributions with constant bias. Finally, we offer three bonus results about BosonSampling. First, we report an observation of Fernando Brandao: that one can efficiently sample a distribution that has large entropy and that's indistinguishable from a BosonSampling distribution by any circuit of fixed polynomial size. Second,
we show that BosonSampling distributions can be efficiently distinguished from uniform even with photon losses and for general initial states. Third, we offer the simplest known proof that Fermion Sampling is solvable in classical polynomial time, and we reuse techniques from our Boson Sampling analysis to characterize random FermionSampling distributions.

Families of codes of topological quantum codes from tessellations tessellations {4i+2,2i+1}, {4i,4i}, {8i-4,4} and ${12i-6,3} (pp1424-1440)
          
Clarice Dias de Albuquerque, Reginaldo Palazzo Jr., and Eduardo Brandani da Silva
In this paper we present some classes of topological quantum codes on surfaces with genus $g \geq 2$ derived from hyperbolic tessellations with a specific property. We find classes of codes with distance $d = 3$ and encoding rates asymptotically going to 1, $\frac{1}{2}$ and $\frac{1}{3}$, depending on the considered tessellation. Furthermore, these codes are associated with embedding of complete bipartite graphs. We also analyze the parameters of these codes, mainly its distance, in addition to show a class of codes with distance 4. We also present a class of codes achieving the quantum Singleton bound, possibly the only one existing under this construction.


back to QIC online Front page