No interactions do not destroy superposition. Example, if you want to rotate a photon's polarization non-destructively pass it through a solution of dextrose. This is a unitary operation thus preserving superpositions of polarizations.
Hermitian operators correspond to measurements. These generally are the final steps in a quantum computation and they are the ones which "destroy" superposition but they also create superpositions as well.
Superposition is just the resolution of a single quantum mode in a different basis. For example a photon measured to be vertically polarized (vs horizontal) is in a superposition of being obliquely polarized at +45deg and -45deg. Likewise a photon polarized at +45deg will be in a superposition of vertical and horizontal polarizations. We can mix in other ways using complex phases so that we can also resolve say either cw circular polarization or ccw circular polarization as superposition of V and H polarization modes (and vis versa).
Thus you create a superposition with respect to one set of basis modes by making a measurement with respect to another set of basis modes. Superposition is not really a property of the quantum system but rather a relationship between different sets of compatible measurements. (compatible = mutually commuting within each of the sets but not between the different sets)
Before trying to understand entanglement in too much detail you should first get very clear on the basics of superposition, unitary evolution, and measurement associated with hermitian observables.
Entanglement involves sharply measuring/preparing an ensemble of a composite quantum system made up of many quantum subsystems in a way which is not compatible with certain individual measurements on anyone sub-system. For example you can determine (,measure,prepare) the total spin of a pair of electrons to be zero (singlet mode) which means each component of spin must be opposite = anti-correlated between the two. But in so doing you "erase" any information about what values any given component of spin will have for anyone of the electrons.
Superposition is part of what makes quantum computation able to improve on classical digital computers but as to how you must look on a case by case basis. Each quantum computation is in a sense custom built for the specific algorithm.
The ability to (theoretically) beat classical digital computers is no great mystery. For many algorithms (such as sorting http://en.wikipedia.org/wiki/Spaghetti_sort" ) there are analogue methods which in theory beat digital methods.