QIC Abstracts

 Vol.15 No.3&4, March 1, 2015

Research Articles:

Adiabatic optimization without local minima (pp0181-0199)
          
Michael Jarret and Stephen P. Jordan
Several previous works have investigated the circumstances under which quantum adiabatic optimization algorithms can tunnel out of local energy minima that trap simulated annealing or other classical local search algorithms. Here we investigate the even more basic question of whether adiabatic optimization algorithms always succeed in polynomial time for trivial optimization problems in which there are no local energy minima other than the global minimum. Surprisingly, we find a counterexample in which the potential is a single basin on a graph, but the eigenvalue gap is exponentially small as a function of the number of vertices. In this counterexample, the ground state wavefunction consists of two ``lobes'' separated by a region of exponentially small amplitude. Conversely, we prove if the ground state wavefunction is single-peaked then the eigenvalue gap scales at worst as one over the square of the number of vertices.

Ground state blind quantum computation on AKLT state (pp0200-0234)
          
Tomoyuki Morimae, Vedran Dunjko, and Elham Kashefi
The blind quantum computing protocols (BQC) enable a classical client with limited quantum technology to delegate a computation to the quantum server(s) in such a way that the privacy of the computation is preserved. Here we present a new scheme for BQC that uses the concept of the measurement based quantum computing with the novel resource state of Affleck-Kennedy-Lieb-Tasaki (AKLT) chains leading to more robust computation. AKLT states are physically motivated resource as they are gapped ground states of a physically natural Hamiltonian in condensed matter physics. Our BQC protocol can enjoy the advantages of AKLT resource states (in a multiserver setup), such as the cooling preparation of the resource state, the energy-gap protection of the quantum computation. It also provides a simple and efficient preparation of the resource state in linear optics with biphotons.

Quantum circuits and Spin(3n) groups (pp0235-0259)
          
Alexander Yu. Vlasov
All quantum gates with one and two qubits may be described by elements of Spin groups due to isomorphisms Spin(3)\isomSU(2) and Spin(6)\isomSU(4). However, the group of n-qubit gates SU(2^n) for n>2 has bigger dimension than Spin(3n). A quantum circuit with one- and two-qubit gates may be used for construction of arbitrary unitary transformation SU(2^n). Analogously, the `$Spin(3n)$ circuits' are introduced in this work as products of elements associated with one- and two-qubit gates with respect to the above-mentioned isomorphisms. The matrix tensor product implementation of the Spin(3n) group together with relevant models by usual quantum circuits with 2n qubits are investigated in such a framework. A certain resemblance with well-known sets of non-universal quantum gates (e.g., matchgates, noninteracting-fermion quantum circuits) related with Spin(2n) may be found in presented approach. Finally, a possibility of the classical simulation of such circuits in polynomial time is discussed.

Limitations of single coset states and quantum algorithms for code equivalence (pp0260-0294)
          
Hang Dinh, Cristopher Moore, and Alexander Russell
Quantum computers can break the RSA, El Gamal, and elliptic curve public-key cryptosystems, as they can efficiently factor integers and extract discrete logarithms. The power of such quantum attacks lies in \emph{quantum Fourier sampling}, an algorithmic paradigm based on generating and measuring coset states. %This motivates the investigation of the power or limitations of quantum Fourier sampling, especially in attacking candidates for ``post-quantum'' cryptosystems -- classical cryptosystems that can be implemented with today's computers but will remain secure even in the presence of quantum attacks. In this article we extend previous negative results of quantum Fourier sampling for Graph Isomorphism, which corresponds to hidden subgroups of order two (over S_n, to several cases corresponding to larger hidden subgroups. For one case, we strengthen some results of Kempe, Pyber, and Shalev on the Hidden Subgroup Problem over the symmetric group. In another case, we show the failure of quantum Fourier sampling on the Hidden Subgroup Problem over the general linear group GL_2(\FF_q). The most important case corresponds to Code Equivalence, the problem of determining whether two given linear codes are equivalent to each other up to a permutation of the coordinates. Our results suggest that for many codes of interest---including generalized Reed Solomon codes, alternant codes, and Reed-Muller codes---solving these instances of Code Equivalence via Fourier sampling appears to be out of reach of current families of quantum algorithms.

Rational approximations and quantum algorithms with postselection (pp0295-0307)
          
Urmila Mahadev and Ronald de Wolf
We study the close connection between rational functions that approximate a given Boolean function, and quantum algorithms that compute the same function using postselection. We show that the minimal degree of the former equals (up to a factor of 2) the minimal query complexity of the latter. We give optimal (up to constant factors) quantum algorithms with postselection for the Majority function, slightly improving upon an earlier algorithm of Aaronson. Finally we show how Newman's classic theorem about low-degree rational approximation of the absolute-value function follows from these algorithms.

Complementarity between signaling and local indeterminacy (pp0308-0315)
          
S. Aravinda and R. Srikanth
The correlations that violate the CHSH inequality are known to have complementary contributions from signaling and local indeterminacy. This complementarity is shown to represent a strengthening of Bell's theorem, and can be used to certify randomness in a device-independent way, assuming neither the validity of quantum mechanics nor even no-signaling. We obtain general nonlocal resources that can simulate the statistics of the singlet state, encompassing existing results. We prove a conjecture due to Hall (2010) and Kar et al. (2011) on the complementarity for such resources.

Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning (pp0316-0356)
          
Nathan Wiebe, Ashish Kapoor, and Krysta M. Svore
We present quantum algorithms for performing nearest-neighbor learning and $k$--means clustering. At the core of our algorithms are fast and coherent quantum methods for computing the Euclidean distance both directly and via the inner product which we couple with methods for performing amplitude estimation that do not require measurement. We prove upper bounds on the number of queries to the input data required to compute such distances and find the nearest vector to a given test example. In the worst case, our quantum algorithms lead to polynomial reductions in query complexity relative to Monte Carlo algorithms. We also study the performance of our quantum nearest-neighbor algorithms on several real-world binary classification tasks and find that the classification accuracy is competitive with classical methods.

back to QIC online Front page