Universality of Entanglement and Quantum Computation Complexity

Details Universality of Entanglement and Quantum Computation Complexity Universality of Entanglement and Quantum Computation Complexity

2003-11-05

arxiv.org/abs/quant-ph/0311017v3

Phys.Rev. A69 (2004) 052308

Physics

Quantum Physics

30 pages, 17 figures, accepted for publication in PRA

Scientific paper

10.1103/PhysRevA.69.052308

We study the universality of scaling of entanglement in Shor's factoring algorithm and in adiabatic quantum algorithms across a quantum phase transition for both the NP-complete Exact Cover problem as well as the Grover's problem. The analytic result for Shor's algorithm shows a linear scaling of the entropy in terms of the number of qubits, therefore difficulting the possibility of an efficient classical simulation protocol. A similar result is obtained numerically for the quantum adiabatic evolution Exact Cover algorithm, which also shows universality of the quantum phase transition the system evolves nearby. On the other hand, entanglement in Grover's adiabatic algorithm remains a bounded quantity even at the critical point. A classification of scaling of entanglement appears as a natural grading of the computational complexity of simulating quantum phase transitions.

Affiliated with

Also associated with

No associations

Rating

Universality of Entanglement and Quantum Computation Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Universality of Entanglement and Quantum Computation Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Universality of Entanglement and Quantum Computation Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-628519