1. Symmetry-assisted adversaries for quantum state generation
Andris Ambainis, Lo?ck Magnin, Martin Roetteler, J��r��mie Roland
26th IEEE Conference on Computational Complexity (CCC’11), pages 167-177, 2011
http://arxiv.org/abs/1012.2112
We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum state generation might be a route to tackle the {\sc Graph Isomorphism} problem. We show that for the related problem of {\sc Index Erasure} our method leads to a lower bound of $\Omega(\sqrt N)$ which matches an upper bound obtained via reduction to quantum search on $N$ elements. This closes an open problem first raised by Shi [FOCS'02]. Our approach is based on two ideas: (i) on the one hand we generalize the known additive and multiplicative adversary methods to the case of quantum state generation, (ii) on the other hand we show how the symmetries of the underlying problem can be leveraged for the design of optimal adversary matrices and dramatically simplify the computation of adversary bounds. Taken together, these two ideas give the new result for {\sc Index Erasure} by using the representation theory of the symmetric group. Also, the method can lead to lower bounds even for small success probability, contrary to the standard adversary method. Furthermore, we answer an open question due to \v{S}palek [CCC'08] by showing that the multiplicative version of the adversary method is stronger than the additive one for any problem. Finally, we prove that the multiplicative bound satisfies a strong direct product theorem, extending a result by \v{S}palek to quantum state generation problems.
2. Quantum walks on complex networks with connection instabilities and community structure
Dimitris I. Tsomokos
Phys. Rev. A 83, 052315 (2011)
http://arxiv.org/abs/1012.2405
A continuous-time quantum walk is investigated on complex networks with the characteristic property of community structure, which is shared by most real-world networks. Motivated by the prospect of viable quantum networks, I focus on the effects of network instabilities in the form of broken links, and examine the response of the quantum walk to such failures. It is shown that the reconfiguration of the quantum walk is determined by the community structure of the network. In this context, quantum walks based on the adjacency and Laplacian matrices of the network are compared, and their responses to link failures is analyzed.
3. Quantum property testing for bounded-degree graphs
Andris Ambainis, Andrew M. Childs, Yi-Kai Liu
Proceedings of RANDOM 2011, Lecture Notes in Computer Science 6845, pp. 365-376
http://arxiv.org/abs/1012.3174
We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the Omega(sqrt(N)) classical lower bound. For testing expansion, we also prove an Omega(N^(1/4)) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph structure.
4. Constructing elliptic curve isogenies in quantum subexponential time
Andrew M. Childs, David Jao, Vladimir Soukharev
J. Math. Cryptol., 8(1):1-29, 2014
http://arxiv.org/abs/1012.4019
Given two elliptic curves over a finite field having the same cardinality and endomorphism ring, it is known that the curves admit an isogeny between them, but finding such an isogeny is believed to be computationally difficult. The fastest known classical algorithm takes exponential time, and prior to our work no faster quantum algorithm was known. Recently, public-key cryptosystems based on the presumed hardness of this problem have been proposed as candidates for post-quantum cryptography. In this paper, we give a subexponential-time quantum algorithm for constructing isogenies, assuming the Generalized Riemann Hypothesis (but with no other assumptions). Our algorithm is based on a reduction to a hidden shift problem, together with a new subexponential-time algorithm for evaluating isogenies from kernel ideals (under only GRH), and represents the first nontrivial application of Kuperberg's quantum algorithm for the hidden shift problem. This result suggests that isogeny-based cryptosystems may be uncompetitive with more mainstream quantum-resistant cryptosystems such as lattice-based cryptosystems.
5. Entanglement for discrete-time quantum walks on the line
Yusuke Ide, Norio Konno, Takuya Machida
Quantum Information and Computation, Vol.11 No.9&10, pp.855-866 (2011)
http://arxiv.org/abs/1012.4164
The discrete-time quantum walk is a quantum counterpart of the random walk. It is expected that the model plays important roles in the quantum field. In the quantum information theory, entanglement is a key resource. We use the von Neumann entropy to measure the entanglement between the coin and the particle's position of the quantum walks. Also we deal with the Shannon entropy which is an important quantity in the information theory. In this paper, we show limits of the von Neumann entropy and the Shannon entropy of the quantum walks on the one dimensional lattice starting from the origin defined by arbitrary coin and initial state. In order to derive these limits, we use the path counting method which is a combinatorial method for computing probability amplitude.
6. Asymptotic entanglement in 1D quantum walks with a time-dependent coined
S. Salimi, R. Yosefjani
International Journal of Modern Physics B, Vol. 26, No. 20 (2012) 1250112
http://arxiv.org/abs/1012.4566
Discrete-time quantum walk evolve by a unitary operator which involves two operators a conditional shift in position space and a coin operator. This operator entangles the coin and position degrees of freedom of the walker. In this paper, we investigate the asymptotic behavior of the coin position entanglement (CPE) for an inhomogeneous quantum walk which determined by two orthogonal matrices in one-dimensional lattice. Free parameters of coin operator together provide many conditions under which a measurement perform on the coin state yield the value of entanglement on the resulting position quantum state. We study the problem analytically for all values that two free parameters of coin operator can take and the conditions under which entanglement becomes maximal are sought.
7. Quantumness of noisy quantum walks: a comparison between measurement-induced disturbance and quantum discord
Balaji R. Rao, R. Srikanth, C. M. Chandrashekar, Subhashish Banerjee
Phys. Rev. A 83, 064302 (2011)
http://arxiv.org/abs/1012.5040
Noisy quantum walks are studied from the perspective of comparing their quantumness as defined by two popular measures, measurement-induced disturbance (MID) and quantum discord (QD). While the former has an operational definition, unlike the latter, it also tends to overestimate non-classicality because of a lack of optimization over local measurements. Applied to quantum walks, we find that MID, while acting as a loose upper bound on QD, still tends to reflect correctly the trends in the behavior of the latter. However, there are regimes where its behavior is not indicative of non-classicality: in particular, we find an instance where MID increases with the application of noise, where we expect a reduction of quantumness.