Romans Needed Quantum Computers

Harys Dalvi

October 2021

Throughout history, we have always tried to condense information into smaller and smaller spaces. Various cultures have created their own techniques and adopted techniques from other cultures. In this post, I'll go through the history of information density with numbers, and compare this to computers and quantum computers.

Ancient Beginnings

Prehistory

Long long ago, before writing was developed, people must have counted on their fingers. But they also sometimes made markings to count. Imagine you are in prehistory counting sheep with a stone, making one mark per sheep. If there are \(x\) sheep, it will take \(n\) markings on the stone to count them all. $$n=x$$ Unfortunately, the stone only has space for a few markings. But since we are talking about concepts here, if the stone was big enough, you could keep counting more sheep forever. So your system is capable of counting to infinity in theory. $$L_x=\infty$$ There is only one type of mark you make, a simple line in the stone. So the number of types of symbols is $$S=1$$

Ancient Rome

Much later, the Romans started using Roman numerals. They started making marks just like in prehistory: I is 1, II is 2, and III is 3. But then they thought, why make five marks like IIIII for five when you can just write V?

And here we are in year MMXXI. Unfortunately, the highest symbol is M, for 1000. Additionally, only up to three of the same letter are allowed in a row. This makes the largest number MMMCMXCIX, or 3999. In the middle ages, a line on top called a vinculum was used, multiplying a number by 1000 [1]. This means MMMCMXCIX is 3999000, and then we can add CMXCIX (999) to get MMMCMXCIXCMXCIX (3999999). Then we're really stuck.

So we have \(L_x=3999999\). Looking at MMMCMXCIXCMXCIX, we count 16 symbols needed to write this number (including the vinculum). Now how can we determine \(n\), the number of symbols needed to write a number, as a function of \(x\), the number we are writing?

For simplicity, I'll only consider numbers up to 3999, so let's bring \(L_x\) down to 3999. Let's map each place value to a Roman numeral. The ones place can have I, II, III, IV, V, VI, VII, VIII, IX. This is an average of 20/9 symbols, or about 2.2 symbols. The tens place can have X, XX, XXX, XL, L, LX, LXX, LXXX, XC. This is very similar, and has the same average symbols. The hundreds place is the same. So we can say each new place value takes another 20/9 symbols to represent. This gives something like $$n = \frac{20}{9} \log_{10} x$$ Does this work? We can make a Matplotlib graph comparing this model to the actual length of the Roman numerals for a number \(x\). Here is what we get:

Our model (in orange) seems to approximate the data (blue) reasonably well over the long term. There is also a moving average of the data over 100 numbers (green) which stays close to the orange line. You can see the low spikes due to numbers like M (1000) and MMD (2500). In case you're curious, the highest point on the graph is \(x=3888\), written with 15 symbols as MMMDCCCLXXXVIII.

Ignoring the vinculum, we see that the symbols increase in a 1/5 pattern for each place value. So if we wanted to expand the Roman numeral system, we would need 2 symbols for each place value: continuing on the pattern of I/V for ones, X/L for tens, and C/D for hundreds. In the long term, this can be modeled as $$S = 2 \log_{10} x$$ So while the number of symbols \(n\) is less than with prehistoric writing, we now face an ever-increasing number of types of symbols \(S\).

Ancient India

Ancient India used a system quite different from that of the Romans. (For unicode compatibility reasons, I'll use modern numerals here. The symbols at the time were different, although still vaguely recognizable. They were 𑁦𑁧𑁨𑁩𑁪𑁫𑁬𑁭𑁮𑁯 if you can see that.)

The Indians also used a simple line for one, like the Romans (and the Chinese and others.) But for a two, instead of two lines, there was a new symbol: 2. This continued all the way to 9. For ten, the symbol for one was used again, and then there was a new symbol for 0. This concept of place value could be used to write any number (\(1729 = 1000+700+20+9\)). Each additional decimal place value required one new symbol rather than an average of 2.2, giving $$n = \log_{10} x$$ This is a lower rate of increase than roman numerals. Even more importantly, \(L_x = \infty\): arbitrarily large numbers could now be written with enough symbols. We can make a graph for this system, now known as Arabic numerals (since Arabs brought the system from India to Europe), similar to that for Roman numerals.

We have confirmed that our model \(n = \log_{10} x\) is roughly accurate, but unlike with Roman numerals, this model can now be extended as \(x \to \infty\) even with just 10 symbols: \(S=10\). This combined the best of the prehistoric and Roman systems: \(n\) increases only as the log of \(x\) rather than linearly, but the number of symbols \(S\) is kept fixed no matter how large \(x\) gets.

Other Ancient Civilizations

The Roman system and the modern descendant of the Indian system are probably the most familiar numeral systems to most readers. However, there were many other ancient numeral systems, at least two of which are still in common use today. I have analyzed these if you're interested.

Ancient Chinese

A descendant of the ancient Chinese system is used in China and Japan today when writing with characters rather than Arabic numerals. For unicode compatibility reasons, I will be using modern Chinese characters here. This is the system used in Chinese characters and Japanese Kanji; there is also an East Asian numeral system using counting rods, which works similarly to the modern system and even includes negative numbers.

Chinese has unique symbols for numbers 1–10. 20 is represented not by 2 and then 0, but by 2 and then 10: 二十. This is multiplication by placing a number 1–10 in front of a larger place. Addition occurs by placing it after: for example, while 二十 is \(2 \times 10 = 20\), 十二 is \(10+2=12\). Both of these can be combined: 32 is 三十二, since \(3 \times 10 + 2 = 32\).

This works up to 99. At 100, a new symbol 百 is introduced for 100. Then 二百二十二 is \(2 \times 100 + 2 \times 10 + 2 = 222\). There is a similar symbol 千 for 1000.

After 1000, a new character is introduced for 10,000. Then a new character must be introduced for every multiple of \(10^4\). So the limit \(L_x\) is high, but it is not infinite. I am not sure exactly how many characters are commonly used these days.

Now let's analyze the number of characters \(n\) it takes to write a number \(x\). For numbers up to 10, only one character is needed. For numbers above 10, we write the tens place and then one more character for the ones place, if needed. If there is a 10 in the tens place, we simply write one character, 十. Otherwise, two characters are needed. So the tens place adds about $$\frac{1}{9}(1) + \frac{8}{9}(2) = \frac{17}{9}$$ 17/9 characters, about 1.9.

Now let's look at the hundreds place. From here on, we must include multiples of one. For example, 115 is not 百十五, but 一百一十五. This means that from 100 on, each place value (other than one) always takes two characters. Since we are interested in long term trends, we can write $$n = 2 \log_{10} x$$ This grows quicker than the modern decimal system, but more slowly than the Roman system: $$1 \lt 2 \lt \frac{20}{9}$$ Past the ten thousands place, there is no character for hundred thousands. How will we handle the hundred thousands place?

We will have to multiply the ten thousands place by a new tens place. This will mean adding a number 10–99 before the character for 10,000. This will take another 2 characters. So our rule of \(n = 2 \log_{10} x\) still applies. As for the number of symbols, in the long term, we need a new symbol for every 10,000. So we can write $$S = \log_{10000} x$$

Ancient Greek, Hebrew, Arabic

The Greek, Hebrew, and Arabic numeral systems are all functionally identical, and differ mainly in the symbols. Greek uses Αʹ Βʹ Γʹ, Hebrew uses א ב ג‎, and Arabic uses ا ب ج for 1 2 3. These systems are all used today for at least some purposes. Arabs used these before they adopted what we know as Arabic numerals from India.

These systems have unique symbols for 1–9, 10–90, and 100–900. They vary in their treatments of numbers past this, but are different from what is shown here, so let's say \(L_x = 999\) for this system. It's notable that each new place value requires only one more letter. For example, 4 is Δʹ/ד/د, 44 is ΜΔʹ/מד/مد, 444 is ΥΜΔʹ/תמד/تمد. Therefore we can write the same rule $$n = \log_{10} x$$ Interestingly, this is the same as modern Arabic numerals. The problem is that this requires a large number of new unique symbols: 9 for each place value. So we have $$S = 9 \log_{10} S$$

Ancient Egyptian

Unfortunately, Egyptian hieroglyphics are not as widely supported in unicode as the other scripts on here, so you may have problems with rendering.

The Ancient Egyptian numeral system starts like the prehistoric one: each line represents a one. So 𓏺 is one, 𓏻 is two, 𓐂 is nine. After that, there are new symbols for each place value: 𓎆 is ten. These can be combined: 𓎇𓏾 is 25, and 𓍣𓎊𓏿 is 256.

The number of symbols needed for each place value obviously depends on the number, but it ranges from 1–9; this averages to 5. So we can say $$n = 5 \log_{10} x$$ Each new place value needs a new symbol. So $$S = \log_{10} x$$ The highest symbol was 𓁨 for \(10^6\). Let's set this as \(L_x\).

Ancient Mayan

Unfortunately, Mayan numerals are not supported on my computer in unicode, and I am not good at writing Ancient Mayan symbols, so I will not be able to show the script here. However, it is conceptually identical to the modern Arabic numerals, even including a symbol for zero. The big difference is that it is base-20, giving $$n = \log_{20} x$$ $$S = 20$$ Meaning that the Mayan system is even more efficient that the modern one in terms of \(n\). (This is considering number of places alone. The symbols in individual places often have multiple components: for example, three is three dots; fourteen is four dots and two lines. This is almost like a numeral system within a larger place value system, rather than arbitrary symbols.)

Comparison

Now, let's compare all the systems we've seen so far. Then we'll see where modern systems come in.

As a refresher, \(x\) is the number being written. \(n\) is the number of symbols required to write \(x\) in this system. \(L_x\) is the maximum number \(x\) that can be written with the system as is. \(S\) is the number of unique symbols that would be needed to write an arbitrarily large \(x\) with a version of the system, perhaps adding more symbols as needed.

Other than the prehistoric system, it seems all the \(n\) values follow logarithmic growth. Is this the most efficient system possible? Well, exponential growth is one of the fastest types of growth out there, so its inverse logarithmic growth should be one of the slowest. I can think of one system that grows faster than exponential: factorial. What would an inverse factorial system look like?

24 might take 4 digits to represent rather than 2. 120 would take 5. 720 would take 6. So far, this system is not doing well. But there is a point, somewhere way out there, beyond which the inverse factorial system will be more efficient than our system. Now to actually invent an inverse factorial method for representing numerals. I haven't seen anything like it. (Edit: when I went to sleep after writing this I couldn't stop thinking about an inverse factorial system, and then I thought I came up with one, but it turns out I didn't. You can look if you're interested, or I can leave it as an “exercise to the reader”.)

My attempted inverse factorial system

Instead of a 1s place, 10s place, 100s place... \(10^n\) place... I had a 2s place, 3s place, 4s place... \(n+2\) place. Each place could have either a 1 or 0. Then you multiply together all the places that have a 1. So \(1_!\) is 2, \(01_!\) is 3, \(11_! = 2 \times 3 = 6\), \(101_! = 2 \times 4 = 8\). I then made some minor restrictions and a computer program so every number had a unique representation.

The reason why I thought this system would follow an inverse factorial law is that in the system, \((n+1)!\) is written as a series of \(n\) ones: 6 is \(11_!\), 24 is \(111_!\), 120 is \(1111_!\).

But this system has some drawbacks. Notably, a prime number \(p\) requires \(p-1\) digits to write, following a rule similar not to inverse factorial, but to \(n=x\). I wrote a program to figure out the number of digits \(n\) needed to write a number \(x\) in this system. Here are some graphs:

On the high side, you can see something approximately \(n=x\) due to prime numbers. My orange model is \(n = 2x/\ln x\). This is very interesting, because a surprisingly good approximation for the number of primes less than \(x\) is $$\frac{x}{\ln (x)}$$ I have no idea why it seems to follow this model so closely.

You could also have something like \(n = \log( \log( x ))\). Again, I don't know how you would invent a numeral system that follows this rule, but it might be theoretically possible, and if so it would be quite efficient.

Modern Systems

Scientific notation

Scientific notation is based on the regular decimal system, so it also has \(L_x = \infty \) and \(S = 10\). However, \(n\) can be anything you want, no matter how large or small \(x\) is. The problem is that this sacrifices accuracy (which can actually be a good thing when experimental uncertainty is involved). I found it interesting how scientific notation fits into the variables we've been looking at for ancient numeral systems.

Binary and Hexadecimal

Binary and Hexadecimal are the same as the decimal system, but with a different base. (This is similar to the Mayan system.) But since \(n = \log_2 x\) for a binary computer, the number of bits \(n\) required actually increases faster than for writing a number on paper. By change of base, the ratio is $$\frac{\ln 10}{\ln 2} \approx 3.3$$ So if a number \(x\) takes \(n_{10}\) digits to write on paper, we can predict it will take \(n_2 \approx 3.3 n_{10}\) bits in a computer as \(x\) grows large. For example, 2021 takes four digits on paper, and the binary representation 11111100101 takes 11 bits. 11/4 = 2.75. If we take a really big number, like 1234567890, this takes ten digits to write on paper, and 31 bits to represent as 1001001100101100000001011010010. 31/10 approaches 3.3 better.

In reality, numbers may take up more or less space in computer memory based on different systems to store them, such as two's complement and float64. However, we are now using numbers as a template to talk more generally about information density.

I can talk about an abstract information density, which is the amount of information \(x\) divided by the space to store it \(n\). With the prehistoric system, this is \(x/x = 1\). With the decimal system, this is \(x/\log_{10}x\), which tends to be higher than 1: each digit in a decimal number, like the 2 in 123, has much more meaning than a simple tally mark.

But with computers, this is \(x/\log_2 x\), which is apparently lower than for the decimal system. This can be explained by the fact that even though computers need a high number of bits, the bits are extremely small physically. They can fit on a microchip.

DNA

DNA has four types of nitrogenous bases, so \(S=4\). Every 3 base pairs codes for one amino acid (or a stop codon). The number of base pairs needed to code for a protein can be considered \(n\). Such a protein will have \(n/3\) amino acids. The question is, what number \(x\) corresponds to the amount of information stored in a protein with these amino acids?

I feel like the amount of information in a protein with 100 amino acids is a lot more than the amount of information conveyed by writing 100 on a piece of paper. Since there are many complicated ways for amino acids to interact as their number increases, moving into tertiary and even quaternary structure, I feel like amino acids have even more ways to add meaning \(x\) as their number \(n/3\) increases. This means \(x\) might be exponentially related to \(n\). So we can invert this and say $$\frac{n}{3} \propto \log_4 x$$ $$n \propto \log_4 x$$ As for the limit of information, DNA can store an immense ammount of information. I'll go with \(L_x = \infty\).

Quantum computing

In quantum computing, quantum particles are in a superposition of states. When measured, they settle on a state that corresponds to either 0 or 1, both with equal probability. So if we have \(n\) qubits (quantum bits), each corresponding to 0 or 1, that's like a binary number with \(n\) bits. So then what's the advantage of quantum computing?

Qubits settle on 0 or 1, when measured. If we don't measure them, they remain in a superposition of all possible states at once. This means that with a properly designed algorithm, they can conduct multiple calculations at once.

Then the question is, how do we access this information if every measurement settles on 0 or 1? This is part of the reason why quantum computing is so difficult, but it is possible through quantum interference. This is the strange phenomenon where since a quantum particle is also a wave (wave-particle duality), this wave can interfere with itself. (This can be shown with the double slit experiment.) The various calculations can be combined and measured to get a useful result [2].

So in theory, a quantum algorithm can perform infinite calculations at once. This means \(n = C\): as long as you have the constant \(C\) qubits for the calculation you're interested in, that same number of qubits can store an infinite amount of information \(x\).

In practice, it is difficult to combine the results in order to extract information, because each qubit's measured state is either 0 or 1. This means that for \(n\) qubits, the information \(x\) is not infinite, at least not based on any measurements we can take. As for the exact relationship between \(n\) and \(x\), I'm not sure. I think it might depend on the algorithm in question, which makes sense since each algorithm has its own \(n\). This reminds me of hard computer science problems that can't be solved generally, like the halting problem, shown undecidable by Alan Turing.

There are a few options for a “type of symbol” in quantum computing. One example is a quantum computer based on ions. In this case, we could say \(S=1\). However, we also need to consider the various connections between qubits. Then we could maybe say \(S=2\), or maybe we could consider the various quantum logic gates [3], composed of qubits, as a new type of symbol in themselves.

What is the limit of information \(L_x\) that can be stored? In theory, more qubits always means more information. In practice, qubits interacting can lead to quantum decoherence, losing the unique quantum properties needed for quantum computers to work. As of September 2020, IBM's largest quantum computer had 65 qubits [4].

So even though superposition means an infinite possible number of states, this doesn't translate into an infinitely larger amount of information compared to a classical computer. However, if quantum decoherence can be kept under control, the idea is promising.

But as with new technologies in general, I worry about how it might be applied negatively. Quantum computing has huge potential for positive advancements in cryptography. On the other hand, this means it has potential for a lot of hacking. If quantum computing is implemented correctly by a hacker, quantum superposition would make our current classical systems completely vulnerable. Hopefully (?) quantum decoherence remains a large issue, so hackers won't be able to solve it reliably, but organized teams will be able to use it for good in certain applications.

Conclusion

Starting with prehistoric counting, I introduced a set of variables with which we can view systems of information. All the numeral systems devised in ancient times fit neatly into this set. Binary and hexadecimal as used in classical computing worked as well.

DNA and scientific notation were difficult but interesting to analyze in the way I did for numeral systems. Quantum computing, on the other hand, became almost impossible. The theoretical aspects of quantum theory and superposition repeatedly imply “infinite power”, but the practical barriers are hard to quantify, especially because they're always being pushed. It's clear that developing quantum computing will be extremely difficult. It's also clear that at least for small numbers of qubits without too much decoherence, quantum computing is promising to handle huge amounts of data at high speeds.

Roman numerals, with their low limit on data \(L_x\) and quickly increasing space needed \(n\), bear little resemblance to the ideals of what quantum computing could be.

Romans needed quantum computers.

References

1. Which is the biggest number in Roman numerals? (Roman Numerals) ^
2. What Can We Do with a Quantum Computer? (Andris Ambainis) (University of Latvia) ^
3. Quantum Logic Gates (NIST) ^
4. IBM promises 1000-qubit quantum computer—a milestone—by 2023 (Adrian Cho) ^