Dynamic programming algorithms as quantum circuits: symmetric function realization

Dmitri A Maslov

doi:10.1117/12.541792

Translator Disclaimer

24 August 2004 Dynamic programming algorithms as quantum circuits: symmetric function realization

Dmitri A Maslov

Author Affiliations +

Proceedings Volume 5436, Quantum Information and Computation II; (2004) https://doi.org/10.1117/12.541792
Event: Defense and Security, 2004, Orlando, Florida, United States

Abstract

The work starts with a general idea of how to realize a dynamic programming algorithm as a quantum circuit. This realization is not tied to a specific design model, technology or a class of dynamic algorithms, it shows an approach for such synthesis. As an illustration of the efficiency of this approach, the class of all multiple-output symmetric functions is realized in a dynamic programming algorithm manner as a reversible circuit of Toffoli type elements (NOT, CNOT, and Toffoli gates). The garbage and quantum cost (found based on Barenco et al. paper) of the presented implementation are calculated and compared to the costs of previously described reversible synthesis methods. The summary of results of this comparison is as follows. The quantum cost of the proposed method is less than the quantum cost of any other reported systematic approach. The garbage is usually lower, except for comparison with the synthesis methods, whose primary goal is synthesis with theoretically minimal garbage. The presented algorithm application to the symmetric function synthesis results in circuits suitable for quantum technology realizations.

Citation Download Citation

Dmitri A Maslov "Dynamic programming algorithms as quantum circuits: symmetric function realization", Proc. SPIE 5436, Quantum Information and Computation II, (24 August 2004); https://doi.org/10.1117/12.541792

ACCESS THE FULL ARTICLE