QIC Abstracts

 Vol.16 No.13&14, October 1, 2016

Research Articles:

Single-quadrature continuous-variable quantum key distribution (pp1081-1095)
Tobias Gehring, Christian S. Jacobsen, and Ulrik L. Andersen
Most continuous-variable quantum key distribution schemes are based on the Gaussian modulation of coherent states followed by continuous quadrature detection using homodyne detectors. In all previous schemes, the Gaussian modulation has been carried out in conjugate quadratures thus requiring two independent modulators for their implementations. Here, we propose and experimentally test a largely simplified scheme in which the Gaussian modulation is performed in a single quadrature. The scheme is shown to be asymptotically secure against collective attacks, and considers a specific attack using asymmetric preparation and excess noise. We find that this protocol is considerably more sensitive to noise than other CVQKD schemes, as a consequence of the simplified implementation. A single-quadrature modulation approach renders the need for a costly amplitude modulator unnecessary, and thus facilitates commercialization of continuous-variable quantum key distribution, provided that the low noise requirement can be achieved.

Optimal and asymptotically optimal NCT reversible circuits by the gate types (pp1096-1112)
Dmitri Maslov
We report optimal and asymptotically optimal reversible circuits composed of NOT, CNOT, and Toffoli (NCT) gates, keeping the count by the subsets of the gate types used. This study fine tunes the circuit complexity figures for the realization of reversible functions via reversible NCT circuits. An important consequence is a result on the limitation of the use of the $T$-count quantum circuit metric popular in applications.

Quantum circuits for qubit fusion (pp1113-1124)
Jonathan Edward Moussa
We consider four-dimensional qudits as qubit pairs and their qudit Pauli operators as qubit Clifford operators. This introduces a nesting, $C_1^2 \subset C_2^4 \subset C_3^2$, where $C_n^m$ is the $n$th level of the $m$-dimensional qudit Clifford hierarchy. If we can convert between logical qubits and qudits, then qudit Clifford operators are qubit non-Clifford operators. Conversion is achieved by qubit fusion and qudit fission using stabilizer circuits that consume a resource state. This resource is a fused qubit stabilizer state with a fault-tolerant state preparation using stabilizer circuits.

Quantum simulations of one dimensional quantum systems (pp1125-1168)
Rolando Diego Somma
We present quantum algorithms for the simulation of quantum systems in one spatial dimension, which result in quantum speedups that range from superpolynomial to polynomial. We first describe a method to simulate the evolution of the quantum harmonic oscillator (QHO) based on a refined analysis of the Trotter-Suzuki formula that exploits the Lie algebra structure. For total evolution time $t$ and precision $\epsilon>0$, the complexity of our method is $ O(\exp(\gamma \sqrt{ \log(N/\epsilon)}))$, where $\gamma>0$ is a constant and $N$ is the quantum number associated with an ``energy cutoff'' of the initial state. Remarkably, this complexity is subpolynomial in $N/\epsilon$. We also provide a method to prepare
discrete versions of the eigenstates of the QHO of complexity polynomial in $\log(N)/\epsilon$, where $N$ is the dimension or number of points in the discretization. Next, we consider a system with a quartic potential. Our numerical simulations suggest a method for simulating the evolution of sublinear complexity $\tilde O(N^{1/3+o(1)})$, for constant $t$ and $\epsilon$. We also analyze complex one-dimensional systems and prove a complexity bound $\tilde O(N)$, under fairly general assumptions. Our quantum algorithms may find applications in other problems. As an example, we discuss a generalization of the Fourier transform that is useful for signal analysis and can be formulated in terms of the evolution of the QHO.

The quantum complexity of approximating the frequency moments (pp1169-1190)
Ashley Montanaro
The k'th frequency moment of a sequence of integers is defined as $F_k = \sum_j n_j^k$, where $n_j$ is the number of times that $j$ occurs in the sequence. Here we study the quantum complexity of approximately computing the frequency moments in two settings. In the query complexity setting, we wish to minimise the number of queries to the input used to approximate $F_k$ up to relative error $\epsilon$. We give quantum algorithms which outperform the best possible classical algorithms up to quadratically. In the multiple-pass streaming setting, we see the elements of the input one at a time, and seek to minimise the amount of storage space, or passes over the data, used to approximate $F_k$. We describe quantum algorithms for $F_0$, $F_2$ and $F_\infty$ in this model which substantially outperform the best possible classical algorithms in certain parameter regimes.

The structure of nearly-optimal quantum strategies for the non-local XOR games (pp1191-1211)
Dimiter Ostrev
We consider the infinite family of non-local games CHSH$(n)$. We consider nearly-optimal strategies for CHSH$(n)$. We introduce a notion of approximate homomorphism for strategies and show that any nearly-optimal strategy for
non-local XOR is approximately homomorphic to the canonical optimal non-local XOR strategy. This demonstrates that any nearly-optimal non-local XOR strategy must approximately contain the algebraic structure of the canonical optimal strategy.

A quantum version of Schoning's algorithm applied to quantum 2-SAT (pp1212-1227)
Edward Farhi, Shelby Kimmel, and Kristan Temme
We study a quantum algorithm that consists of a simple quantum Markov process, and we analyze its behavior on restricted versions of Quantum 2-SAT. We prove that the algorithm solves these decision problems with high probability for $n$ qubits, $L$ clauses, and promise gap $c$ in time ${\cal O}(n^2 L^2 c^{-2})$. If the Hamiltonian is additionally polynomially gapped, our algorithm efficiently produces a state that has high overlap with the satisfying subspace. The Markov process we study is a quantum analogue of Sch\"oning's probabilistic algorithm for $k$-SAT.

Random MERA states and the tightness of the Brandao-Horodecki entropy bound (pp1228-1252)
Matthew Hastings
We construct a random MERA state with a bond dimension that varies with the level of the MERA. This causes the state to exhibit a very different entanglement structure from that usually seen in MERA, with neighboring intervals of length $l$ exhibiting a mutual information proportional to $\epsilon l$ for some constant $\epsilon$, up to a length scale exponentially large in $\epsilon$. We express the entropy of a random MERA in terms of sums over cuts through the MERA network, with the entropy in this case controlled by the cut minimizing bond dimensions cut through. One motivation for this construction is to investigate the tightness of the Brandao-Horodecki\cite{bh} entropy bound relating entanglement to correlation decay. Using the random MERA, we show that at least part of the proof is tight: there do exist states with the required property of having linear mutual information between neighboring intervals at all length scales. We conjecture that this state has exponential correlation decay and that it demonstrates that the Brandao-Horodecki bound is tight (at least up to constant factors), and we provide some numerical evidence for this as well as a sketch of how a proof of correlation decay might proceed.

back to QIC online Front page