<p>Actually the usual RAM model is just this approach taken into extreme: each "storage unit" has as many as $\textrm{poly}(n)$ possible states (instead of just 2 states). We assume that each memory word can store $O(\log n)$ bits and word-operations have unit cost.</p>

<p>Cf. <a href="https://cstheory.stackexchange.com/questions/26/complexity-of-the-fisher-yates-shuffle-algorithm">this question</a>.</p>

CC BY-SA 2.5
2010-09-01T23:31:20.427Z
2010-09-01T23:31:20.427Z
2017-04-13T12:32:28.053Z
Jukka Suomela
<p>Certainly in the context of quantum computation systems of dimension 3 or more have been looked at. These are known as qudits in general, and qutrits for 3 level systems. The motivation here has mostly been the available physical systems, rather than any expectation of a significant change in computational power. Indeed in quantum systems it is very easy to see that there is no such advantage: Evolution in quantum systems is described by unitary operations which can be associated with the Lie group su(D), where D is the total dimensionality of the system. Given entangling gates between subsystems, together with individual control over these local subsystems, it is known that it is always possible to approximate any such operator, independent of the dimensionality of the local systems. Obviously, if you can reach all unitary operations on D dimensions, then you can reach all of the ones on $d&lt;D$ dimensions. So, you can use, for example 2 qutrits to replace 3 qubits, or 4 qubits to replace 3 qutrits, with only constant overhead.</p>

<p>With this in mind, the relationship between qutrits and qubits versus trits and bits is similar, and the level of interest on a theoretical level has been fairly similar. It is really in the context of physical implementations that qutrits attract interest, since quantum computing has not really settled on a dominant architecture yet, and there are plenty of systems with local dimensionality > 2.</p>

<p>You may want to have a look into what are called continuous variable systems, which are a type of system considered in quantum computation which have an infinite number of local dimensions (position is an example of a continuous variable quantity). Such systems do actually exist, and are fundamentally different from analog computers due to the quantization of energy levels.</p>

CC BY-SA 3.0
2010-09-01T23:12:03.897Z
2012-11-23T17:11:03.727Z
2012-11-23T17:11:03.727Z
Joe Fitzsimons
<p>Ternary logic attracted attention in mid 70s and 80s, but I guess theorists are not interested by it since advantages are not that incredible and because it is more or less the same thing that classical logic (from the conceptual point of view).</p>

<p>However, if you read a paper such as this one: <a href="http://www.ee.bgu.ac.il/~kushnero/ternary/Using%20CMOS%20gates/Low%20power%20dissipation%20MOS%20ternary%20logic%20family.pdf" rel="nofollow">Low power dissipation MOS ternary logic family</a>,you will find many references in it about the interest in practice (but keep in mind that it was practical interests of the 80s).</p>

CC BY-SA 2.5
2010-09-01T21:30:50.743Z
Thanks, I guess I should get back into my hot-tub time machine now...
Shane
CC BY-SA 2.5
2010-09-01T21:21:51.083Z
2010-09-01T21:21:51.083Z
Sylvain Peyronnet
<p>why was my post deleted? I didn't do anything against the guidelines, i read the guidelines page!</p>

<p>I'll post this AGAIN. The only way to get ternary logic to work in a computer, is to first understand that you must have 3 magnetic fields, from a 3 terminal powersource. This is a simple negative>positive + a 3rd option.</p>

<p>But first, to whoever deleted my prior post, just because you do not enjoy reading the responses of people who can actually think for themselves and outside the box doesn't mean that person broke any rules. To others reading this, I posted a very good and informative response explaining how in theory a 3 state power system can work.</p>

<p>It's very obvious to me you can have a 3 terminal (but still 2 pole) battery. All you need is Zinc for negative and copper for positive (very common, of course) and the 3rd is aluminum. In order for me to explain how it's possible to have a 3rd type of electric current i first have to explain how we understand color scales. Take the green, red and blue color scale. Doesn't matter which color you want to with. So we will say in this case red is positive and blue is negative. What are these colors combined? Purple! So what is the opposite of purple? GREEN! This is how you figure out the other metal. Combine zinc and copper and guess what, you have brass, what the ancient greeks were very fond of at some point in their time. So, just like we take purple and look at it's opposite, we find that the opposite of brass is aluminum. Now you have your third terminal's alkaline.</p>

<p>Ok, so now that we have that out of the way. It is now possible to have a 3rd current. What will happen, due to the aluminum being weaker than the zinc negative, but stronger than the copper positive, if you place the aluminum 3rd terminal in a position that makes all three triangular in placement, the zinc's stronger energy will obviously flow to both of the terminals. But in the case of zinc to aluminum, the electrons will flow around the metal, creating a circular field, instead of a forward one. The reason for this is because of the aluminum's stronger magnetic field relative to the copper. So it's "pushing" on the copper and is being pushed by the zinc. If you put them in your battery correctly, the 3rd terminal will by default have a circular magnetic field, and so will the wire connected to it.</p>

<p>So why was my post deleted? Can you prove anything I just said wrong?</p>

CC BY-SA 3.0
2014-10-31T19:15:02.033Z
It may or may not be wrong, but it is definitely off-topic.
Emil Jeřábek
CC BY-SA 3.0
2014-10-31T18:47:40.697Z
2014-10-31T20:16:21.320Z
2014-10-31T20:16:21.320Z
iamverysmart234
<p>Computing with trits instead of bits is like computing with Turing machines that have an alphabet size of 3 instead of an alphabet size of 2.  Increasing the alphabet size like that (not necessarily 2 to 3, but 2 to larger) can permit a speedup in running time, and a compression in the use of space.  (See <a href="http://en.wikipedia.org/wiki/Linear_speedup_theorem">http://en.wikipedia.org/wiki/Linear_speedup_theorem</a> for some initial discussion.)  Note that these improvements are fairly "minimal" -- they won't make an intractable problem tractable.  (If you use an intractably large alphabet instead of computing over bits, that's "cheating," because then you are just transferring the hardness from one part of the computation to another.)</p>

<p>Qubits at least appear to have a fundamentally different "character" from bits or trits.  The state of a qubit (or, more generally, a quDit, "quantum digit") is a collection of probability amplitudes that associates the qubit to some extent with each possible state.  Bits, trits, etc., are crisply in one state, the end.  In particular, if Factoring is not in polynomial time, then there exists no ptime algorithm over trits that factor integers, while there does exist a quantum algorithm over qudits that factors integers.</p>

<p><a href="http://en.wikipedia.org/wiki/Qubit">http://en.wikipedia.org/wiki/Qubit</a></p>

CC BY-SA 2.5
2010-09-01T23:23:28.193Z
Well, there is a quantum algorithm for factoring with qubits as well as qudits, so actually the relationship between qudits and qubits vs trits and bits is pretty similar.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-01T23:46:46.583Z
I agree with you, I must have been unclear.  I meant to say that just because there is a PTIME quantum algorithm over qubits, this doesn't mean there's a classical PTIME algorithm for the same problem over bits.  Sorry for the confusion.
Aaron Sterling
CC BY-SA 2.5
2010-09-02T00:01:59.593Z
Sorry, my mistake.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-01T21:12:36.483Z
2010-09-01T21:12:36.483Z
Aaron Sterling
<p>Binary math is at the heart of most computing, in large part because of the ease with which two energy states can be achieved.  I have always thought that having more states could improve computing power (e.g. using a <a href="http://en.wikipedia.org/wiki/Trit" rel="noreferrer">trit</a> instead of a bit), but there is a seeming lack of attention being paid to the problem.</p>

<p>Some work has been done in the quantum computing area using qubits to achieve more than the normal two energy levels (see, for example, <a href="http://www.sciencemag.org/cgi/content/abstract/sci;325/5941/722?maxtoshow=&amp;HITS=10&amp;hits=10&amp;RESULTFORMAT=&amp;fulltext=Matthew+Neeley&amp;searchid=1&amp;FIRSTINDEX=0&amp;resourcetype=HWCIT" rel="noreferrer">the recent effort at UCSB</a>).</p>

<p>What advances have been made toward having <a href="http://en.wikipedia.org/wiki/Ternary_computer" rel="noreferrer">ternary</a> (or greater) computers, and what are the primary the implications of the extra states?</p>

CC BY-SA 3.0
2014-10-31T14:09:51.717Z
A computer based on ternary logic (*this is not the same thing as trits!*) was built in the Soviet Union in the 50's: [Setun](https://en.wikipedia.org/wiki/Setun).
Bruno
CC BY-SA 3.0
2014-10-31T17:39:12.047Z
We do know that it's not possible to make a reversible universal gate using 2 inputs and 2 outputs on a binary computer, but it is possible in ternary, in fact [about 97% of possible ternary 2 input 2 output gates are universal](http://goo.gl/WP0A3c). Also see [this question](http://cstheory.stackexchange.com/questions/1794/circuit-lower-bounds-over-arbitrary-sets-of-gates) for how circuit lower bounds change for different sets of ternary (or higher than 3-valued) gates.
Phylliida
CC BY-SA 2.5
2010-09-01T21:12:30.620Z
But if ternary is less than factor-2 improvement by definition, how could it be a "major leap"?
Jukka Suomela
CC BY-SA 2.5
2010-09-01T21:17:51.773Z
@Jukka: Fair point; I tempered the language.  Let me know if you have other suggestions, but in general I'm curious about the impact of having more than two states.
Shane
CC BY-SA 2.5
2010-09-03T21:38:55.873Z
BTW: binary was not *always* at the heart of most computing. In fact, early computers were often decimal. It was people like Claude Shannon who pointed out the close relationship (dare I say isomorphism) between on/off (digital electrical circuit), high/low (analog electrical circuit), true/false (logic), 0/1 (math). But even then, it took some time to convinve the hardware vendors that this was a good idea. It was mainly a question of intertia: the engineers had lived in "decimal" since they were 4 years old, they simply couldn't *imagine* anything else. Maybe it's the same with ternary?
Jörg W Mittag
<quantum-computing>
Ternary (and beyond) computation and quantum computing?
Shane
# Ternary (and beyond) computation and quantum computing?

(Asked by: username_0 on 2010-09-01)

Binary math is at the heart of most computing, in large part because of the ease with which two energy states can be achieved. I have always thought that having more states could improve computing power (e.g. using a [trit](http://en.wikipedia.org/wiki/Trit) instead of a bit), but there is a seeming lack of attention being paid to the problem.

Some work has been done in the quantum computing area using qubits to achieve more than the normal two energy levels (see, for example, [the recent effort at UCSB](http://www.sciencemag.org/cgi/content/abstract/sci;325/5941/722?maxtoshow=&HITS=10&hits=10&RESULTFORMAT=&fulltext=Matthew+Neeley&searchid=1&FIRSTINDEX=0&resourcetype=HWCIT)).

What advances have been made toward having [ternary](http://en.wikipedia.org/wiki/Ternary_computer) (or greater) computers, and what are the primary the implications of the extra states?

**Tags:** quantum-computing

> **Comments:**
> **username_3**: But if ternary is less than factor-2 improvement by definition, how could it be a "major leap"?  
> **username_0**: @Jukka: Fair point; I tempered the language.  Let me know if you have other suggestions, but in general I'm curious about the impact of having more than two states.  
> **username_4**: BTW: binary was not *always* at the heart of most computing. In fact, early computers were often decimal. It was people like Claude Shannon who pointed out the close relationship (dare I say isomorphism) between on/off (digital electrical circuit), high/low (analog electrical circuit), true/false (logic), 0/1 (math). But even then, it took some time to convinve the hardware vendors that this was a good idea. It was mainly a question of intertia: the engineers had lived in "decimal" since they were 4 years old, they simply couldn't *imagine* anything else. Maybe it's the same with ternary?  
> **username_1**: A computer based on ternary logic (*this is not the same thing as trits!*) was built in the Soviet Union in the 50's: [Setun](https://en.wikipedia.org/wiki/Setun).  
> **username_2**: We do know that it's not possible to make a reversible universal gate using 2 inputs and 2 outputs on a binary computer, but it is possible in ternary, in fact [about 97% of possible ternary 2 input 2 output gates are universal](http://goo.gl/WP0A3c). Also see [this question](http://cstheory.stackexchange.com/questions/1794/circuit-lower-bounds-over-arbitrary-sets-of-gates) for how circuit lower bounds change for different sets of ternary (or higher than 3-valued) gates.  

---

## 5 answers

### Answer by username_9 on 2010-09-01. Score: 14 | Accepted answer

Computing with trits instead of bits is like computing with Turing machines that have an alphabet size of 3 instead of an alphabet size of 2. Increasing the alphabet size like that (not necessarily 2 to 3, but 2 to larger) can permit a speedup in running time, and a compression in the use of space. (See <http://en.wikipedia.org/wiki/Linear_speedup_theorem> for some initial discussion.) Note that these improvements are fairly "minimal" -- they won't make an intractable problem tractable. (If you use an intractably large alphabet instead of computing over bits, that's "cheating," because then you are just transferring the hardness from one part of the computation to another.)

Qubits at least appear to have a fundamentally different "character" from bits or trits. The state of a qubit (or, more generally, a quDit, "quantum digit") is a collection of probability amplitudes that associates the qubit to some extent with each possible state. Bits, trits, etc., are crisply in one state, the end. In particular, if Factoring is not in polynomial time, then there exists no ptime algorithm over trits that factor integers, while there does exist a quantum algorithm over qudits that factors integers.

<http://en.wikipedia.org/wiki/Qubit>

> **Comments:**
> **username_5**: Well, there is a quantum algorithm for factoring with qubits as well as qudits, so actually the relationship between qudits and qubits vs trits and bits is pretty similar.  
> **username_9**: I agree with you, I must have been unclear.  I meant to say that just because there is a PTIME quantum algorithm over qubits, this doesn't mean there's a classical PTIME algorithm for the same problem over bits.  Sorry for the confusion.  
> **username_5**: Sorry, my mistake.  

---

### Answer by username_3 on 2010-09-01. Score: 18

Actually the usual RAM model is just this approach taken into extreme: each "storage unit" has as many as $\textrm{poly}(n)$ possible states (instead of just 2 states). We assume that each memory word can store $O(\log n)$ bits and word-operations have unit cost.

Cf. [this question](https://cstheory.stackexchange.com/questions/26/complexity-of-the-fisher-yates-shuffle-algorithm).


---

### Answer by username_5 on 2010-09-01. Score: 5

Certainly in the context of quantum computation systems of dimension 3 or more have been looked at. These are known as qudits in general, and qutrits for 3 level systems. The motivation here has mostly been the available physical systems, rather than any expectation of a significant change in computational power. Indeed in quantum systems it is very easy to see that there is no such advantage: Evolution in quantum systems is described by unitary operations which can be associated with the Lie group su(D), where D is the total dimensionality of the system. Given entangling gates between subsystems, together with individual control over these local subsystems, it is known that it is always possible to approximate any such operator, independent of the dimensionality of the local systems. Obviously, if you can reach all unitary operations on D dimensions, then you can reach all of the ones on $d

With this in mind, the relationship between qutrits and qubits versus trits and bits is similar, and the level of interest on a theoretical level has been fairly similar. It is really in the context of physical implementations that qutrits attract interest, since quantum computing has not really settled on a dominant architecture yet, and there are plenty of systems with local dimensionality > 2.

You may want to have a look into what are called continuous variable systems, which are a type of system considered in quantum computation which have an infinite number of local dimensions (position is an example of a continuous variable quantity). Such systems do actually exist, and are fundamentally different from analog computers due to the quantization of energy levels.


---

### Answer by username_6 on 2010-09-01. Score: 1

Ternary logic attracted attention in mid 70s and 80s, but I guess theorists are not interested by it since advantages are not that incredible and because it is more or less the same thing that classical logic (from the conceptual point of view).

However, if you read a paper such as this one: [Low power dissipation MOS ternary logic family](http://www.ee.bgu.ac.il/~kushnero/ternary/Using%20CMOS%20gates/Low%20power%20dissipation%20MOS%20ternary%20logic%20family.pdf),you will find many references in it about the interest in practice (but keep in mind that it was practical interests of the 80s).

> **Comments:**
> **username_0**: Thanks, I guess I should get back into my hot-tub time machine now...  

---

### Answer by username_7 on 2014-10-31. Score: -9

why was my post deleted? I didn't do anything against the guidelines, i read the guidelines page!

I'll post this AGAIN. The only way to get ternary logic to work in a computer, is to first understand that you must have 3 magnetic fields, from a 3 terminal powersource. This is a simple negative>positive + a 3rd option.

But first, to whoever deleted my prior post, just because you do not enjoy reading the responses of people who can actually think for themselves and outside the box doesn't mean that person broke any rules. To others reading this, I posted a very good and informative response explaining how in theory a 3 state power system can work.

It's very obvious to me you can have a 3 terminal (but still 2 pole) battery. All you need is Zinc for negative and copper for positive (very common, of course) and the 3rd is aluminum. In order for me to explain how it's possible to have a 3rd type of electric current i first have to explain how we understand color scales. Take the green, red and blue color scale. Doesn't matter which color you want to with. So we will say in this case red is positive and blue is negative. What are these colors combined? Purple! So what is the opposite of purple? GREEN! This is how you figure out the other metal. Combine zinc and copper and guess what, you have brass, what the ancient greeks were very fond of at some point in their time. So, just like we take purple and look at it's opposite, we find that the opposite of brass is aluminum. Now you have your third terminal's alkaline.

Ok, so now that we have that out of the way. It is now possible to have a 3rd current. What will happen, due to the aluminum being weaker than the zinc negative, but stronger than the copper positive, if you place the aluminum 3rd terminal in a position that makes all three triangular in placement, the zinc's stronger energy will obviously flow to both of the terminals. But in the case of zinc to aluminum, the electrons will flow around the metal, creating a circular field, instead of a forward one. The reason for this is because of the aluminum's stronger magnetic field relative to the copper. So it's "pushing" on the copper and is being pushed by the zinc. If you put them in your battery correctly, the 3rd terminal will by default have a circular magnetic field, and so will the wire connected to it.

So why was my post deleted? Can you prove anything I just said wrong?

> **Comments:**
> **username_8**: It may or may not be wrong, but it is definitely off-topic.  

---

