Translator Disclaimer
24 August 2004 Dynamic programming algorithms as quantum circuits: symmetric function realization
Author Affiliations +
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.
© (2004) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Dmitri A Maslov "Dynamic programming algorithms as quantum circuits: symmetric function realization", Proc. SPIE 5436, Quantum Information and Computation II, (24 August 2004);

Back to Top