This question is motivated by my attempt to understand quantum computing and the source of its computational power.

Quantum statest are described by complex numbers. That is, 1 qubit is described by 2 complex numbers, one for each state (actually 1 complex number, due to the constraint and the invariance).

Quantum phenomena are explained by the fact that quantum states consists of probability amplitutes (complex numbers) rather than actual probabilities (real numbers).

My question is, what if we would consider an alternative "pseudo-quantum" system, the states of which, unlike classical physics, still consist of a distribution over classical states, only it is now real-valued rather than complex-valued. What would remain of quantum computing (or "pseudo-quantum computing")?

One thing that would remain is that the number of dimensions in the system would still exponentially increase w.r.t. the number of pqubits (pseudo-qbits), which as far as I understand is one source of the power of quantum computing. That is, it would allow correlations/entanglement, contrary to classical computing, but I am not sure if this actually matters for comoutational power.


1 Answer 1


The gate set Hadamard + Toffoli is universal for quantum computation [1] and only uses real number coefficients (some negative). So all quantum algorithms can be run without involving imaginary numbers.

That being said, you will pay some representation overhead if you stick with just H+Tof. For example, you need an extra ancilla qubit and essentially every encoded operation will act on this qubit. This creates a false dependency between most operations, preventing parallelism and locality.

[1]: https://arxiv.org/abs/quant-ph/0301040


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.