Sign up ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free.

In a paper by Richard Josza and Noah Linden they argue that the way state spaces of composite systems are formed is a key aspect in the benefits of quantum computers. In (classical) phase space, two systems are composed by the Cartesian product, whereas in (quantum) Hilbert space, they're composed by the tensor product. This means that the amount of physical resource (for example, 2 level systems) required to get a state space of a given dimension can be exponentially smaller for quantum over classical states.

So my question is whether all benefits of quantum mechanics in computing rely on this feature. One way of asking this is, if you restrict yourself to a paradigm where your entire state can only consist of a single qudit (ignoring the unfeasibly large number of levels this would require), would all quantum complexity classes become equal to their classical equivalents?

share|cite|improve this question
See Quantum algorithms – Trimok Jun 5 '13 at 18:21
Do you mean that you take your system to be a single harmonic oscillator (or maybe a single Rydberg atom), to the state space of which you can apply unitary transformations, maybe with some energy bound? This isn't enough to define a computational complexity class. What is the characterization of the transformations you can apply to this state? If you allow all unitary transformations, there is a single unitary transformation which takes the input to the output, and you can compute all functions. – Peter Shor Jun 5 '13 at 20:08
Classical probability distributions over strings of bits also have a tensor product structure, also of dimension $2^n$. So the difference between bits and qubits is more subtle than that. – Dan Stahlke Jun 7 '13 at 2:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.