Share Email Print

Proceedings Paper

Dynamic programming algorithms as quantum circuits: symmetric function realization
Author(s): Dmitri A Maslov
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 24 August 2004
PDF: 8 pages
Proc. SPIE 5436, Quantum Information and Computation II, (24 August 2004); doi: 10.1117/12.541792
Show Author Affiliations
Dmitri A Maslov, Univ. of Victoria (Canada)

Published in SPIE Proceedings Vol. 5436:
Quantum Information and Computation II
Eric Donkor; Andrew R. Pirich; Howard E. Brandt, Editor(s)

© SPIE. Terms of Use
Back to Top