QIC Abstracts

 Vol.15 No.11&12, September 1, 2015

Research Articles:

Quantum lower bound for inverting a permutation with advice (pp0901-0913)
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input $y$. Classically, there is a data structure of size $\tilde{O}(S)$ and an algorithm that with the help of the data structure, given $f(x)$, can invert $f$ in time $\tilde{O}(T)$, for every choice of parameters $S$, $T$, such that $S\cdot T \ge N$. We prove a quantum lower bound of $T^2\cdot S = \tilde{\Omega}(\eps N)$ for quantum algorithms that invert a random permutation $f$ on an $\eps$ fraction of inputs, where $T$ is the number of queries to $f$ and $S$ is the amount of advice. This answers an open question of De et al. We also give a $\Omega(\sqrt{N/m})$ quantum lower bound for the simpler but related Yao's box problem, which is the problem of recovering a bit $x_j$, given the ability to query an $N$-bit string $x$ at any index except the $j$-th, and also given $m$ bits of classical advice that depend on $x$ but not on $j$.

Quantum circuits for asymmetric 1 to n quantum cloning (pp0914-0922)
Xi-Jun Ren and Heng Fan
In this paper, we considered asymmetric $1\rightarrow n$ cloning circuits generalized from the asymmetric $1\rightarrow 2$ cloning circuit proposed by Bu\v{z}ek \textit{et al.} [Phys. Rev. A 56, 3446 (1997)]. The generalization is based on an information flux insight of the original cloning circuit. Specifically, the circuit separately and sequentially transfers the Z-type information and X-type information of the input state to the output copies with controlled-not gates. The initial input state of the clones defines the asymmetry among all output clones. Although the generalized circuits do not perform universally, the averaged fidelities over a uniform distribution of all possible input cloning states saturate the optimal fidelity tradeoff relations of universal asymmetric cloning.

Entanglement and swap of quantum states in two qubits (pp0923-0931)
Takaya Ikuto and Satoshi Ishizaka
Suppose that two distant parties Alice and Bob share an entangled state $\rho_{AB}$, and they want to exchange the subsystems of $\rho_{AB}$ by local operations and classical communication (LOCC). In general, this LOCC task (i.e. the LOCC transformation of $\rho_{AB} \to V\rho_{AB} V$ with $V$ being a swap operator) is impossible deterministically, but becomes possible probabilistically. In this paper, we study how the optimal probability is related to the amount of entanglement in the framework of positive partial transposed (PPT) operations, and numerically show a remarkable class of states whose probability is the smallest among every state in two quantum bits.

Optimal ancilla-free Clifford+V approximation of z-rotations (pp0932-0950)
Neil J. Ross
We describe a new efficient algorithm to approximate $z$-rotations by ancilla-free Clifford+$V$ circuits, up to a given precision $\epsilon$. Our algorithm is optimal in the presence of an oracle for integer factoring: it outputs the shortest Clifford+$V$ circuit solving the given problem instance. In the absence of such an oracle, our algorithm is still near-optimal, producing circuits of $V$\!-count $m + O(\log(\log(1/\epsilon)))$, where $m$ is the $V$\!-count of the third-to-optimal solution. A restricted version of the algorithm approximates $z$-rotations in the Pauli+$V$ gate set. Our method is based on previous work by the author and Selinger on the optimal ancilla-free approximation of $z$-rotations using Clifford+$T$ gates and on previous work by Bocharov, Gurevich, and Svore on the asymptotically optimal ancilla-free approximation of $z$-rotations using Clifford+$V$ gates.

Geometric phase carried by the observables and its application to quantum computation (pp0951-0961)
Zisheng Wang and Hui Pan
We investigate geometric phases in terms of Heisenberg equation. We find that, equivalently to Schr\"odinger picture with a memory of its motion in terms of the geometric phase factor contained in the wave function, the observales carry with the geometric message under their evolutions in the Heisenberg picture. Such an intrinsic geometric feature may be particularly useful to implement the multi-time correlation geometric quantum gate in terms of the observables, which leads to a possible reduction in experimental errors as well as gate timing. An application is discussed for nuclear-magnetic-resonance system, where the geometric quantum gate is proposed.

Reduced space-time and time costs Ising dislocation codes and arbitrary ancillas (pp0962-0986)
Matthew B. Hastings and A. Geller
We propose two distinct methods of improving quantum computing protocols based on surface codes. First, we analyze the use of dislocations instead of holes to produce logical qubits, potentially reducing spacetime volume required. Dislocations\cite{dis2,dis} induce defects which, in many respects, behave like Majorana quasi-particles. We construct circuits to implement these codes and present fault-tolerant measurement methods for these and other defects which may reduce spatial overhead. One advantage of these codes is that Hadamard gates take exactly $0$ time to implement. We numerically study the performance of these codes using a minimum weight and a greedy decoder using finite-size scaling. Second, we consider state injection of arbitrary ancillas to produce arbitrary rotations. This avoids the logarithmic (in precision) overhead in online cost required if $T$ gates are used to synthesize arbitrary rotations. While this has been considered before\cite{ancilla}, we consider also the parallel performance of this protocol. Arbitrary ancilla injection leads to a probabilistic protocol in which there is a constant chance of success on each round; we use an amortized analysis to show that even in a parallel setting this leads to only a constant factor slowdown as opposed to the logarithmic slowdown that might be expected naively.

A constructive quantum Lovasz local lemma for commuting projectors (pp0987-0996)
Or Sattath and Itai Arad
The Quantum Satisfiability problem generalizes the Boolean satisfiability problem to the quantum setting by replacing classical clauses with local projectors. The Quantum Lov\'asz Local Lemma gives a sufficient condition for a Quantum Satisfiability problem to be satisfiable~\cite{ambainis2012quantum}, by generalizing the classical Lov\'asz Local Lemma. The next natural question that arises is: can a satisfying quantum state be \emph{efficiently} found, when these conditions hold? In this work we present such an algorithm, with the additional requirement that all the projectors commute. The proof follows the information theoretic proof given by Moser's breakthrough result in the classical setting~\cite{moser2009constructiveSTOC}. Similar results were independently published in~\cite{cubitt2011constructive, cubitt2013quantum}.

Leakage suppression in the toric code (pp0997-1016)
Martin Suchara, Andrew W. Cross, Jay M. Gambetta
Quantum codes excel at correcting local noise but fail to correct leakage faults that excite qubits to states outside the computational space. Aliferis and Terhal \cite{aliferis07} have shown that an accuracy threshold exists for leakage faults using gadgets called leakage reduction units (LRUs). However, these gadgets reduce the accuracy threshold and increase overhead and experimental complexity, and these costs have not been thoroughly understood. We explore a variety of techniques for leakage-resilient, fault-tolerant error correction in topological codes. Our contributions are threefold. First, we develop a leakage model that is physically motivated and efficient to simulate. Second, we use Monte-Carlo simulations to survey several syndrome extraction circuits. Third, given the capability to perform 3-outcome measurements, we present a dramatically improved syndrome processing algorithm. Our simulations show that simple circuits with one extra CNOT per check operator and no additional ancillas reduce the accuracy threshold by less than a factor of $4$ when leakage and depolarizing noise rates are comparable. This becomes a factor of $2$ when the decoder uses 3-outcome measurements. Finally, when the physical error rate is less than $2\times 10^{-4}$, placing LRUs after every gate may achieve the lowest logical error rates of all of the circuits we considered. We anticipate that the closely related planar codes might exhibit the same accuracy thresholds and that the ideas may generalize naturally to other topological codes.

Modular quantum memories using passive linear optics and coherent feedback (pp1017-1040)
Hendra I. Nurdin and John E. Gough
In this paper, we show that quantum memory for qudit states encoded in a single photon pulsed optical field has a conceptually simple modular realization using only passive linear optics and coherent feedback. We exploit the idea that two decaying optical cavities can be coupled in a coherent feedback configuration to create an internal mode of the coupled system which is isolated and decoherence-free for the purpose of qubit storage. The qubit memory can then be switched between writing/read-out mode and storage mode simply by varying the routing of certain freely propagating optical fields in the network. It is then shown that the qubit memories can be interconnected with one another to form a qudit quantum memory. We explain each of the phase of writing, storage, and read-out for this modular quantum memory scheme. The results point a way towards modular architectures for complex compound quantum memories.

Quantum information splitting using a pair of GHZ states (pp1041-1047)
Kaushik Nandi and Goutam Paul
We describe a protocol for quantum information splitting (QIS) of a restricted class of three-qubit states among three parties Alice, Bob and Charlie, using a pair of GHZ states as the quantum channel. There are two different forms of this three-qubit state that is used for QIS depending on the distribution of the particles among the three parties. There is also a special type of four-qubit state that can be used for QIS using the above channel. We explicitly construct the quantum channel, Alice's measurement basis and the analytic form of the unitary operations required by the receiver for such a purpose.

An almost sudden jump in quantum complexity (pp1048-1059)
Or Sattath
The Quantum Satisfiability problem ($\qsat$) is the generalization of the canonical $\NPC$ problem - Boolean Satisfiability. $\ksqsat$ is the following variant of the problem: given a set of projectors of rank $1$, acting non-trivially on $k$ qubits out of $n$ qubits, such that each qubit appears in at most $s$ projectors, decide whether there exists a quantum state in the null space of all the projectors. Let $\qf(k)$ be the maximal integer $s$ such that every $\ksqsat$ instance is satisfiable. Deciding $\ksqsat[\qf(k)]$ is computationally easy: by definition the answer is ``satisfiable''. But, by relaxing the conditions slightly, we show that $\ksqsat[\qf(k)+2]$ is $\QMAoH$, for $k \geq 15$. This is a quantum analogue of a classical result by Kratochv{\'\i}l et al.~\cite{kratochvil1993one}. We use the term ``an \emph{almost} sudden jump'' to stress that the complexity of $\ksqsat[\qf(k)+1]$ is open, where the jump in the classical complexity is known to be sudden. We present an implication of this finding to the quantum PCP conjecture, arguably one of the most important open problems in the field of Hamiltonian complexity. Our implication imposes some constraints on one possible way to refute the quantum PCP.

The non-uniform stationary measure for discrete-time quantum walks in one dimension (pp1060-1075)
Norio Konno and Masato Takei
We consider stationary measures of the one-dimensional discrete-time quantum walks (QWs) with two chiralities, which is defined by a 2 $\times$ 2 unitary matrix $U$. In our previous paper \cite{Konno2014}, we proved that any uniform measure becomes the stationary measure of the QW by solving the corresponding eigenvalue problem. This paper reports that non-uniform measures are also stationary measures of the QW except when $U$ is diagonal. For diagonal matrices, we show that any stationary measure is uniform. Moreover, we prove that any uniform measure becomes a stationary measure for more general QWs not by solving the eigenvalue problem but by a simple argument.

back to QIC online Front page