×

Binary superposed quantum decision diagrams. (English) Zbl 1201.81037

The key theme of this work is the binary superposed decision diagrams or BSQDDs for short. The basic idea that lies behind BSQDDs is to represent a quantum superposition as a decision diagram where each node on each branch of a BSQDD corresponds to a gate. Each of those gates is controlled by the path originated from the root of the decision diagram. Each branch of BSQDD represents a different part of the desired quantum superposition. It is proved in Theorem 9 that, given a sufficient set of gates, a BSQDD enables to represent any quantum superposition. In this sense BSQDDs are universal. Two transformation rules to manipulate and reduce BSQDDs are derived. The canonical form for BSQDDs is defined. It is demonstrated that BSQDDs have some advantages to initialize quantum superpositions compared to the existing approaches. One of them is that BSQDDs do not require the ancilla qubits. Several examples of BSQDDs are discussed.

MSC:

81P68 Quantum computation
81P10 Logical foundations of quantum mechanics; quantum logic (quantum-theoretic aspects)

Software:

QMDD
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdaollahi, A., Pedram, M.: Analysis and synthesis of quantum circuits by using quantum decision diagrams. Design, Automation and Test in Europe (2006)
[2] Biron, D., Biham, O., Biham, E., Grassl, M., Lidar, D.A.: Generalized grover search algorithm for arbitrary initial amplitude distribution. Quantum Comput. Quantum Commun. 1509/1999, 140–147 (1999) · Zbl 0945.68037
[3] Bryant R.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Comp. C-35, 677–691 (1986) · Zbl 0593.94022 · doi:10.1109/TC.1986.1676819
[4] Ezhov A., Nifanova, A., Ventura, D.: Quantum associative memory with distributed queries. Inf. Sci. (2000) · Zbl 0980.68044
[5] Grover, L.: A fast quantum mechanical algorithm for database search. In: Annual ACM Symposium on Theory of Computing (1996) · Zbl 0922.68044
[6] Long G., Sun Y.: Efficient scheme for initializing a quantum register with an arbitrary superposed state. Phys. Rev. A. 64, 014303 (2001) · doi:10.1103/PhysRevA.64.014303
[7] Miller, D., Thornton, M.: QMDD: A decision diagram structure for reversible and quantum circuits. In: IEEE International Symposium on Multiple Valued Logic (2006)
[8] Rosenbaum, D., Perkowski, M.: Superposed quantum state initialization using disjoint prime implicants. In: IEEE International Symposium on Multiple Valued Logic (2008)
[9] Rosenbaum D.J., Perkowski M.A.: Extended superposed quantum state initialization using disjoint prime implicants. Phys. Rev. A. 79, 052310 (2009) · doi:10.1103/PhysRevA.79.052310
[10] Schulman, L., Vazirani, U.: Molecular scale heat engines and scalable quantum computation. In: Annual ACM Symposium on Theory of Computing (1999) · Zbl 1345.81028
[11] Ventura D., Martinez T.: Initializing the amplitude distribution of a quantum state. Found. Phys. Lett. 12, 547–559 (1999) · doi:10.1023/A:1021695125245
[12] Ventura D., Martinez T.: Quantum associative memory. Inf. Sci. 124, 273–296 (2000) · Zbl 02180351 · doi:10.1016/S0020-0255(99)00101-2
[13] Viamontes G., Markov I., Hayes J.: Graph-based simulation of quantum computation in the density matrix representation. Quantum Inf. Comput. 5, 113–130 (2004) · Zbl 1213.81105
[14] Viamontes, G., Rajagopalan, M., Markov, I., Hayes, J.: Gate-level simulation of quantum circuits. In: Conference on Asia South Pacific Design Automation (2003) · Zbl 1130.81341
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.