4
$\begingroup$

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 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).

What advances have been made toward having ternary (or greater) computers, and what are the primary the implications of the extra states?

$\endgroup$
  • 4
    $\begingroup$ But if ternary is less than factor-2 improvement by definition, how could it be a "major leap"? $\endgroup$ – Jukka Suomela Sep 1 '10 at 21:12
  • $\begingroup$ @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. $\endgroup$ – Shane Sep 1 '10 at 21:17
  • 2
    $\begingroup$ 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? $\endgroup$ – Jörg W Mittag Sep 3 '10 at 21:38
  • 2
    $\begingroup$ 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. $\endgroup$ – Bruno Oct 31 '14 at 14:09
  • 2
    $\begingroup$ 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. Also see this question for how circuit lower bounds change for different sets of ternary (or higher than 3-valued) gates. $\endgroup$ – Phylliida Oct 31 '14 at 17:39
14
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Joe Fitzsimons Sep 1 '10 at 23:23
  • $\begingroup$ 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. $\endgroup$ – Aaron Sterling Sep 1 '10 at 23:46
  • $\begingroup$ Sorry, my mistake. $\endgroup$ – Joe Fitzsimons Sep 2 '10 at 0:01
18
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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<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.

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.

$\endgroup$
1
$\begingroup$

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,you will find many references in it about the interest in practice (but keep in mind that it was practical interests of the 80s).

$\endgroup$
  • $\begingroup$ Thanks, I guess I should get back into my hot-tub time machine now... $\endgroup$ – Shane Sep 1 '10 at 21:30
1
$\begingroup$

Theoretically, there is no reason to prefer trits to bits or vice versa. Everything is trivially equivalent since you can simulate a bit-based computation using trits and you can simulate a trit-based computation using bits.

Experimentally, many physical systems, such as natural or artificial atoms, naturally give higher-dimensional qudits (in principle, infinite-dimensional qudits). Even in experiments, though, most of the focus has been on qubits, sometimes with one or two extra dimensions used for readout. Largely this is because it is simpler to address and manipulate only two dimensions at a time.

In the future, as quantum computers begin to scale up, experimentalists may find it easier to work with a few more dimensions per system, for example using a four-level artificial atom instead of two two-level artificial atoms. A less obvious example is that several proposed experimental systems easily allow for a small constant number of qudits to be coupled simultaneously, for example superconducting qudits all coupled together along the same transmission line or ions all caught in the same trap. (In a scalable system you need multiple transmission lines or multiple ion traps, but these are harder to fabricate.) The question, though, is how to control the systems that are all coupled together, evolving simultaneous. It is a difficult control-theory problem, because the dimension grows very quickly.

Once again, though, the last two paragraphs are only about practical implementation issues. Theoretically, from a CS perspective (and ignoring fault tolerance), there is no reason to prefer bits to trits or whatever else.

$\endgroup$
-9
$\begingroup$

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?

$\endgroup$
  • 7
    $\begingroup$ It may or may not be wrong, but it is definitely off-topic. $\endgroup$ – Emil Jeřábek Oct 31 '14 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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