Quantum computation: entanglement, chaos and decoherence

Quantum algorithms for complex dynamics in the regime of classical and quantum chaos are discussed. It is shown that quantum and classical chaotic maps can be simulated on a quantum computer in a polynomial number of gates for exponentially many quantum states or classical trajectories. For classical chaotic dynamics there is exponential growth of classical (last bit) errors, while the quantum errors in gate operations shown to grow only polynomially with time. Recent results on entanglement properties in such algorithms and chaos-assisted tunneling will be also discussed.