2026-07-29T10:45:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23490 2025-10-02T12:56:41Z ddc:004 open_access

Nearly Optimal Circuit Size for Sparse Quantum State Preparation Li, Lvzhou Luo, Jingquan Quantum computing quantum state preparation circuit complexity Quantum state preparation is a fundamental and significant subroutine in quantum computing. In this paper, we conduct a systematic investigation of the circuit size (the total count of elementary gates in the circuit) for sparse quantum state preparation. A quantum state is said to be d-sparse if it has only d non-zero amplitudes. For the task of preparing an n-qubit d-sparse quantum state, we obtain the following results: - Without ancillary qubits: Any n-qubit d-sparse quantum state can be prepared by a quantum circuit of size O(nd/(log n) + n) without using ancillary qubits, which improves the previous best results. It is asymptotically optimal when d = poly(n), and this optimality holds for a broader scope under some reasonable assumptions. - With limited ancillary qubits: (i) Based on the first result, we prove for the first time a trade-off between the number of ancillary qubits and the circuit size: any n-qubit d-sparse quantum state can be prepared by a quantum circuit of size O((nd)/(log(n + m)) + n) using m ancillary qubits for any m ∈ O((nd)/(log nd) + n). (ii) We establish a matching lower bound Ω((nd)/(log(n+m))+n) under some reasonable assumptions, and obtain a slightly weaker lower bound Ω((nd)/(log(n+m)+log d) + n) without any assumptions. - With unlimited ancillary qubits: Given an arbitrary amount of ancillary qubits available, the circuit size for preparing n-qubit d-sparse quantum states is Θ((nd)/(log nd) + n). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lvzhou Li and Jingquan Luo 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.113 urn:nbn:de:0030-drops-234900 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.113 eng https://creativecommons.org/licenses/by/4.0/legalcode