2026-08-16T22:16:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4319 2024-03-06T10:34:48Z ddc:004 open_access

Dequantizing Read-once Quantum Formulas Cosentino, Alessandro Kothari, Robin Paetznick, Adam formulas dequantization circuit complexity Quantum formulas, defined by Yao [FOCS'93], are the quantum analogs of classical formulas, i.e., classical circuits in which all gates have fanout one. We show that any read-once quantum formula over a gate set that contains all single-qubit gates is equivalent to a read-once classical formula of the same size and depth over an analogous classical gate set. For example, any read-once quantum formula over Toffoli and single-qubit gates is equivalent to a read-once classical formula over Toffoli and NOT gates. We then show that the equivalence does not hold if the read-once restriction is removed. To show the power of quantum formulas without the read-once restriction, we define a new model of computation called the one-qubit model and show that it can compute all boolean functions. This model may also be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alessandro Cosentino and Robin Kothari and Adam Paetznick 2013 Is Part Of LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2013.80 urn:nbn:de:0030-drops-43197 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.80 eng https://creativecommons.org/licenses/by/3.0/legalcode