The Dynamics of Entanglement in the Adiabatic Search and Deutsch Algorithms

Abstract

The goal of this paper is to study the effect of entanglement on the running time of a quantum computation. Adiabatic quantum computation is suited to this kind of study, since it allows us to explicitly calculate the time evolution of the entanglement throughout the calculation. On the other hand however, the adiabatic formalism makes it impossible to study the roles of entanglement and fidelity separately, which means that results have to be interpreted carefully. We study two algorithms: the search algorithm and the Deutsch-Jozsa algorithm. We find some evidence that entanglement can be considered a resource in quantum computation.

arXiv comment29 pages, 25 figures

References in corpus (15)

• Efficient classical simulation of slightly entangled quantum computations
• Quantifying Entanglement
• Quantum Search by Local Adiabatic Evolution
• Entanglement Entropy dynamics in Heisenberg chains
• Inconsistency in the application of the adiabatic theorem
• Implementation of quantum search algorithm using classical Fourier optics
• Quantum Computing Without Entanglement
• Universality of Entanglement and Quantum Computation Complexity
• Optimal Entanglement Witnesses for Qubits and Qutrits
• Two qubits entanglement dynamics in a symmetry-broken environment
• Adiabatic Quantum Computation and Deutsch's Algorithm
• Quantum circuit implementation of the Hamiltonian versions of Grover's algorithm
• Entanglement dynamics for two interacting spins
• Entangling capacity of global phases and implications for Deutsch-Jozsa algorithm
• Entanglement and Adiabatic Quantum Computation