Vol.16 No.1&12, January 1, 2016

Complexity of the XY antiferromagnet at fixed magnetization (pp0001-0018)
          Andrew M. Childs, David Gosset, and Zak Webb
We prove that approximating the ground energy of the antiferromagnetic XY model on a simple graph at fixed magnetization (given as part of the instance specification) is QMA-complete. To show this, we strengthen a previous result by establishing QMA-completeness for approximating the ground energy of the Bose-Hubbard model on simple graphs. Using a connection between the XY and Bose-Hubbard models that we exploited in previous work, this establishes QMA-completeness of the XY model.

Single-query quantum algorithms for symmetric problems (pp0019-0038)
          Orest Bucicovschi, Daniel Copeland, David Meyer, and James Pommersheim
Given a unitary representation of a finite group on a finite-dimensional Hilbert space, we show how to find a state whose translates under the group are distinguishable with the highest probability. We apply this to several quantum oracle problems, including the \GM\ problem, in which the product of an ordered  $n$-tuple of group elements is to be determined by querying elements of the tuple. For any finite group $G$, we give an algorithm to find the product of two elements of $G$ with a single quantum query with probability $2/|G|$. This generalizes Deutsch's Algorithm from $\Zs_2$ to an arbitrary finite group. We further prove that this algorithm is optimal. We also introduce the \HCEP, in which the oracle acts by conjugating by an unknown element of the group. We show that for many groups, including dihedral and symmetric groups, the unknown element can be determined with probability $1$ using a single quantum query.

Quantum codes over a class of finite chain ring (pp0039-0049)
          Mustafa Sari and Irfan Siap
In this study, we introduce a new Gray map which preserves the orthogonality from the chain ring ${{F}_2}\left[ u \right]/\left( {{u^s}} \right)$ to ${F}_2^s$ where $F_2$ is the finite field with two elements. We also give a condition of the existence for cyclic codes of odd length containing its dual over the ring $ {{F}_2}\left[ u \right]/\left( {{u^s}} \right).$ By taking advantage of this Gray map and the structure of the ring, we obtain two classes of binary quantum error correcting (QEC) codes and we finally illustrate our results by presenting some examples with good parameters.

Security analysis of Quantum-Readout PUFs in the case of challenge-estimation attacks (pp0050-0060)
          Boris Skoric
Quantum Readout (QR) of Physical Unclonable Functions (PUFs) is a new technique for remotely authenticating objects, which has recently been demonstrated experimentally. The security is based on basic quantum information theoretic principles and holds under the assumption that the adversary cannot clone or physically emulate PUFs. We analyse the security of QR under a class of attacks called `digital emulation', in which the adversary first performs state estimation on the challenge and then bases his response on this estimate. We make use of a result by Bru\ss{} and Macchiavello to derive an upper bound on the adversary's success probability as a function of the Hilbert space dimension $K$ and the photon number~$n$. We prove that QR is unconditionally secure against digital emulation attacks when the challenges are Fock states. For non-Fock-states we provide a security proof under the condition that the attacker's measurements commute with the particle number operator.

Quantum-enhanced secure delegated classical computing (pp0061-0086)
          Vedran Dunjko, Theodoros Kapourniotis, and Elham Kashefi
We present a family of quantumly-enhanced protocols to achieve unconditionally secure delegated classical computation where the client and the server have both their classical and quantum computing capacity limited. We prove the same task cannot be achieved using only classical protocols. This extends the work of Anders and Browne on the computational power of correlations to a security setting. In doing so we are able to highlight the power of online quantum communication as we prove the same task could not be achieved using pre-shared (offline) quantum correlations.

Efficient approximation of diagonal unitaries over the Clifford+T basis (pp0087-0104)
          Jonathan Welch, Alex Bocharov, and Krysta M. Svore
We present an algorithm for the \emph{approximate} decomposition of diagonal operators, focusing specifically on decompositions over the Clifford+$T$ basis, that minimizes the number of phase-rotation gates in the synthesized approximation circuit. The equivalent $T$-count of the synthesized circuit is bounded by $k C_0 \log_2(1/\varepsilon) + E(n,k)$, where $k$ is the number of distinct phases in the diagonal $n$-qubit unitary, $\varepsilon$ is the desired precision, $C_0$ is a quality factor of the implementation method ($1<C_0<4$), and $E(n,k)$ is the total entanglement cost (in $T$ gates). We determine an optimal decision boundary in $(n,k,\varepsilon)$-space where our decomposition algorithm achieves lower entanglement cost than previous state-of-the-art techniques. Our method outperforms state-of-the-art techniques for a practical range of $\varepsilon$ values and diagonal operators and can reduce the number of $T$ gates exponentially in $n$ when $k \ll 2^n$.

Gaussian (N, z)-generalized Yang-Baxter operators (pp0105-0114)
          Eric Rowell
We find unitary matrix solutions $\tilde{R}(a)$ to the (multiplicative parameter-dependent) $(N,z)$-generalized Yang-Baxter equation that carry the standard measurement basis to $m$-level $N$-partite entangled states that generalize the $2$-level bipartite entangled Bell states. This is achieved by a careful study of solutions to the Yang-Baxter equation discovered by Fateev and Zamolodchikov in 1982.

Natural information measures for contextual probabilistic models (pp0115-0133)
          Federico Holik, Angel Plastino, and Manuel Saenz
In this article we provide, from a novel perspective, arguments that support the idea that, in the wake of Cox' approach to probability theory, von Neumann's entropy should be the natural one in Quantum Mechanics. We also generalize the pertinent reasoning to more general orthomodular lattices, which reveals the structure of a general non-Boolean information theory.

Quantum arithmetic and numerical analysis using Repeat-Until-Success circuits (pp0134-0178)
          Nathan Wiebe and Martin Roetteler
We develop a method for approximate synthesis of single-qubit rotations of the form $e^{-i f(\phi_1,\ldots,\phi_k)X}$ that is based on the Repeat-Until-Success (RUS) framework for quantum circuit synthesis. We demonstrate how smooth computable functions $f$ can be synthesized from two basic primitives. This synthesis approach constitutes a manifestly quantum form of arithmetic that differs greatly from the approaches commonly used in quantum algorithms. The key advantage of our approach is that it requires far fewer qubits than existing approaches: as a case in point, we show that using as few as $3$ ancilla qubits, one can obtain RUS circuits for approximate multiplication and reciprocals. We also analyze the costs of performing multiplication and inversion on a quantum computer using conventional approaches and find that they can require too many qubits to execute on a small quantum computer, unlike our approach.

back to QIC online Front page