  We investigate macroscopic entanglement of quantum states in quantum
computers, where we say a quantum state is entangled macroscopically if the
state has superposition of macroscopically distinct states. The index $p$ of
the macroscopic entanglement is calculated as a function of the step of the
computation, for Grover's quantum search algorithm and Shor's factoring
algorithm. It is found that whether macroscopically entangled states are used
or not depends on the numbers and properties of the solutions to the problem to
be solved. When the solutions are such that the problem becomes hard in the
sense that classical algorithms take more than polynomial steps to find a
solution, macroscopically entangled states are always used in Grover's
algorithm and almost always used in Shor's algorithm. Since they are
representative algorithms for unstructured and structured problems,
respectively, our results support strongly the conjecture that quantum
computers utilize macroscopically entangled states when they solve hard
problems much faster than any classical algorithms.
