Vol.14 No.7&8, May 1, 2014

Generalizing and derandomizing Gurvits's approximation algorithm for the permanent  (pp0541-0559)
          Scott Aaronson and Travis Hance
Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an $n\times n$ matrix A. The algorithm runs in $O( n^{2}/\varepsilon^{2})$ time, and approximates $\operatorname*{Per}( A)$ to within $\pm\varepsilon\left\Vert A\right\Vert ^{n}$ additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. \ This makes it highly relevant to quantum optics, where the permanents of bounded-norm complex matrices play a central role. (In particular, $n\times n$ permanents arise as the transition amplitudes for $n$ identical photons.)  Indeed, the existence of Gurvits's algorithm is why, in their recent work on the \textit{hardness} of quantum optics, Aaronson and Arkhipov (AA) had to talk about sampling problems rather than ordinary decision problems. In this paper, we improve Gurvits's algorithm in two ways. First, using an idea from quantum optics, we generalize the algorithm so that it yields a better approximation when the matrix A has either repeated rows or repeated columns. Translating back to quantum optics, this lets us classically estimate the probability of any outcome of an AA-type experiment -- even an outcome involving multiple photons "bunched" in the same mode -- at least as well as that probability can be estimated by the experiment itself. It also yields a general upper bound on the probabilities of "bunched" outcomes, which resolves a conjecture of Gurvits and might be of independent physical interest. Second, we use $\varepsilon$-biased sets to derandomize Gurvits's algorithm, in the special case where the matrix A is nonnegative. More interestingly, we generalize the notion of $\varepsilon$-biased sets to the complex numbers, construct "complex $\varepsilon$-biased sets", then use those sets to derandomize even our generalization of Gurvits's algorithm to the case (again for nonnegative A) where some rows or columns are identical.  Whether Gurvits's algorithm can be derandomized for general A remains an outstanding problem.

Distillation protocols for Fourier states in quantum computing (pp0560-0576)
          Cody Jones
Fourier states are multi-qubit registers that facilitate phase rotations in fault-tolerant quantum computing. We propose distillation protocols for constructing the fundamental, $n$-qubit Fourier state with error $O(2^{-n})$ at a cost of $O(n \log n)$ Toffoli gates and Clifford gates, or any arbitrary Fourier state using $O(n^2)$ gates. We analyze these protocols with methods from digital signal processing. These results suggest that phase kickback, which uses Fourier states, could be the current lowest-overhead method for generating arbitrary phase rotations.

Quantum computation of prime number functions (pp0577-0588)
          Jose I. Latorre and German Sierra
We propose a quantum circuit that creates a pure state corresponding to the quantum superposition of all prime numbers less than $2^n$, where $n$ is the number of qubits of the register. This Prime state can be built using Grover's algorithm, whose oracle is a quantum implementation of the classical Miller-Rabin primality test. The Prime state is highly entangled, and its entanglement measures encode number theoretical functions such as the distribution of twin primes or the Chebyshev bias. This algorithm can be further combined with the quantum Fourier transform to yield an estimate of the prime counting function, more efficiently than any classical algorithm and with an error below the bound that allows for the verification of the Riemann hypothesis. Arithmetic properties of prime numbers are then, in principle, amenable to experimental verifications on quantum systems.

Robust variations of secret sharing through noisy quantum channel (pp0589-0607)
          Xiu-Bo Chen, Gang Xu, Yuan Su, and Yi-Xian Yang
In this paper, the perfect secret sharing in quantum cryptography is investigated. On one hand, the security of a recent protocol [Adhikari et al. Quantum Inform. \& Comput. 12 (2012) 0253-0261] is re-examined. We find that it violates the requirement of information theoretic security in the secret sharing and suffers from the information leakage. The cryptanalysis including several specific attack strategies are given, which shows that a dishonest participant can steal half or all of the secrets without being detected. On the other hand, we design a new quantum secret sharing protocol. The security of protocol is rigorously proved. It meets the fundamental requirement of information theoretic security. Furthermore, the security analysis including both the outside attacks and participant attacks is given in details. It is shown that our proposed protocol can achieve perfect secret sharing.

Uselessness for an Oracle model with internal randomness (pp0608-0624)
          Aram W. Harrow and David J. Rosenbaum
We consider a generalization of the standard oracle model in which the oracle acts on the target with a permutation selected according to internal random coins. We describe several problems that are impossible to solve classically but can be solved by a quantum algorithm using a single query; we show that such infinity-vs-one separations between classical and quantum query complexities can be constructed from much weaker separations. We also give conditions to determine when oracle problems -- either in the standard model, or in any of the generalizations we consider -- cannot be solved with success probability better than random guessing would achieve. In the oracle model with internal randomness where the goal is to gain any nonzero advantage over guessing, we prove (roughly speaking) that k quantum queries are equivalent in power to 2k classical queries, thus extending results of Meyer and Pommersheim.

Implementation of a multiqubit phase gate with one qubit simultaneously controlling n qubits in the ion-trap system (pp0625-0632)
          Xiu Lin
In this paper, we present a scheme for implementing a multiqubit phase gate with one control qubit simultaneously controlling n target qubits in the ion-trap system. In our scheme, there is no energy exchange between the internal and external degrees of freedom in the course of operation, and the vibrational mode is only virtually excited. The system is insensitive to changes in the vibrational motion. The proposed scheme is experimentally feasible based on the present ion-trap techniques.

Classical simulation complexity of extended Clifford circuits (pp0633-0648)
          Richard Jozsa and Marrten Van den Nest
Clifford gates are a winsome class of quantum operations combining mathematical elegance with physical significance. The Gottesman-Knill theorem asserts that Clifford computations can be classically efficiently simulated but this is true only in a suitably restricted setting. Here we consider Clifford computations with a variety of additional ingredients: (a) strong vs. weak simulation, (b) inputs being computational basis states vs. general product states, (c) adaptive vs. non-adaptive choices of gates for circuits involving intermediate measurements, (d) single line outputs vs. multi-line outputs. We consider the classical simulation complexity of all combinations of these ingredients and show that many are not classically efficiently simulatable (subject to common complexity assumptions such as P not equal to NP). Our results reveal a surprising proximity of classical to quantum computing power viz. a class of classically simulatable quantum circuits which yields universal quantum computation if extended by a purely classical additional ingredient that does not extend the class of quantum processes occurring.

Fast quantum modular exponentiation architecture for Shor's factoring algorithm (pp0649-0682)
          Archimedes Pavlidis and Dimitris Gizopoulos
We present a novel and efficient, in terms of circuit depth, design for Shor's quantum factorization algorithm. The circuit effectively utilizes a diverse set of adders based on the Quantum Fourier transform (QFT) Draper's adders to build more complex arithmetic blocks: quantum multiplier/accumulators by constants and quantum dividers by constants. These arithmetic blocks are effectively architected into a quantum modular multiplier which is the fundamental block for the modular exponentiation circuit, the most computational intensive part of Shor's algorithm. The proposed modular exponentiation circuit has a depth of about $2000n^2$ and requires $9n+2$ qubits, where $n$ is the number of bits of the classic number to be factored. The total quantum cost of the proposed design is $1600n^3$. The circuit depth can be further decreased by more than three times if the approximate QFT implementation of each adder unit is exploited.

On the geometry of stabilizer states (pp0683-0720)
          Hector J. Garcia, Igor L. Markov, and Andrew W. Cross
Large-scale quantum computation is likely to require massive quantum error correction (QEC). QEC codes and circuits are described via the stabilizer formalism, which represents stabilizer states by keeping track of the operators that preserve them. Such states are obtained by {\em stabilizer circuits} (consisting of CNOT, Hadamard and Phase gates) and can be represented compactly on conventional computers using $\Theta (n^2)$ bits, where $n$ is the number of qubits \cite{Gottes98}. As an additional application, the work in~\cite{Aaron, AaronGottes} suggests the use of superpositions of stabilizer states to represent arbitrary quantum states. To aid in such applications and improve our understanding of stabilizer states, we characterize and count nearest-neighbor stabilizer states, quantify the distribution of angles between pairs of stabilizer states, study succinct stabilizer superpositions and stabilizer bivectors, explore the approximation of non-stabilizer states by single stabilizer states and short linear combinations of stabilizer states, develop an improved inner-product computation for stabilizer states via synthesis of compact canonical stabilizer circuits, propose an orthogonalization procedure for stabilizer states, and evaluate several of these algorithms empirically.

back to QIC online Front page