Qubit complexity of continuous problems

DOI10.1007/S11784-009-0132-7MaRDI QIDQ2431383zbMATH OpenOpenAlexFDO

Authors J. F. Traub, A. Papageorgiou

Publication date 13 April 2011

Published in Journal of Fixed Point Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0512082

zbMATH Keywords

numerical approximationquantum algorithmsquery complexity

Mathematics Subject Classification ID

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

Abstract: The number of qubits used by a quantum algorithm will be a crucial computational resource for the foreseeable future. We show how to obtain the classical query complexity for continuous problems. We then establish a simple formula for a lower bound on the qubit complexity in terms of the classical query complexity

Recommendations

• The quantum setting with randomized queries for continuous problems
• Quantum complexity of integration
• Quantum complexity of the approximation for the classes \({\mathcal B}(W^r_p([0,1]^d))\) and \({\mathcal B}(H^r_p([0,1]^d))\)
• Large-Scale Scientific Computing
• scientific article; zbMATH DE number 2186559

Cited in

(7)

• On the quantum complexity of the continuous hidden subgroup problem
• Representing continuoust-norms in quantum computation with mixed states
• Computational Complexity of Quantum Satisfiability
• Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding
• scientific article; zbMATH DE number 5049912 (Why is no real title available?)
• The quantum setting with randomized queries for continuous problems
• The quantum query complexity of elliptic PDE

This page was built for publication: Qubit complexity of continuous problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2431383)