Vol.18 No.1&12, February 1, 2018

A note on optimality of quantum circuits over metaplectic basis (pp0001-0017)
          Alex Bocharov
Metaplectic quantum basis is a universal multi-qutrit quantum basis, formed by the ternary Clifford group and the axial reflection gate $R=|0\rangle \langle 0|  + |1\rangle \langle 1| - |2\rangle \langle 2|$. It is arguably, a ternary basis with the simplest geometry. Recently Cui, Kliuchnikov, Wang and the Author have proposed a compilation algorithm to approximate any two-level Householder reflection to precision $\varepsilon$ by a metaplectic circuit of $R$-count at most $C \, \log_3(1/\varepsilon) + O(\log \log 1/\varepsilon)$ with $C=8$. A new result in this note takes the constant down to $C=5$ for non-exceptional target reflections under a certain credible number-theoretical conjecture. The new method increases the chances  of obtaining a truly optimal circuit but may not guarantee the true optimality. Efficient approximations of an important ternary quantum gate proposed by Howard, Campbell and others is also discussed.

Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness (pp0018-0050)
          Chris Cade, Ashley Montanaro, and Aleksandrs Belovs
We study space and time-efficient quantum algorithms for two graph problems -- deciding whether an $n$-vertex graph is a forest, and whether it is bipartite. Via a reduction to the s-t connectivity problem, we describe quantum algorithms for deciding both properties in $\tilde{O}(n^{3/2})$ time whilst using $O(\log n)$ classical and quantum bits of storage in the adjacency matrix model. We then present quantum algorithms for deciding the two properties in the adjacency array model, which run in time $\tilde{O}(n\sqrt{d_m})$ and also require $O(\log n)$ space, where $d_m$ is the maximum degree of any vertex in the input graph.

Reinforcement learning using quantum Boltzmann machines (pp0051-0074)
          Daniel Crawford, Anna Levit, Navid Ghadermarzy, Jaspreet S. Oberoi, and Pooya Ronagh
We investigate whether quantum annealers with select chip layouts can outperform classical computers in reinforcement learning tasks. We associate a transverse field Ising spin Hamiltonian with a layout of qubits similar to that of a deep Boltzmann machine (DBM) and use simulated quantum annealing (SQA) to numerically simulate quantum sampling from this system. We design a reinforcement learning algorithm in which the set of visible nodes representing the states and actions of an optimal policy are the first and last layers of the deep network. In absence of a transverse field, our simulations show that DBMs are trained more effectively than restricted Boltzmann machines (RBM) with the same number of nodes. We then develop a framework for training the network as a quantum Boltzmann machine (QBM) in the presence of a significant transverse field for reinforcement learning. This method also outperforms the reinforcement learning method that uses RBMs.

Qubit-loss-free fusion of W states (pp0075-0084)
          Meiyu Wang, Quanzhi Hao, Fengli Yan, and Ting Gao
With the assistance of weak cross-Kerr nonlinearities, we introduce an optical scheme to fuse two small-size polarization entangled photonic W states into a large-scale W state without qubit loss, i.e.,$\mathrm{W}_{n+m}$ state can be generated from an $n$-qubit W state and a $m$-qubit W state. To complete the fusion task, two polarization entanglement processes and one spatial entanglement process are applied. The fulfillments of the above processes are contributed by a cross-Kerr nonlinear interaction between the signal photons and a coherent state via Kerr media.  We analyze the resource cost and the success probability of the scheme. There is no complete failure output in our fusion mechanism, and all the remaining states are recyclable. In addition, there is no need for any controlled quantum gate and any ancillary photon, so this fusion scheme may be implemented with current experimental techniques.

Relations between bipartite entanglement measures (pp0085-0113)
          Katharina Schwaiger and Barbara Kraus
We investigate the entanglement of bipartite systems from an operational point of view. Main emphasis is put on bipartite pure states in the single copy regime. First, we present an operational characterization of bipartite pure state entanglement, viewing the state as a multipartite state. Then, we investigate the properties and relations of two classes of operational bipartite and multipartite entanglement measures, the so-called source and the accessible entanglement. The former measures how easy it is to generate a given state via local operations and classical communication (LOCC) from some other state, whereas the latter measures the potentiality of a state to be convertible to other states via LOCC.  We investigate which parameter regime is physically available, i.e. for which values of these measures does there exist a bipartite pure state. Moreover, we determine, given some state, which parameter regime can be accessed by it and from which parameter regime it can be accessed. We show that this regime can be determined analytically using the Positivstellensatz. We compute the boundaries of these sets and the boundaries of the corresponding source and accessible sets. Furthermore, we relate these results to other entanglement measures and compare their behaviors.

Magic state distillation at intermediate size (pp0114-0140)
          Jeongwan Haah, Matthew B. Hastings, D. Poulin, and D. Wecker
Recently~\cite{hhpw} we proposed a family of magic state distillation protocols that obtains asymptotic performance that is conjectured to be optimal. This family depends upon several codes, called ``inner codes'' and ``outer codes.'' In Ref.~\cite{hhpw}, some small examples of these codes were given as well as an analysis of codes in the asymptotic limit.  Here, we analyze such protocols in an intermediate size regime, using hundreds to thousands of qubits. We use BCH inner codes~\cite{qbch}, combined with various outer codes. We extend the protocols of Ref.~\cite{hhpw} by adding error correction in some cases. We present a variety of protocols in various input error regimes; in many cases these protocols require significantly fewer input magic states to obtain a given output error than previous protocols.
 

back to QIC online Front page