The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
Optimal synthesis of multiple output Boolean functions using a set of quantum gates by symbolic reachability analysis
Abstract
This paper proposes an approach to optimally synthesize quantum circuits by symbolic reachability analysis, where the primary inputs and outputs are basis binary and the internal signals can be nonbinary in a multiple-valued domain. The authors present an optimal synthesis method to minimize quantum cost and some speedup methods with nonoptimal quantum cost. The methods here are applicable to small reversible functions. Unlike previous works that use permutative reversible gates, a lower level library that includes nonpermutative quantum gates is used here. The proposed approach obtains the minimum cost quantum circuits for Miller gate, half adder, and full adder, which are better than previous results. This cost is minimum for any circuit using the set of quantum gates in this paper, where the control qubit of 2-qubit gates is always basis binary. In addition, the minimum quantum cost in the same manner for Fredkin, Peres, and Toffoli gates is proven. The method can also find the best conversion from an irreversible function to a reversible circuit as a byproduct of the generality of its formulation, thus synthesizing in principle arbitrary multi-output Boolean functions with quantum gate library. This paper constitutes the first successful experience of applying formal methods and satisfiability to quantum logic synthesis.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Quantum Computation and Quantum Information
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
Quantum computation and quantum information
Law, J. (2001) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/505482.505499 · Cited by 18,842
Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
Einstein, A., Podolsky, B., & Rosen, N. (1935) · Physical Review · doi:10.1103/physrev.47.777 · Cited by 16,654
Graph-Based Algorithms for Boolean Function Manipulation
Bryant (1986) · IEEE Transactions on Computers · doi:10.1109/tc.1986.1676819 · Cited by 8,891
Elementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311
Clarke, E., McMillan, K., Campos, S., & Hartonas-Garmhausen, V. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-61474-5_93 · Cited by 2,839
Fredkin, E., & Toffoli, T. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf01857727 · Cited by 1,896
Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
Vandersypen, L. M. K., Steffen, M., Breyta, G., Yannoni, C. S., Sherwood, M. H., & Chuang, I. L. (2001) · Nature · doi:10.1038/414883a · Cited by 1,738
McMillan, K. L. (1993) · Springer eBooks · doi:10.1007/978-1-4615-3190-6 · Cited by 1,677
Toffoli, T. (1980) · Lecture Notes in Computer Science · doi:10.1007/3-540-10003-2_104 · Cited by 1,523 · cited 1×
“R EVERSIBLE logic [1] plays an important role in the 30 synthesis of quantum computing circuits [2], [3].”
Fredkin, E., & Toffoli, T. (2001) · Cited by 1,302
Quantum computational networks
Deutsch, D. E. (1989) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1989.0099 · Cited by 1,270
Reversible logic and quantum computers
Peres, A. (1985) · Physical Review A · doi:10.1103/physreva.32.3266 · Cited by 892
Symbolic model checking using SAT procedures instead of BDDs
Biere, A., Cimatti, A., Clarke, E. M., Fujita, M., & Zhu, Y. (1999) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1145/309847.309942 · Cited by 752
Synthesis of reversible logic circuits
Shende, V. V., Prasad, A. K., Markov, I. L., & Hayes, J. P. (2003) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2003.811448 · Cited by 568
Realizable Universal Quantum Logic Gates
Sleator, T., & Weinfurter, H. (1995) · Physical Review Letters · doi:10.1103/physrevlett.74.4087 · Cited by 515
A transformation based algorithm for reversible logic synthesis
Miller, D. M., Maslov, D., & Dueck, G. W. (2003) · Proceedings of the 40th annual Design Automation Conference · doi:10.1145/775832.775915 · Cited by 493
Gruska, J. (1999) · Cited by 463
BerkMin: A fast and robust SAT-solver
Goldberg, E. I., & Novikov, Y. (2003) · Design, Automation, and Test in Europe · doi:10.1109/date.2002.998262 · Cited by 363
Implementation of a quantum algorithm on a nuclear magnetic resonance quantum computer
Jones, J. A., & Mosca, M. (1998) · The Journal of Chemical Physics · doi:10.1063/1.476739 · Cited by 324
Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate
Smolin, J. A., & DiVincenzo, D. P. (1996) · Physical Review A · doi:10.1103/physreva.53.2855 · Cited by 276
Benefits of Bounded Model Checking at an Industrial Setting
Copty, F., Fix, L., Fraer, R., Giunchiglia, E., Kamhi, G., Tacchella, A., & Vardi, M. Y. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44585-4_43 · Cited by 189
Transformation rules for designing CNOT-based quantum circuits
Iwama, K., Kambayashi, Y., & Yamashita, S. (2002) · Proceedings of the 39th conference on Design automation - DAC '02 · doi:10.1145/513918.514026 · Cited by 164
Symbolic model checking using SAT procedures instead of BDDs
Biere, A., Cimatti, A., Clarke, E. M., Fujita, M., & Zhu, Y. (2003) · Proceedings - ACM IEEE Design Automation Conference · doi:10.1109/dac.1999.781333 · Cited by 156
Basic Concepts in Quantum Computation
EKERT, A. K., Hayden, P. M., & Inamori, H. (2007) · Springer eBooks · doi:10.1007/3-540-45338-5_10 · Cited by 124
Majority-based reversible logic gates
Yang, G., Hung, W. N. N., Song, X., & Perkowski, M. A. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.12.026 · Cited by 75
Self-citationSpectral and two-place decomposition techniques in reversible logic
Miller, D. M. (2003) · IEEE International Midwest Symposium on Circuits and Systems (MWSCAS) · doi:10.1109/mwscas.2002.1186906 · Cited by 58
Vos, A. D. (1999) · Progress in Quantum Electronics · doi:10.1016/s0079-6727(99)00002-6 · Cited by 51
Transformation rules for designing CNOT-based quantum circuits
Iwama, K., Kambayashi, Y., & Yamashita, S. (2002) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac.2002.1012662 · Cited by 50
Algebraic Characterization of Reversible Logic Gates
Xiaoyu Song, B., Yang, G., Perkowski, M. A., & Wang, Y. (2004) · Theory of Computing Systems · doi:10.1007/s00224-004-1166-2 · Cited by 31
Self-citation
Cited by
A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits
Amy, M., Maslov, D., Mosca, M., & Roetteler, M. (2013) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2013.2244643 · Cited by 549
“[15] considered a problem somewhat closer to”
RevLib: An Online Resource for Reversible Functions and Reversible Circuits
Wille, R., Gro, D., Teuber, L., Dueck, G. W., & Drechsler, R. (2008) · 38th International Symposium on Multiple Valued Logic (ismvl 2008) · doi:10.1109/ismvl.2008.43 · Cited by 495
BDD-based synthesis of reversible logic for large functions
Wille, R., & Drechsler, R. (2009) · Proceedings of the 46th Annual Design Automation Conference · doi:10.1145/1629911.1629984 · Cited by 323
Synthesis and optimization of reversible circuits—a survey
Saeedi, M., & Markov, I. L. (2013) · ACM Computing Surveys · doi:10.1145/2431211.2431220 · Cited by 298
Metadata
- Authors
- Hung, W. N. N., Song, X., Yang, G., Yang, J., & Perkowski, M.
- Venue
- IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Published
- 2006-09
- Volume
- 25
- Issue
- 9
- Pages
- 1652-1663
- ISSN
- 0278-0070 (ISSN-L)
- OpenAlex
- W2144272791
- Cited by
- 261
- References
- 30
- FWCI
- 10.72
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.