A calculation on a quantum computer that cannot be in practice be performed on a conventional computer. Either the number of CPU steps required or the necessary computer memory increases exponentially with the size of the input. This means that for all but the simplest cases, the calculation becomes unfeasible on a real machine using only conventional digital hardware.
