patternModerate
Will the future quantum computers use the binary, ternary or quaternary numeral system?
Viewed 0 times
thesystemquaternaryfuturecomputerswillbinaryternarynumeraluse
Problem
Our current computers use bits, so they use the binary numeral system. But I heard that the future quantum computers will use qubits instead of simple bits.
Since in the word "qubit" there is the word "bi" I first thought that this meant that quantum computers would use binary (base 2).
But then I heard that qubits had three possible states: 0, 1, or a superposition of 0 and 1. So I then thought that this must mean that they will use ternary (base 3).
But then I saw that one qubit can hold as much information as two bits. So I thought that this maybe mean that they will use quaternary (base 4).
So which numeral system will the future quantum computers use: binary, ternary or quaternary?
Since in the word "qubit" there is the word "bi" I first thought that this meant that quantum computers would use binary (base 2).
But then I heard that qubits had three possible states: 0, 1, or a superposition of 0 and 1. So I then thought that this must mean that they will use ternary (base 3).
But then I saw that one qubit can hold as much information as two bits. So I thought that this maybe mean that they will use quaternary (base 4).
So which numeral system will the future quantum computers use: binary, ternary or quaternary?
Solution
The other answers are nice, but none address the question: what numeric base(s) might quantum computers use? I will answer in two parts: first, the question is a little subtle, and second, you may use any numeric base, and then you work with qutrits or in general with qudits, which lead to qualitatively new intuitions! Or at any rate, I will try to make the case that they do.
A quantum bit isn't just a $0$ or a $1$, it's a bit more complex than that. For example, a quantum bit may be in the state $\sqrt{\frac{1}{4}}|0\rangle+\sqrt{\frac{3}{4}}|1\rangle$. When measured, you will measure the outcome $0$ with probability $\frac{1}{4}$ and the outcome $1$ with probability $\frac{3}{4}$. The 'superposition' you talked about is $\sqrt{\frac{1}{2}}|0\rangle+\sqrt{\frac{1}{2}}|1\rangle$, but in general any pair of complex numbers $a$ and $b$ will do, as long as $a^2+b^2=1$. If you have three qubits, then you can entangle them, and the state will be
$$a_0|000\rangle + a_1|001\rangle+a_2|010\rangle+a_3|011\rangle+a_4|100\rangle +a_5|101\rangle+a_6|110\rangle +a_7|111\rangle$$
But when you measure this three-qubit system, your measurement outcome is one out of these 8 states, that is, three bits. This is this really weird dichotomy where on the one hand quantum systems seem to have this exponential state space, but on the other hand we only seem to be able to 'get at' a logarithmic part of the state space. In 'Quantum Computing Since Democritus', Scott Aaronson probes this question by matching off several complexity classes to try and understand how much of this exponential state space we can exploit for computation.
Having said that, there is an obvious complaint to the answer above: all the notation is in binary. Qubits are in a superposition of two base states, and entangling them doesn't change that much, because three qubits are in a superposition of $2^3$ base states. It's a legitimate complaint, because one usually thinks of $\texttt{unsigned int}$ as a number, and only remembers that it is implemented as a 32-bit string as an afterthought.
Enter the qutrit. It is a vector in $\mathbb{C}^3$, in other words, it consists of three base states rather than two. You operate on this vector with a $3\times 3$ matrix, and all the usual things done in quantum computing don't change much, because any operation expressed in terms of qutrits can be expressed in terms of qudits, so it's really just syntactic sugar. But some problems are much easier to write down and/or think about when expressed as qudits instead of entangled qubits. For example, a variation of the Deutsch-Josza problem might ask, given an oracle for a function $f\colon \{0,\ldots, kn-1\}\rightarrow \{0,\ldots, k-1\}$, is this function constant or balanced, given that one is promised to be the case? This function naturally takes one $k$-qudit register as input. To solve it, you must apply a Fourier transform to this $k$-qudit, like so: (if this goes over your head, don't worry, it's just for illustration)
$$|a\rangle \mapsto \sum_{u=0}^{k-1}e^{i2\pi\frac{au}{k}}|u\rangle$$
If you want to express this in binary, you end up with a gate that does this on numbers $0\ldots k-1$ and acts trivially (does nothing) on all numbers $\geq k$, which is slightly less contrived than doing it this way. Similarly, consider a Bernstein-Vazirani variation where the oracle computes an in-product in some radix $r$. If $r=2$, then we know how to do it. But if $r=5$, the problem is much easier to solve by hand using several $5$-qudit registers. Some problems are easier if you have several different qudit registers, e.g. one $5$-qudit register and one $2$-qudit register.
In summary, yes, you are free to consider other numeric bases, and in the right setting that will make your life easier, for the same reason that thinking about numbers in terms other than their binary expansion helps you with normal computers. I felt compelled to answer because while most answers explained that a qubit has something to do with two base states when measuring but infinite in principle, no answer mentioned that the OPs suggestion of using other bases is legitimate and in fact really happens (for example, in Quantum walks on graphs, Aharonov et al. use a subroutine that takes a qubit and an $n$-qudit as input)
A quantum bit isn't just a $0$ or a $1$, it's a bit more complex than that. For example, a quantum bit may be in the state $\sqrt{\frac{1}{4}}|0\rangle+\sqrt{\frac{3}{4}}|1\rangle$. When measured, you will measure the outcome $0$ with probability $\frac{1}{4}$ and the outcome $1$ with probability $\frac{3}{4}$. The 'superposition' you talked about is $\sqrt{\frac{1}{2}}|0\rangle+\sqrt{\frac{1}{2}}|1\rangle$, but in general any pair of complex numbers $a$ and $b$ will do, as long as $a^2+b^2=1$. If you have three qubits, then you can entangle them, and the state will be
$$a_0|000\rangle + a_1|001\rangle+a_2|010\rangle+a_3|011\rangle+a_4|100\rangle +a_5|101\rangle+a_6|110\rangle +a_7|111\rangle$$
But when you measure this three-qubit system, your measurement outcome is one out of these 8 states, that is, three bits. This is this really weird dichotomy where on the one hand quantum systems seem to have this exponential state space, but on the other hand we only seem to be able to 'get at' a logarithmic part of the state space. In 'Quantum Computing Since Democritus', Scott Aaronson probes this question by matching off several complexity classes to try and understand how much of this exponential state space we can exploit for computation.
Having said that, there is an obvious complaint to the answer above: all the notation is in binary. Qubits are in a superposition of two base states, and entangling them doesn't change that much, because three qubits are in a superposition of $2^3$ base states. It's a legitimate complaint, because one usually thinks of $\texttt{unsigned int}$ as a number, and only remembers that it is implemented as a 32-bit string as an afterthought.
Enter the qutrit. It is a vector in $\mathbb{C}^3$, in other words, it consists of three base states rather than two. You operate on this vector with a $3\times 3$ matrix, and all the usual things done in quantum computing don't change much, because any operation expressed in terms of qutrits can be expressed in terms of qudits, so it's really just syntactic sugar. But some problems are much easier to write down and/or think about when expressed as qudits instead of entangled qubits. For example, a variation of the Deutsch-Josza problem might ask, given an oracle for a function $f\colon \{0,\ldots, kn-1\}\rightarrow \{0,\ldots, k-1\}$, is this function constant or balanced, given that one is promised to be the case? This function naturally takes one $k$-qudit register as input. To solve it, you must apply a Fourier transform to this $k$-qudit, like so: (if this goes over your head, don't worry, it's just for illustration)
$$|a\rangle \mapsto \sum_{u=0}^{k-1}e^{i2\pi\frac{au}{k}}|u\rangle$$
If you want to express this in binary, you end up with a gate that does this on numbers $0\ldots k-1$ and acts trivially (does nothing) on all numbers $\geq k$, which is slightly less contrived than doing it this way. Similarly, consider a Bernstein-Vazirani variation where the oracle computes an in-product in some radix $r$. If $r=2$, then we know how to do it. But if $r=5$, the problem is much easier to solve by hand using several $5$-qudit registers. Some problems are easier if you have several different qudit registers, e.g. one $5$-qudit register and one $2$-qudit register.
In summary, yes, you are free to consider other numeric bases, and in the right setting that will make your life easier, for the same reason that thinking about numbers in terms other than their binary expansion helps you with normal computers. I felt compelled to answer because while most answers explained that a qubit has something to do with two base states when measuring but infinite in principle, no answer mentioned that the OPs suggestion of using other bases is legitimate and in fact really happens (for example, in Quantum walks on graphs, Aharonov et al. use a subroutine that takes a qubit and an $n$-qudit as input)
Context
StackExchange Computer Science Q#29722, answer score: 18
Revisions (0)
No revisions yet.