{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,5]],"date-time":"2026-04-05T10:16:24Z","timestamp":1775384184161,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,10,29]],"date-time":"2020-10-29T00:00:00Z","timestamp":1603929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["Phy-1818914, CF-1730449\/1832377"],"award-info":[{"award-number":["Phy-1818914, CF-1730449\/1832377"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>\n            Quantum computation is traditionally expressed in terms of quantum bits, or qubits. In this work, we instead consider three-level qu\n            <jats:italic>trits<\/jats:italic>\n            . Past work with qutrits has demonstrated only constant factor improvements, owing to the log\n            <jats:sub>2<\/jats:sub>\n            (3) binary-to-ternary compression factor. We present a novel technique, intermediate qutrits, to achieve sublinear depth decompositions of the Generalized Toffoli and other arithmetic circuits using no additional ancilla\u2014a significant improvement over linear depth for the best qubit-only equivalents. For example, our Generalized Toffoli construction features a 70\u00d7 improvement in two-qudit gate count over a qubit-only decomposition. This results in circuit cost reductions for important algorithms like quantum neurons, Grover search, and even Shor\u2019s algorithm. Using a previously developed simulator with near-term noise models, we demonstrate for these models over 90% mean reliability (fidelity) for the Toffoli construction, versus under 30% for the qubit-only baseline. For our other constructions, such as the Incrementer, the A + B adder and the +K adder, we demonstrate the power of intermediate qutrits in producing asymptotic depth improvements with no additional ancilla. Together, these results suggest qutrits offer a promising path toward scaling quantum computation.\n          <\/jats:p>","DOI":"10.1145\/3406309","type":"journal-article","created":{"date-parts":[[2020,10,29]],"date-time":"2020-10-29T22:09:45Z","timestamp":1604009385000},"page":"1-25","source":"Crossref","is-referenced-by-count":14,"title":["Improved Quantum Circuits via Intermediate Qutrits"],"prefix":"10.1145","volume":"1","author":[{"given":"Jonathan M.","family":"Baker","sequence":"first","affiliation":[{"name":"University of Chicago, Chicago"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Casey","family":"Duckering","sequence":"additional","affiliation":[{"name":"University of Chicago, Chicago"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pranav","family":"Gokhale","sequence":"additional","affiliation":[{"name":"University of Chicago, Chicago"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Natalie C.","family":"Brown","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenneth R.","family":"Brown","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frederic T.","family":"Chong","sequence":"additional","affiliation":[{"name":"University of Chicago, Chicago"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,10,29]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Quantum Machine Learning. Nature 549 (13","author":"Biamonte Jacob","year":"2016"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-physchem-032210-103512"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_5_1","volume-title":"Quantum computing in the NISQ era and beyond. Quantum 2 (Aug","author":"Preskill John","year":"2018"},{"key":"e_1_2_1_6_1","volume-title":"2018 51st Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO\u201918)","author":"Ding Yongshan","year":"2018"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 50th Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO-50\u201917)","author":"Javadi-Abhari Ali"},{"key":"e_1_2_1_8_1","first-page":"4","article-title":"Two-step approach to scheduling quantum circuits. Quantum Sci","volume":"3","author":"Guerreschi Gian Giacomo","year":"2018","journal-title":"Technol."},{"key":"e_1_2_1_9_1","unstructured":"Archimedes Pavlidis and Emmanuel Floratos. 2017. Arithmetic circuits for multilevel qudits based on quantum Fourier transform. arXiv preprint arXiv:1707.08834.  Archimedes Pavlidis and Emmanuel Floratos. 2017. Arithmetic circuits for multilevel qudits based on quantum Fourier transform. arXiv preprint arXiv:1707.08834."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1103\/PhysRevA.91.012322","article-title":"Efficient preparation and detection of microwave dressed-state qubits and qutrits with trapped ions","volume":"91","author":"Randall J.","year":"2015","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1103\/PhysRevA.98.043414","article-title":"Generation of high-fidelity quantum control methods for multilevel systems","volume":"98","author":"Randall J.","year":"2018","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_12_1","volume-title":"International Symposium on Computer Architecture (ISCA\u201919)","author":"Gokhale Pranav"},{"key":"e_1_2_1_13_1","volume-title":"Chuang","author":"Nielsen Michael A.","year":"2011"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","volume-title":"Mathematics of Quantum Computation","author":"Brylinski Jean-Luc","DOI":"10.1201\/9781420035377"},{"key":"e_1_2_1_15_1","unstructured":"Yao-Min Di and Hai-Rui Wei. 2011. Elementary gates for ternary quantum logic circuit. arXiv preprint arXiv:1105.5485.  Yao-Min Di and Hai-Rui Wei. 2011. Elementary gates for ternary quantum logic circuit. arXiv preprint arXiv:1105.5485."},{"key":"e_1_2_1_16_1","first-page":"5","article-title":"Multivalued logic gates for quantum computation","volume":"62","author":"Muthukrishnan Ashok","year":"2000","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1103\/PhysRevA.67.062313","article-title":"Qutrit quantum computer with trapped ions","volume":"67","author":"Klimov A. B.","year":"2003","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_18_1","volume-title":"Stefania Sciara, Benjamin Wetzel, Yanbing Zhang, Alfonso Cino, Sai T. Chu, Brent E. Little, David J. Moss, Lucia Caspani, Jos\u00e9 Aza\u00f1a, and Roberto Morandotti.","author":"Kues Michael","year":"2017"},{"key":"e_1_2_1_19_1","unstructured":"T. B\u00e6kkegaard L. B. Kristensen N. J. S. Loft C. K. Andersen D. Petrosyan and N. T. Zinner. 2018. Superconducting qutrit-qubit circuit: A toolbox for efficient quantum gates. arXiv preprint arXiv:1802.04299.  T. B\u00e6kkegaard L. B. Kristensen N. J. S. Loft C. K. Andersen D. Petrosyan and N. T. Zinner. 2018. Superconducting qutrit-qubit circuit: A toolbox for efficient quantum gates. arXiv preprint arXiv:1802.04299."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"A. Fedorov L. Steffen M. Baur M. P. da Silva and A. Wallraff. 2011. Implementation of a Toffoli gate with superconducting circuits. Nature 481 (Dec. 2011) 170 EP. https:\/\/doi.org\/10.1038\/nature10713  A. Fedorov L. Steffen M. Baur M. P. da Silva and A. Wallraff. 2011. Implementation of a Toffoli gate with superconducting circuits. Nature 481 (Dec. 2011) 170 EP. https:\/\/doi.org\/10.1038\/nature10713","DOI":"10.1038\/nature10713"},{"key":"e_1_2_1_21_1","first-page":"9","article-title":"Maximizing the Hilbert space for a finite number of distinguishable quantum states","volume":"92","author":"Greentree Andrew D.","year":"2004","journal-title":"Phys. Rev. Lett."},{"key":"e_1_2_1_22_1","first-page":"7","article-title":"Quantum ternary parallel adder\/subtractor with partially-look-ahead carry","volume":"53","author":"Khan Mozammel H. A.","year":"2007","journal-title":"J. Syst. Archit."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Yale Fan. 2008. Applications of multi-valued quantum algorithms. arXiv preprint arXiv:0809.0932. DOI:http:\/\/dx.doi.org\/10.1109\/ISMVL.2007.3  Yale Fan. 2008. Applications of multi-valued quantum algorithms. arXiv preprint arXiv:0809.0932. DOI:http:\/\/dx.doi.org\/10.1109\/ISMVL.2007.3","DOI":"10.1109\/ISMVL.2007.3"},{"key":"e_1_2_1_24_1","article-title":"Fast quantum search algorithm for databases of arbitrary size and its implementation in a cavity QED system","author":"Li H. Y.","year":"2011","journal-title":"Phys. Lett. A 375"},{"key":"e_1_2_1_25_1","volume-title":"2011 41st IEEE International Symposium on Multiple-Valued Logic. 294--301","author":"Wang Y.","year":"2011"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1103\/PhysRevA.85.062321","article-title":"Time-efficient implementation of quantum search with qudits","volume":"85","author":"Ivanov S. S.","year":"2012","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_27_1","first-page":"1","article-title":"Factoring with qutrits: Shor\u2019s algorithm on ternary and metaplectic quantum architectures","volume":"96","author":"Bocharov Alex","year":"2017","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_28_1","volume-title":"Constructing Large Controlled Nots. (2015). Retrieved on","author":"Gidney Craig","year":"2018"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","DOI":"10.1007\/s10773-017-3389-4","article-title":"Decompositions of n-qubit Toffoli Gates with Linear Circuit","author":"He Y.","year":"2017","journal-title":"Complexity. Int. J. Theor. Phys. 56"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.52.3457"},{"key":"e_1_2_1_31_1","volume-title":"White","author":"Lanyon Benjamin P.","year":"2008"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1103\/PhysRevA.75.022313","article-title":"Efficient Toffoli gates using qudits","volume":"75","author":"Ralph T. C.","year":"2007","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_33_1","unstructured":"2019. Code for Asymptotic Improvements to Quantum Circuits via Qutrits. Retrieved from https:\/\/github.com\/epiqc\/qutrits.  2019. Code for Asymptotic Improvements to Quantum Circuits via Qutrits. Retrieved from https:\/\/github.com\/epiqc\/qutrits."},{"key":"e_1_2_1_34_1","unstructured":"Thomas G. Draper. 2000. Addition on a quantum computer. arXiv preprint quant-ph\/0008033.  Thomas G. Draper. 2000. Addition on a quantum computer. arXiv preprint quant-ph\/0008033."},{"key":"e_1_2_1_35_1","unstructured":"Craig Gidney. 2017. Factoring with n+2 clean qubits and n-1 dirty qubits. arXiv preprint arXiv:1706.07884.  Craig Gidney. 2017. Factoring with n+2 clean qubits and n-1 dirty qubits. arXiv preprint arXiv:1706.07884."},{"key":"e_1_2_1_36_1","unstructured":"Steven A. Cuccaro Thomas G. Draper Samuel A. Kutin and David Petrie Moulton. 2004. A new quantum ripple-carry addition circuit. arXiv e-prints quant-ph\/0410184.  Steven A. Cuccaro Thomas G. Draper Samuel A. Kutin and David Petrie Moulton. 2004. A new quantum ripple-carry addition circuit. arXiv e-prints quant-ph\/0410184."},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1038\/s41534-019-0140-4","article-title":"An artificial neuron implemented on an actual quantum processor. npj","volume":"5","author":"Tacchino Francesco","year":"2019","journal-title":"Quant. Inf."},{"key":"e_1_2_1_38_1","unstructured":"Francesco Tacchino. Personal Communication.  Francesco Tacchino. Personal Communication."},{"key":"e_1_2_1_39_1","first-page":"7","article-title":"Factoring using 2N + 2 qubits with Toffoli based modular multiplication","volume":"17","author":"H\u00e4ner Thomas","year":"2017","journal-title":"Quantum Inf. Comput."},{"key":"e_1_2_1_40_1","first-page":"10","article-title":"Experimental quantum error correction","volume":"81","author":"Cory D. G.","year":"1998","journal-title":"Phys. Rev. Lett."},{"key":"e_1_2_1_41_1","first-page":"5","article-title":"Toward fault-tolerant quantum computation without concatenation","volume":"63","author":"Dennis Eric","year":"2001","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_42_1","volume-title":"Gray","author":"Otten Matthew","year":"2019"},{"key":"e_1_2_1_43_1","unstructured":"2018. Quantum devices and simulators. Retrieved from https:\/\/www.research.ibm.com\/ibm-q\/technology\/devices\/.  2018. Quantum devices and simulators. Retrieved from https:\/\/www.research.ibm.com\/ibm-q\/technology\/devices\/."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1618020114"},{"key":"e_1_2_1_45_1","volume-title":"Martinis","author":"Barends R.","year":"2014"},{"key":"e_1_2_1_46_1","first-page":"2","article-title":"Fast microwave-driven three-qubit gates for cavity-coupled superconducting qubits","volume":"96","author":"Barnes Edwin","year":"2017","journal-title":"Phys. Rev. B"},{"key":"e_1_2_1_47_1","first-page":"1","article-title":"Quantum memory with millisecond coherence in circuit QED","volume":"94","author":"Reagor Matthew","year":"2016","journal-title":"Phys. Rev. B"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1103\/PhysRevLett.120.150504","article-title":"Realization of a \u039b system with metastable states of a capacitively shunted fluxonium","volume":"120","author":"Earnest N.","year":"2018","journal-title":"Phys. Rev. Lett."},{"key":"e_1_2_1_49_1","volume-title":"Circuit QED: Superconducting qubits coupled to microwave photons. Quantum Machines: Measurement and Control of Engineered Quantum Systems","author":"Girvin Steven M."},{"key":"e_1_2_1_50_1","volume-title":"Co-designing a scalable quantum computer with trapped atomic ions. npj Quantum Inf. 2","author":"Brown Kenneth R.","year":"2016"},{"key":"e_1_2_1_51_1","first-page":"5","article-title":"Comparing Zeeman qubits to hyperfine qubits in the context of the surface code: 174Yb+ and 171Yb+","volume":"97","author":"Brown Natalie C.","year":"2018","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-017-02046-6"},{"key":"e_1_2_1_53_1","volume-title":"Reversible Computation","author":"Soeken Mathias"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 2003 Design Automation Conference (IEEE Cat. No. 03CH37451)","author":"Miller D. M."}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406309","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406309","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406309","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:52Z","timestamp":1750195912000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406309"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,29]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3406309"],"URL":"https:\/\/doi.org\/10.1145\/3406309","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,29]]}}}