Quantum Query Complexity of State Conversion

DOI10.1109/FOCS.2011.75zbMath1292.68069arXiv1011.3020MaRDI QIDQ5494975

Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, Mario Szegedy

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.3020

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

A query-efficient quantum algorithm for maximum matching on general graphs ⋮ Low-Sensitivity Functions from Unambiguous Certificates. ⋮ Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ A strong direct product theorem for quantum query complexity ⋮ Optimal parallel quantum query algorithms ⋮ Approximate span programs ⋮ EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS ⋮ Unnamed Item ⋮ Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ On the power of non-adaptive learning graphs ⋮ A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function ⋮ Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems ⋮ Quantum counterfeit coin problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum Algorithms for Classical Probability Distributions ⋮ Квантовые атаки на итерационные блочные шифры ⋮ Extended learning graphs for triangle finding ⋮ Key establishment à la Merkle in a quantum world ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum algorithms for learning symmetric juntas via the adversary bound