Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity

Physics – Quantum Physics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

18 pages, 1 figure. The operation R is now really a quantum operation (it was not before); corrected some typos, III.B more re

Scientific paper

We show that there exists a universal quantum Turing machine (UQTM) that can simulate every other QTM until the other QTM has halted and then halt itself with probability one. This extends work by Bernstein and Vazirani who have shown that there is a UQTM that can simulate every other QTM for an arbitrary, but preassigned number of time steps. As a corollary to this result, we give a rigorous proof that quantum Kolmogorov complexity as defined by Berthiaume et al. is invariant, i.e. depends on the choice of the UQTM only up to an additive constant. Our proof is based on a new mathematical framework for QTMs, including a thorough analysis of their halting behaviour. We introduce the notion of mutually orthogonal halting spaces and show that the information encoded in an input qubit string can always be effectively decomposed into a classical and a quantum part.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov 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 Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-307587

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.