A characterization of important algorithms for quantum-dot cellular automata

Feature sizes in chip manufacturing are becoming so small that quantum mech anical behavior will. soon have a deleterious effect on the function of dev ices. Quantum-dot cellular automats (QDCA) have been proposed as computing devices which are helped, rather than hindered, by the quantum behavior of electrons. QDCA compute by relaxing to a configuration of minimal energy. P reviously, it has been shown that a quantum-dot device may not compute prop erly if all of its relaxed configurations are not equal in energy level. Su ch an automaton is termed unbalanced. A necessary condition for an automato n to be balanced is that the number of distinguished configurations with mi nimum energy should equal the number of input combinations the automaton ha ndles. Does an efficient algorithm for determining the number of distinguis hed ground states exist? If so, it will be difficult to find, as such an al gorithm is shown to be NP-hard. Furthermore, the related problem of determi ning the minimum energy level of arbitrary automata is also shown to be NP- hard, These results have important implications for simulating and analyzin g QDCA on conventional computers. (C) 1999 Elsevier Science Inc. All rights reserved.