The best articles by Ciro Santilli Updated 2024-12-15 +Created 1970-01-01
View more
These are the best articles ever authored by Ciro Santilli, most of them in the format of Stack Overflow answers.
Ciro posts update about new articles on his Twitter accounts.
A chronological list of all articles is also kept at: Section "Updates".
Some random generally less technical in-tree essays will be present at: Section "Essays by Ciro Santilli".
Read the full article
Electronic design automation Updated 2024-12-15 +Created 1970-01-01
View more
A set of software programs that compile high level register transfer level languages such as Verilog into something that a fab can actually produce. One is reminded of a compiler toolchain but on a lower level.
The most important steps of that include:
Read the full article
Fabless manufacturing Updated 2024-12-15 +Created 1970-01-01
View more
In the past, most computer designers would have their own fabs.
But once designs started getting very complicated, it started to make sense to separate concerns between designers and fabs.
What this means is that design companies would primarily write register transfer level, then use electronic design automation tools to get a final manufacturable chip, and then send that to the fab.
It is in this point of time that TSMC came along, and benefied and helped establish this trend.
The term "Fabless" could in theory refer to other areas of industry besides the semiconductor industry, but it is mostly used in that context.
Read the full article
High level quantum synthesis Updated 2024-12-15 +Created 1970-01-01
View more
This is a term "invented" by Ciro Santilli to refer to quantum compilers that are able to convert non-specifically-quantum (functional, since there is no state in quantum software) programs into quantum circuit.
The term is made by adding "quantum" to the more "classical" concept of "high-level synthesis", which refers to software that converts an imperative program into register transfer level hardware, typicially for FPGA applications.
Read the full article
How computers work? Updated 2024-12-15 +Created 1970-01-01
View more
A computer is a highly layered system, and so you have to decide which layers you are the most interested in studying.
Although the layer are somewhat independent, they also sometimes interact, and when that happens it usually hurts your brain. E.g., if compilers were perfect, no one optimizing software would have to know anything about microarchitecture. But if you want to go hardcore enough, you might have to learn some lower layer.
It must also be said that like in any industry, certain layers are hidden in commercial secrecy mysteries making it harder to actually learn them. In computing, the lower level you go, the more closed source things tend to become.
But as you climb down into the abyss of low level hardcoreness, don't forget that making usefulness is more important than being hardcore: Figure 1. "xkcd 378: Real Programmers".
First, the most important thing you should know about this subject: cirosantilli.com/linux-kernel-module-cheat/should-you-waste-your-life-with-systems-programming
Here's a summary from low-level to high-level:
Figure 1.
xkcd 378: Real Programmers
. Source.
Video 1.
How low can you go video by Ciro Santilli (2017)
Source. In this infamous video Ciro has summarized the computer hierarchy.
Read the full article
Logic synthesis Updated 2024-12-15 +Created 1970-01-01
View more
The output of this step is another Verilog file, but one that exclusively uses interlinked cell library components.
Read the full article
Programmer's model of quantum computers Updated 2024-12-15 +Created 1970-01-01
View more
This is a quick tutorial on how a quantum computer programmer thinks about how a quantum computer works. If you know:
a concrete and precise hello world operation can be understood in 30 minutes.
Although there are several types of quantum computer under development, there exists a single high level model that represents what most of those computers can do, and we are going to explain that model here. This model is the is the digital quantum computer model, which uses a quantum circuit, that is made up of many quantum gates.
Beyond that basic model, programmers only may have to consider the imperfections of their hardware, but the starting point will almost always be this basic model, and tooling that automates mapping the high level model to real hardware considering those imperfections (i.e. quantum compilers) is already getting better and better.
This model is very simple to understand, being only marginally more complex than that of a classical computer, see also: quantumcomputing.stackexchange.com/questions/6639/is-my-background-sufficient-to-start-quantum-computing/14317#14317
The situation of quantum computers today in the 2020's is somewhat analogous to that of the early days of classical circuits and computers in the 1950's and 1960's, before CPU came along and software ate the world. Even though the exact physics of a classical computer might be hard to understand and vary across different types of integrated circuits, those early hardware pioneers (and to this day modern CPU designers), can usefully view circuits from a higher level point of view, thinking only about concepts such as:
as modelled at the register transfer level, and only in a separate compilation step translated into actual chips. This high level understanding of how a classical computer works is what we can call "the programmer's model of a classical computer". So we are now going to describe the quantum analogue of it.
The way quantum programmers think about a quantum computer in order to program can be described as follows:
  • the input of a N qubit quantum computer is a vector of dimension N containing classic bits 0 and 1
  • the quantum program, also known as circuit, is a unitary matrix of complex numbers that operates on the input to generate the output
  • the output of a N qubit computer is also a vector of dimension N containing classic bits 0 and 1
To operate a quantum computer, you follow the step of operation of a quantum computer:
Each time you do this, you are literally conducting a physical experiment of the specific physical implementation of the computer:
  • setup your physical system to represent the classical 0/1 inputs
  • let the state evolve for long enough
  • measure the classical output back out
and each run as the above can is simply called "an experiment" or "a measurement".
The output comes out "instantly" in the sense that it is physically impossible to observe any intermediate state of the system, i.e. there are no clocks like in classical computers, further discussion at: quantum circuits vs classical circuits. Setting up, running the experiment and taking the does take some time however, and this is important because you have to run the same experiment multiple times because results are probabilistic as mentioned below.
Unlike in a classical computer, the output of a quantum computer is not deterministic however.
But the each output is not equally likely either, otherwise the computer would be useless except as random number generator!
This is because the probabilities of each output for a given input depends on the program (unitary matrix) it went through.
Therefore, what we have to do is to design the quantum circuit in a way that the right or better answers will come out more likely than the bad answers.
We then calculate the error bound for our circuit based on its design, and then determine how many times we have to run the experiment to reach the desired accuracy.
The probability of each output of a quantum computer is derived from the input and the circuit as follows.
First we take the classic input vector of dimension N of 0's and 1's and convert it to a "quantum state vector" of dimension :
(1)
We are after all going to multiply it by the program matrix, as you would expect, and that has dimension !
Note that this initial transformation also transforms the discrete zeroes and ones into complex numbers.
For example, in a 3 qubit computer, the quantum state vector has dimension and the following shows all 8 possible conversions from the classic input to the quantum state vector:
000 -> 1000 0000 == (1.0, 0.0, 0.0, 0.0,  0.0, 0.0, 0.0, 0.0)
001 -> 0100 0000 == (0.0, 1.0, 0.0, 0.0,  0.0, 0.0, 0.0, 0.0)
010 -> 0010 0000 == (0.0, 0.0, 1.0, 0.0,  0.0, 0.0, 0.0, 0.0)
011 -> 0001 0000 == (0.0, 0.0, 0.0, 1.0,  0.0, 0.0, 0.0, 0.0)
100 -> 0000 1000 == (0.0, 0.0, 0.0, 0.0,  1.0, 0.0, 0.0, 0.0)
101 -> 0000 0100 == (0.0, 0.0, 0.0, 0.0,  0.0, 1.0, 0.0, 0.0)
110 -> 0000 0010 == (0.0, 0.0, 0.0, 0.0,  0.0, 0.0, 1.0, 0.0)
111 -> 0000 0001 == (0.0, 0.0, 0.0, 0.0,  0.0, 0.0, 0.0, 1.0)
This can be intuitively interpreted as:
  • if the classic input is 000, then we are certain that all three bits are 0.
    Therefore, the probability of all three 0's is 1.0, and all other possible combinations have 0 probability.
  • if the classic input is 001, then we are certain that bit one and two are 0, and bit three is 1. The probability of that is 1.0, and all others are zero.
  • and so on
Now that we finally have our quantum state vector, we just multiply it by the unitary matrix of the quantum circuit, and obtain the dimensional output quantum state vector :
(2)
And at long last, the probability of each classical outcome of the measurement is proportional to the square of the length of each entry in the quantum vector, analogously to what is done in the Schrödinger equation.
For example, suppose that the 3 qubit output were:
(3)
Then, the probability of each possible outcomes would be the length of each component squared:
(4)
i.e. 75% for the first, and 25% for the third outcomes, where just like for the input:
  • first outcome means 000: all output bits are zero
  • third outcome means 010: the first and third bits are zero, but the second one is 1
All other outcomes have probability 0 and cannot occur, e.g.: 001 is impossible.
Keep in mind that the quantum state vector can also contain complex numbers because we are doing quantum mechanics, but we just take their magnitude in that case, e.g. the following quantum state would lead to the same probabilities as the previous one:
(5)
This interpretation of the quantum state vector clarifies a few things:
  • the input quantum state is just a simple state where we are certain of the value of each classic input bit
  • the matrix has to be unitary because the total probability of all possible outcomes must be 1.0
    This is true for the input matrix, and unitary matrices have the probability of maintaining that property after multiplication.
    Unitary matrices are a bit analogous to self-adjoint operators in general quantum mechanics (self-adjoint in finite dimensions implies is stronger)
    This also allows us to understand intuitively why quantum computers may be capable of accelerating certain algorithms exponentially: that is because the quantum computer is able to quickly do an unitary matrix multiplication of a humongous sized matrix.
    If we are able to encode our algorithm in that matrix multiplication, considering the probabilistic interpretation of the output, then we stand a chance of getting that speedup.
Bibliography:
Read the full article
Quantum circuits vs classical circuits Updated 2024-12-15 +Created 1970-01-01
View more
Just like a classic programmer does not need to understand the intricacies of how transistors are implemented and CMOS semiconductors, the quantum programmer does not understand physical intricacies of the underlying physical implementation.
The main difference to keep in mind is that quantum computers cannot save and observe intermediate quantum state, so programming a quantum computer is basically like programming a combinatorial-like circuit with gates that operate on (qu)bits:
For this reason programming a quantum computer is much like programming a classical combinatorial circuit as you would do with SPICE, verilog-or-vhdl, in which you are basically describing a graph of gates that goes from the input to the output
For this reason, we can use the words "program" and "circuit" interchangeably to refer to a quantum program
Also remember that and there is no no clocks in combinatorial circuits because there are no registers to drive; and so there is no analogue of clock in the quantum system either,
Another consequence of this is that programming quantum computers does not look like programming the more "common" procedural programming languages such as C or Python, since those fundamentally rely on processor register / memory state all the time.
Quantum programmers can however use classic languages to help describe their quantum programs more easily, for example this is what happens in Qiskit, where you write a Python program that makes Qiskit library calls that describe the quantum program.
Read the full article
Standard cell library Updated 2024-12-15 +Created 1970-01-01
View more
Basically what register transfer level compiles to in order to achieve a real chip implementation.
After this is done, the final step is place and route.
They can be designed by third parties besides the semiconductor fabrication plants. E.g. Arm Ltd. markets its Artisan Standard Cell Libraries as mentioned e.g. at: web.archive.org/web/20211007050341/https://developer.arm.com/ip-products/physical-ip/logic This came from a 2004 acquisition: www.eetimes.com/arm-to-acquire-artisan-components-for-913-million/, obviously.
The standard cell library is typically composed of a bunch of versions of somewhat simple gates, e.g.:
  • AND with 2 inputs
  • AND with 3 inputs
  • AND with 4 inputs
  • OR with 2 inputs
  • OR with 3 inputs
and so on.
Each of those gates has to be designed by hand as a 3D structure that can be produced in a given fab.
Simulations are then carried out, and the electric properties of those structures are characterized in a standard way as a bunch of tables of numbers that specify things like:
  • how long it takes for electrons to pass through
  • how much heat it produces
Those are then used in power, performance and area estimates.
Read the full article