The Curious Programmer

Software, Gadgets, Books, and All Things Geek

🔮 Unveiling the Hidden Magic: How a URL Transforms into a Webpage 🧙 — March 17, 2023

🔮 Unveiling the Hidden Magic: How a URL Transforms into a Webpage 🧙

Hello, dear readers! Today I’m going to explain one of the most basic and fascinating concepts of the web world: what happens when you navigate to a URL in a browser and hit “Enter”. You probably do this every day without thinking much about it, but behind the scenes there is a lot of magic going on. Let’s dive into it!

What is a URL?

First of all, let’s clarify what a URL is. URL stands for Uniform Resource Locator and it is basically an address that tells your browser where to find the information you want on the Internet. A URL has different parts that have different meanings. For example:

https://example.com/page1

In this URL, the first part https tells your browser which protocol to use for communication. A protocol is a set of rules that define how data is exchanged over the network. There are different protocols for different purposes, such as http, https, ftp, etc. In this case, https means that the communication will be secure and encrypted.

The second part example.com is called the domain name and it identifies the server that hosts the website you want to visit. A server is a powerful computer that stores web files and responds to requests from browsers. Each server has a unique address called an IP address that consists of four numbers separated by dots, such as 203.0.113.0. However, these numbers are hard to remember and type, so we use domain names instead.

The third part /page1 is called the path and it specifies which page or resource on the website you want to access. A website can have multiple pages or resources such as images, videos, scripts, etc., each with its own path.

What happens when you hit “Enter”?

Now that we know what a URL is made of, let’s see what happens when you hit “Enter” after typing it in your browser.

Step 1: DNS lookup

The first thing your browser does is to look up the IP address of the domain name using a service called DNS (Domain Name System). DNS is like a phone book for the Internet that maps domain names to IP addresses. Your browser contacts a DNS server (usually provided by your Internet Service Provider) and asks for the IP address of example.com. The DNS server responds with something like 203.0.113.0.

Step 2: TCP connection

The next thing your browser does is to establish a TCP (Transmission Control Protocol) connection with the server at 203.0.113.0. TCP is another protocol that ensures reliable and ordered delivery of data over the network. Your browser initiates a three-way handshake with the server:

  • Your browser sends a SYN (synchronize) packet to the server asking for permission to start communication.
  • The server replies with a SYN-ACK (synchronize-acknowledge) packet granting permission.
  • Your browser sends an ACK (acknowledge) packet back confirming receipt.

This way, both your browser and the server agree on some parameters such as port numbers and sequence numbers for data transmission.

Step 3: HTTPS handshake

If your URL starts with https, then your browser also performs an HTTPS (Hypertext Transfer Protocol Secure) handshake with
the server before sending any data. HTTPS adds another layer of security on top of TCP by encrypting all data using SSL/TLS (Secure Sockets Layer/Transport Layer Security) protocols.

Your browser initiates an HTTPS handshake with these steps:

  • Your browser sends a ClientHello message to the server indicating its supported SSL/TLS versions and cipher suites (encryption algorithms).
  • The server replies with a ServerHello message choosing one SSL/TLS version and cipher suite from those offered by your browser.
  • The server also sends its digital certificate signed by a trusted Certificate Authority (CA) proving its identity.
  • Your browser verifies the certificate against its list of trusted CAs and checks if it matches with example.com.
  • If everything checks out, your browser generates a random symmetric key for encryption and sends it to
    the server encrypted with its public key.
  • The server decrypts this key using its private key and sends back an encrypted Finished message indicating readiness.
  • Your browser decrypts this message using its symmetric key and sends back another encrypted Finished message confirming completion.

This way both your browser and
the server agree on an encryption key for secure communication.

Step 4: HTTP request

Now that your browser has established both TCP
and HTTPS connections, it’s time to send the actual HTTP (Hypertext Transfer Protocol) request to the server. The request contains the following information:

  • The HTTP method (usually GET for retrieving data or POST for submitting data)
  • The path of the resource you want to access (/page1)
  • The HTTP version (usually HTTP/1.1 or HTTP/2)
  • Additional headers that provide more information about your browser, the type of content it accepts, cookies, etc.

Here’s an example of an HTTP GET request:
`

GET /page1 HTTP/1.1
Host: example.com
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/89.0.4389.82 Safari/537.36
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8

Step 5: Server processing

Upon receiving the HTTP request, the server processes it and generates an appropriate response. This may involve querying databases, executing server-side scripts, or fetching static files, depending on the requested resource. Once the server has prepared the response, it sends it back to your browser over the established TCP and HTTPS connections.

Step 6: HTTP response

The server’s response is also an HTTP message with the following information:

  • The HTTP version (e.g., HTTP/1.1 or HTTP/2)
  • The status code indicating the result of the request (e.g., 200 OK for success, 404 Not Found for a missing resource)
  • Additional headers providing more information about the server, the content type, the content length, etc.
  • The actual content (HTML, images, videos, etc.) of the requested resource

Here’s an example of an HTTP 200 OK response:

HTTP/1.1 200 OK
Content-Type: text/html; charset=UTF-8
Content-Length: 12345

<!DOCTYPE html>
<html>
<head>
<title>Page 1</title>
...

Step 7: Rendering the page

Now that your browser has received the response, it starts parsing the HTML content and rendering the page on your screen. This involves several sub-steps:

  1. The browser builds the DOM (Document Object Model), a tree-like structure representing the HTML elements and their hierarchy.
  2. The browser retrieves and applies CSS (Cascading Style Sheets) rules to style the DOM elements.
  3. The browser executes JavaScript code (if any) that may manipulate the DOM, fetch additional resources, or provide interactivity.
  4. The browser calculates the layout and position of each DOM element based on the CSS rules and the available screen space.
  5. The browser paints the final representation of the page on your screen, including images, videos, and other media elements.

Step 8: Closing the connection

Once the page is fully rendered, your browser may close the TCP and HTTPS connections to the server, unless you have enabled HTTP Keep-Alive or are using HTTP/2 multiplexing features that allow multiple requests and responses to share the same connection.

And that’s it! You’ve now seen the intricate dance of all the underlying events that occur every time you request more cat memes from a site…

Well, sort of 😬

In actuality, this is still a relatively high level view of all of the technologies, events, and protocols that make the internet possible. We didn’t cover a lot of interesting details that allow for each of the topics explained above to even be possible. But this is a blog post… not a book!

If you are interested in learning all of those fascinating details in a fun and engaging “comic book” style type of writing, then check out this book on How the Internet Really Works, which I highly recommend:

How the Internet Really Works

internet

It’s amazing how much is going on behind the scenes, and understanding these details can help you appreciate the marvel of modern web technologies. So the next time you visit a website, remember the intricate ballet of protocols, connections, and data transfers that make it all possible.

Quantum Computing and AI Tie the Knot — April 13, 2018

Quantum Computing and AI Tie the Knot

In 2018, quantum technicians and daring developers are using quantum algorithms to transform the field of artificial neural network optimization: the bees knees of machine learning and AI. So we can say with some confidence that thanks to quantum algorithms, the future of quantum computing and artificial intelligence are hopelessly entangled. So let’s take a deep dive into the quantum algorithms that are making waves in the digital age. I’ll be paying special attention to quantum annealing (rhymes with feeling), a unique animal that seems to thrive in an AI-rich area where classical algorithms often struggle or altogether fail: training artificial neural networks.

Trouble training your neural net? Join the club…

Rather amazingly, you can train artificial neural nets such as RNNs and CNNs to get wise and not make the same mistake twice. It’s this power to follow Esther Dyson’s advice that makes neural nets the intelligence engine that drives machine learning and AI. That said, training neural networks is a notoriously tricky task. But this hasn’t stopped researchers and coders from working furiously over the last few years to find new ways to reduce training errors with bleeding-edge optimization algorithms. The first stab at the error-reduction problem is best known as hill climbing. Let’s run through it.

Hill climbing

Optimization algorithms that belong to the hill climbing club always check for the gradient (more or less the steepness of a graphed function’s slope) before making their next move. But this runs a real risk of missing out on the real action going on in the graph’s landscape. Two enemies hill climbers often find themselves facing are the plateau problem and the local minima problem. In a word, these problems are the hiker’s equivalent to getting lost in a mirage-riddled desert, or getting stuck in a small muddy valley. But let’s dig deeper…

blog1.png

The plateau problem

When an optimization process enters a plateau, it means it’s getting roughly the same output (y) for every input (x). Because the slope of the function is at or near zero for long flat stretches, an optimization algorithm can run out of time before it finds the edge. And like a shimmering desert mirage, the long stretches of flat function can create the illusion that you’ve reached an optimal state (in this case the global minimum) when you’re nowhere near it.

blog2.png

The local minima problem

A local minimum is a relatively small valley in the graph of a function whose deepest and most important valley lies elsewhere. You can think of the optimization process (when it’s searching for the lowest value in a function) as a beach ball: it will roll downhill and eventually stop at the lowest point in the immediate landscape, even if there’s a much deeper valley on the other side of a nearby hill. That’s the problem.

blog3.png

The most exciting solution

There are a number of alternatives to conventional hill climbing that can help you get out of the dreaded valleys posed by the local minima problem and the desert mirages posed by the plateau problem. But for the purposes at hand, let’s just focus on the most exciting solution: simulated annealing. This is a wild breed of optimization animal that is tackling valleys and plateaus in a computationally clever way that’s well worth at least a couple paragraphs of pondering…

The hottest and coolest classical optimization algorithm around

To cut to the chase, simulated annealing steals from physics to tie time and temperature together in a single elegant algorithm. Yes, you read that right: an algorithm with a temperature parameter. When you run a simulated annealing algorithm, it begins with a completely random, frenetic series of selections from the entire landscape of the function at hand. This is the hot phase of the process. But as the temperature parameter drops with time, the random selections cover an ever-narrower range of the landscape. Finally, we enter the cool phase of the process as the algorithm begins to home in on (with a little luck) the deepest valley or the highest peak, where the holy grail of optimization lies: the global minimum or maximum.

Although the code found in simulated annealing algorithms generally contains some heavy math, the underlying connection between time and temperature is quite easy to grasp. Just picture something hot moving wildly throughout an unknown landscape, hitting everything in sight and reporting back a very rough picture of the lay of the land. Then you can think of progressively colder things moving ever-more slowly and cautiously through an ever-narrower region of the landscape, documenting the details as they creep further down into the deepest valley or up onto the highest peak… Okay, if you’re still not sure what on earth I’m talking about, here’s an excellent animation that should do the trick.

Quantum annealing (oh, what a feeling)

Simulated annealing can often get you out of a pinch when the other alternatives to conventional hill climbing come up short. But it’s an extremely specialized approach, and it suffers from at least one chilling drawback: you have to run the algorithm for an infinite amount of time to smoothly reach absolute zero and thus guarantee that you reach the true global minimum or maximum in the energy landscape. Since you probably don’t have an eternity to spare, you will never really know if your optimization solution is caught in yet another trap.

Enter quantum annealing. First, it’s important to keep in mind that quantum annealing algorithms in their basic form are remarkably similar to simulated annealing algorithms. Why? Because quantum tunneling strength plays the same role in quantum annealing as temperature does in simulated annealing. As time passes, the quantum tunneling strength in the quantum annealer drops dramatically, just as the temperature in the simulated annealer drops dramatically. It’s also easy to visualize the similarity between tunneling-strength and temperature. As time passes and quantum tunneling strength decreases, the system gets cozier and cozier with each progressively deeper valley in the energy landscape, and less and less inclined to tunnel its way out. Eventually, it gives up tunneling altogether when it finds itself (ideally) at the bottom of the deepest and coziest valley in the energy landscape (AKA the global minimum).

blog4.jpeg

Not your grandmother’s quantum computer

The first difference your bound to notice between relatively conventional quantum computers and quantum annealing computers is the number of qubits they use. While the state-of-the-art in conventional quantum computers is pushing a few dozen qubits in 2018, the leading quantum annealer has more than 2000 qubits. Of course, the trade-off is that quantum annealers are not universal but specialized quantum computers that technically tackle only optimization problems and sampling problems. Because solving optimization problems is considered one of the key paths to the AI promised land, I’m going to focus on it from here on out.

A dizzying state of disarray

Before we apply the quantum annealing algorithm to the pool of qubits in our quantum annealer, they’re a mess: a maximally cloudy and unconnected configuration. This means we start out knowing nothing about the quantum system, which may be in any of 2n different states (where n is the number of qubits). For a quantum annealer with 2000 qubits, that’s a crazy number of possible states. If you have any doubts about that, try plugging 2²⁰⁰⁰ into your favorite calculator for a second opinion.

The quantum wishing well

Individual qubits always start out in an initial state of cloudy superposition that places them at the minimum possible energy. Physicists like to visualize this lowest-energy state as the bottom of a quantum potential well that looks sort of like a big letter U.

U

0/1

Then quantum annealing comes along and forces the state of superposition into two halves, two states, two bottoms of the well: 0 and 1. The result looks more like a big letter W:

W

0 1

The next step for the quantum annealer is to start loading the dice to favor the house in the quantum probability game.

Biases

With the help of an applied magnetic field, the quantum annealer nudges each qubit into being heavily biased toward 0 or 1: favoring either the first or the second dip in the W above.

Couplings

While quantum annealers are loading the dice (that is, individual qubits) with biases via magnetic fields, they are also busy tying together pairs of dice with theoretical threads via couplers. Specifically, a coupler can do one of two things. It can guarantee that a pair of qubits are always in the same state: either both 0 or both 1. Or it can ensure that two neighboring qubits are always in the opposite state: 0 and 1, or 1 and 0. The quantum coupler uses (surprise, surprise) quantum entanglement to tie qubits together and create the couplings.

Sculpting an energy landscape

As an aspiring developer working with a quantum annealer, it’s your job to essentially load all the quantum dice by coding a collection of biases and couplings that define the optimization problem you want your trusty annealer to solve. Another way to look at it is that you are sculpting, or at least generating, a sophisticated energy landscape of peaks and valleys that represent all possible outcomes in your optimization problem. Then you are setting the quantum annealer loose to search and ferret out the very bottom of that energy landscape’s deepest valley, which corresponds to the optimal solution. If you’re consistently successful, then your quantum annealing prowess may help power a new generation of machine learning and AI for posterity.

Quantum computing and AI news

On August 31st, 2017, the Universities Space Research Association (USRA) announced that in partnership with NASA and Google it had upgraded the quantum annealing computer at the Quantum Artificial Intelligence Lab(Quantum AI Lab) to a D-Wave 2000Q. With nearly twice as many qubits as its predecessor and a new knack for “adiabatic quantum computing,” the latest D-Wave is going after bigger fish in the optimization-problem pond. The USRA team has even got their eye on using quantum algorithms and the D-Wave to tackle “challenging computational problems involved in NASA missions.” Partner Google, on the other hand, has their eye on AI:

“We are particularly interested in applying quantum computing to artificial intelligence and machine learning.”

But it’s not just Google and NASA that have access to the Quantum AI Lab. Believe it or not, you may too. If you’re a qualified candidate, you might just get some quality time with the latest D-Wave to try out your genius idea. In the Lab’s own words, “the call is open.”

If you liked this article I would be super excited if you could share with your curious friends. Anyway, thanks again for reading have a great day!

Demystifying Quantum Gates — One Qubit At A Time — February 27, 2018

Demystifying Quantum Gates — One Qubit At A Time

(I’ve written an introduction to quantum computing found here. If you are brand new to the field, it will be a better place to start.)

If you want to get into quantum computing, there’s no way around it: you will have to master the cloudy concept of the quantum gate. Like everything in quantum computing, not to mention quantum mechanics, quantum gates are shrouded in an unfamiliar fog of jargon and matrix mathematics that reflects the quantum mystery. My goal in this post is to peel off a few layers of that mystery. But I’ll save you the suspense: no one can get rid of it completely. At least, not in 2018. All we can do today is reveal the striking similarities and alarming differences between classical gates and quantum gates, and explore the implications for the near and far future of computing.

Classical vs quantum gates: comparing the incomparable?

Striking similarities

If nothing else, classical logic gates and quantum logic gates are both logic gates. So let’s start there. A logic gate, whether classical or quantum, is any physical structure or system that takes a set of binary inputs (whether 0s and 1s, apples and oranges, spin-up electrons and spin-down electrons, you name it) and spits out a single binary output: a 1, an orange, a spin-up electron, or even one of two states of superposition. What governs the output is a Boolean function. That sounds fancy and foreboding, but trust me, it’s not. You can think of a Boolean function as nothing more than a rule for how to respond to Yes/No questions. It’s as simple as that. The gates are then combined into circuits, and the circuits into CPUs or other computational components. This is true whether we’re talking about Babbage’s Difference Engine, ENIAC, retired chess champion Deep Blue, or the latest room-filling, bone-chilling, headline-making quantum computer.

Alarming differences

Classical gates operate on classical bits, while quantum gates operate on quantum bits (qubits). This means that quantum gates can leverage two key aspects of quantum mechanics that are entirely out of reach for classical gates: superposition and entanglement. These are the two concepts that you’ll hear about most often in the context of quantum computing, and here’s why. But there’s a lesser known concept that’s perhaps equally important: reversibility. Simply put, quantum gates are reversible. You’ll learn a lot about reversibility as you go further into quantum computing, so it’s worth really digging into it. For now, you can think of it this way — all quantum gates come with an undo button, while many classical gates don’t, at least not yet. This means that, at least in principle, quantum gates never lose information. Qubits that are entangled on their way into the quantum gate remain entangled on the way out, keeping their information safely sealed throughout the transition. Many of the classical gates found in conventional computers, on the other hand, do lose information, and therefore can’t retrace their steps. Interestingly enough, that information is not ultimately lost to the universe, but rather seeps out into your room or your lap as the heat in your classical computer.

V is for vector

We can’t talk about quantum gates without talking about matrices, and we can’t talk about matrices without talking about vectors. So let’s get on with it. In the language of quantum mechanics and computing, vectors are depicted in an admittedly pretty weird package called a ket, which comes from the second half of the word braket. And they look the part. Here’s a ket vector: |u>, where u represents the values in the vector. For starters, we’ll use two kets, |0> and |1>, which will stand-in for qubits in the form of electrons in the spin-up (|0>) and spin-down (|1>) states. These vectors can span any number of numbers, so to speak. But in the case of a binary state such as a spin up/down electron qubit, they have only two. So instead of looking like towering column vectors, they just looked like numbers stacked two-high. Here’s what |0> looks like:

/ 1 \

\ 0 /

Now, what gates/matrices do is transform these states, these vectors, these kets, these columns of numbers, into brand new ones. For example, a gate can transform an up-state (|0>) into a down state (|1>), like magic:

/ 1 \ → / 0 \

\ 0 / \ 1 /

M is for matrix

This transformation of one vector into another takes place through the barely understood magic of matrix multiplication, which is completely different than the kind of multiplication we all learned in pre-quantum school. However, once you get the hang of this kind of math, it’s extremely rewarding, because you can apply it again and again to countless otherwise incomprehensible equations that leave the uninitiated stupefied. If you need some more motivation, just remember that it was through the language of matrix mathematics that Heisenberg unlocked the secrets of the all-encompassing uncertainty principle.

All the same, if you’re not familiar with this jet-fuel of a mathematical tool, your eyes will glaze over if I start filling this post with big square arrays of numbers at this point. And we can’t let that happen. So let’s wait a few more paragraphs for the matrix math and notation. Suffice it to say, for now, that we generally use a matrix to stand-in for a quantum gate. The size and outright fear-factor of the matrix will depend on the number of qubits it’s operating on. If there’s just one qubit to transform, the matrix will be nice and simple, just a 2 x 2 array with four elements. But the size of the matrix balloons with two, three or more qubits. This is because a decidedly exponential equation that’s well worth memorizing drives the size of the matrix (and thus the sophistication of the quantum gate):

2^n x 2^n = the total number of matrix elements

Here, n is the number of qubits the quantum gate is operating on. As you can see, this number goes through the roof as the number of qubits (n) increases. With one qubit, it’s 4. With two, it’s 16. With three, it’s 64. With four, it’s… hopeless. So for now, I’m sticking to one qubit, and it’s got Pauli written all over it.

The Pauli gates

The Pauli gates are named after Wolfgang Pauli, who not only has a cool name, but has managed to immortalize himself in two of the best-known principles of modern physics: the celebrated Pauli exclusion principle and the dreaded Pauli effect.

The Pauli gates are based on the better-known Pauli matrices (aka Pauli spin matrices) which are incredibly useful for calculating changes to the spin of a single electron. Since electron spin is the favored property to use for a qubit in today’s quantum gates, Pauli matrices and gates are right up our alley. In any event, there’s essentially one Pauli gate/matrix for each axis in space (X, Y and Z).

So you can picture each one of them wielding the power to change the direction of an electron’s spin along their corresponding axis in 3D space. Of course, like everything else in the quantum world, there’s a catch: this is notour ordinary 3D space, because it includes an imaginary dimension. But let’s let that slide for now, shall we?

Mercifully, the Pauli gates are just about the simplest quantum gates you’re ever going to meet. (At least the X and Z-gates are. The Y is a little weird.) So even if you’ve never seen a matrix in your life, Pauli makes them manageable. His gates act on one, and only one, qubit at a time. This translates to simple, 2 x 2 matrices with only 4 elements a piece.

The Pauli X-gate

The Pauli X-gate is a dream come true for those that fear matrix math. No imaginary numbers. No minus signs. And a simple operation: negation. This is only natural, because the Pauli X-gate corresponds to a classical NOT gate. For this reason, the X-gate is often called the quantum NOT gate as well.

In an actual real-world setting, the X-gate generally turns the spin-up state |0> of an electron into a spin-down state |1> and vice-versa.

|0>   -->   |1>   OR   |1> --> |0>

A capital “X” often stands in for the Pauli X-gate or matrix itself. Here’s what Xlooks like:

/ 0 1 \

\ 1 0 /

In terms of proper notation, applying a quantum gate to a qubit is a matter of multiplying a ket vector by a matrix. In this case, we are multiplying the spin-up ket vector |0> by the Pauli X-gate or matrix X. Here’s what X|0> looks like:

/ 0 1 \ /1\

\ 1 0 / \0/

Note that you always place the matrix to the left of the ket. As you may have heard, matrix multiplication, unlike ordinary multiplication, does not commute, which goes against everything we were taught in school. It’s as if 2 x 4 was not always equal to 4 x 2. But that’s how matrix multiplication works, and once you get the hang of it, you’ll see why. Meanwhile, keeping the all-important ordering of elements in mind, the complete notation for applying the quantum NOT-gate to our qubit (in this case the spin-up state of an electron), looks like this:

X|0> = / 0 1 \ /1\ = /0\ = |1>

\ 1 0 / \0/ \1/

Applied to a spin-down vector, the complete notation looks like this:

X|1> = / 0 1 \ /0\ = /1\ = |0>

\ 1 0 / \1/ \0/

Despite all the foreign notation, in both of these cases what’s actually happening here is that a qubit in the form of a single electron is passing through a quantum gate and coming out the other side with its spin flipped completely over.

The Pauli Y and Z-gates

I’ll spare you the math with these two. But you should at least know about them in passing.

Of the three Pauli gates, the Pauli Y-gate is the fancy one. It looks a lot like the X-gate, but with an i (yep, the insane square root of -1) in place of the regular 1, and a negative sign in the upper right. Here’s what Y looks like:

/ 0 -i \

\ i 0 /

The Pauli Z-gate is far easier to follow. It looks kind of like a mirror image of the X-gate above, but with a negative sign thrown into the mix. Here’s what Zlooks like:

/ 1 0 \

\ 0 -1 /

The Y-gate and the Z-gate also change the spin of our qubit electron. But I’d probably need to delve into the esoteric mysteries of the Bloch sphere to really explain how, and I’ve got another gate to go through at the moment…

The Hadamard gate

While the Pauli gates are a lot like classic logic gates in some respects, the Hadamard gate, or H-gate, is a bona fide quantum beast. It shows up everywhere in quantum computing, and for good reason. The Hadamard gate has the characteristically quantum capacity to transform a definite quantum state, such as spin-up, into a murky one, such as a superposition of both spin-up and spin-down at the same time.

Once you send a spin-up or spin-down electron through an H-gate, it will become like a penny standing on its end, with precisely 50/50 odds that it will end up heads (spin-up) or tails (spin-down) when toppled and measured. This H-gate is extremely useful for performing the first computation in any quantum program because it transforms pre-set, or initialized, qubits back into their natural fluid state in order to leverage their full quantum powers.

Other quantum gates

There are a number of other quantum gates you’re bound to run into. Many of them operate on several qubits at a time, leading to 4×4 or even 8×8 matrices with complex-numbered elements. These are pretty hairy if you don’t already have some serious matrix skills under your belt. So I’ll spare you the details.

The main gates that you will want to be familiar are the ones we covered shown in the graph below:

You should know that other gates exist so here’s a quick list of some of the most widely used other quantum gates, just so you can get a feel for the jargon:

  • Toffoli gateFredkin gate
  • Deutsch gate
  • Swap gate (and swap-gate square root)
  • NOT-gate square root
  • Controlled-NOT gate (C-NOT) and other controlled gates

There are many more. But don’t let the numbers fool you. Just as you can perform any classical computation with a combination of NOT + OR = NOR gates or AND + OR = NAND gates, you can reduce the list of quantum gates to a simple set of universal quantum gates. But we’ll save that deed for another day.

Future gazing through the quantum gateway

As a recent Quanta Magazine article points out, the quantum computers of 2018 aren’t quite ready for prime time. Before they can step into the ring with classical computers with billions of times as many logic gates, they will need to face a few of their own demons. The most deadly is probably the demon of decoherence. Right now, quantum decoherence will destroy your quantum computation in just “a few microseconds.” However, the faster your quantum gates perform their operations, the more likely your quantum algorithm will beat the demon of decoherence to the finish line, and the longer the race will last. Alongside speed, another important factor is the sheer number of operations performed by quantum gates to complete a calculation. This is known as a computation’s depth. So another current quest is to deepen the quantum playing field. By this logic, as the rapidly evolving quantum computer gets faster, its calculations deeper, and the countdown-to-decoherence longer, the classical computer will eventually find itself facing a formidable challenger, if not successor, in the (quite possibly) not too far future.

If you liked this article I would be super excited if you hit the like button 🙂 or share with your curious friends. You can subscribe to this profile and get all my articles sent to you as soon as I write them by clicking the subcribe button! (how awesome?!)

Anyway, thanks again for reading have a great day!

The Need, Promise, and Reality of Quantum Computing — February 1, 2018

The Need, Promise, and Reality of Quantum Computing

Despite giving us the most spectacular wave of technological innovation in human history, there are certain computational problems that the digital revolution still can’t seem to solve. Some of these problems could be holding back key scientific breakthroughs, and even the global economy. Although conventional computers have been doubling in power and processing speed nearly ever two years for decades, they still don’t seem to be getting any closer to solving these persistent problems. Want to know why? Ask any computer scientist, and they’ll probably give you the same answer: today’s digital, conventional computers are built on a classical, and very limited, model of computing. In the long run, to efficiently solve the world’s most persistent computing problems, we’re going to have to turn to an entirely new and more capable animal: the quantum computer.

Ultimately, the difference between a classical computer and a quantum computer is not like the difference between an old car and a new one. Rather, it’s like the difference between a horse and a hawk: while one can run, the other can fly. Classical computers and quantum computers are indeed that different. Here we take a good look at where the key difference lies, and take a deep dive into what makes quantum computers unique. However, what you won’t find here is a final explanation for how quantum computers ultimately work their magic. Because no one really knows.

The hard limits of classical computing

Moore’s law, Shmore’s Law

For several decades now, the sheer speed and computational power of conventional computers has been doubling every two years (and by some accounts just eighteen months). This is known as Moore’s law. Although the breakneck pace of progress may have finally begun to slow slightly, it’s still more or less true that the room-filling supercomputer of today is the budget laptop of tomorrow. So at this rate, it seems reasonable to assume that there is no computational task that a conventional computer couldn’t eventually tackle in the foreseeable future. Nonetheless, unless we’re talking trillions of years (and then some), that’s simply not a safe assumption when it comes to certain stubborn tasks.

The conventional computer’s Achilles heel

The fact is that a computational task such as quickly finding the prime factors for very large integers is probably out of reach for even the fastest conventional computers of the future. The reason behind this is that finding the prime factors of a number is a function that has exponential growth. What’s exponential growth? Well let’s dive into it because this is a very important piece for understanding why quantum computers have so much potential and why classical computers fall short.

Quick introduction to exponential growth

Some things grow at a consistent rate and somethings grow faster as the number of “things” you have also grows. When growth becomes more rapid (not constant) in relation to the growing total number, then it is exponential.

Exponential growth is extremely powerful. One of the most important features of exponential growth is that, while it starts off slowly, it can result in enormous quantities fairly quickly — often in a way that is shocking.

This definition can be a bit hard to get your head around without an example, so let’s dive into a quick story.

There is a legend in which a wise man, who was promised an award by a king, asks the ruler to reward him by placing one grain of rice on the first square of a chessboard, two grains on the second square, four grains on the third and so forth. Every square was to have double the number of grains as the previous square. The king granted his request but soon realized that the rice required to fill the chessboard was more than existed in the entire kingdom and would cost him all of his assets.

Exponential Growth of Rice

The number of grains on any square reflects the following rule, or formula:

In this formula, k is the number of the square and N is the number of grains of rice on that square.

  • If k = 1 (the first square), then N = 2⁰, which equals 1.
  • If k = 5 (the fifth square), then N = 2⁴, which equals 16.

This is exponential growth because the exponent, or power, increases as we go from square to square.

To conceptualize this further, I’ve included a graph of what exponential growth looks like in relation to the input quantity of an exponential function.

As you can see, the function starts relatively slow, but soon shoots up to numbers that no classical computer would be able to compute with large enough input sizes.

Real exponential functions have real consequences

Okay, enough storytelling. Let’s move on to real-world exponential problems like the one we were talking about earlier. Prime Factorization.

Take the number 51. See how long it takes you to find the two unique prime numbers that you can multiply together to generate it. If you’re familiar with these kinds of problems, it probably only took you a few seconds to find that 3 and 17, both primes, generate 51. As it turns out, this seemingly simple process, lies at the heart of the digital economy and is the basis for our most secure types of encryption. The reason we use this technique in encryption is because as the numbers used in prime factorization get larger and larger, it becomes increasingly difficult for conventional computers to factor them. Once you reach a certain number of digits, you find that it would take even the fastest conventional computer months, years, centuries, millennia, or even countless eons to factor it.

With this idea in mind, even if computers continue to double in processing power every two years for the foreseeable future (and don’t bet on it), they will always struggle with prime factorization. Other equally stubborn problems at the heart of modern science and mathematics include certain molecular modeling and mathematical optimization problems which promise to crash any supercomputer that dares to come anywhere near them.

Below is a great illustration from IBM Research that shows the most complex molecule (F cluster) that we can simulate on our the worlds most powerful supercomputer. As you can see (in the bottom left of the image), the molecule is not very complex at all, and if we want to model more complex molecules to discover better drug treatments and understand our biology, then we will need a different approach!

Molecular Simulation Problem. Source: IBM Research

Enter the quantum computer

Conventional computers are strictly digital and rely purely on classical computing principles and properties. Quantum computers, on the other hand, are strictly quantum. Accordingly, they rely on quantum principles and properties — most importantly superposition and entanglement — that make all the difference in their almost miraculous capacity to solve seemingly insurmountable problems.

Superposition

To make sense out of the notion of superposition, let’s consider the simplest possible system: a two-state system. An ordinary, classical two-state system is like an On/Off switch that is always in one state (On) or another (Off). Yet a two-state quantum system is something else entirely. Of course, whenever you measure its state, you will find that it is indeed either on or off, just like a classical system. But between measurements, a quantum system can be in a superposition of both on and off states at the same time, no matter how counter-intuitive, and even supernatural, this may seem to us.

Superposition. Source: IBM Research

Generally speaking, physicists maintain that it’s meaningless to talk about a quantum system’s state, such as its spin, prior to measurement. Some even argue that the very act of measuring a quantum system causes it to collapse from a murky state of uncertainty to the value (On or Off, Up or Down) that you measure. Although probably impossible to visualize, there’s no escaping the fact that this mysterious phenomenon is not only real but gives rise to a new dimension of problem-solving power that paves the way for the quantum computer. Keep the idea of superposition in mind. We will come back to how this is used in quantum computing in a bit.

How superposition is even possible is beyond the scope of this article, but trust that it has been proven to be true. If you want to understand what gives rise to superposition then you are going to first need to understand the idea of Wave/Particle Duality.

Entanglement

Okay, on to the next property of quantum mechanics which we need to leverage to create a quantum computer.

It is known that once two quantum systems interact with one another, they become hopelessly entangled partners. From then on, the state of one system will give you precise information about the state of the other system, no matter how far the two are from one another. Seriously, the two systems can be light years apart and still give you precise and instantaneous information about each other. Let’s illustrate this with a concrete example as this caused even Einstein to puzzle about how this could be possible. (Einstein famously referred to this phenomenon as “Spooky action at a distance”)

Quantum Entanglement. Source: IBM Research

Suppose you have two electrons, A and B. Once you have them interact in just the right way, their spins will automatically get entangled. From then on, if A’s spin is Up, B’s spin will be Down, like two kids on a seesaw, except that this holds true even you take A and B to opposite ends of the Earth (or the galaxy, for that matter). Despite the thousands of miles (or light years) between them, it’s been proven that if you measure A to have spin Up, you will know instantly that B’s spin is Down. But wait: we’ve already learned that these systems don’t have precise values for states such as spin, but rather exist in a murky superposition, prior to measurement. So does our measuring A actually cause B to instantaneously collapse to the opposite value, even when the two are light years apart? If so, then we have yet another problem on our hands, because Einstein taught us that no causal influence, such as a light signal, between two systems can travel faster than the speed of light. So what gives? All told, we honestly don’t know. All we know is that quantum entanglement is real and that you can leverage it to work wonders.

The qubit

The qubit plays the same role in quantum computing as the bit does in classical computing: its the fundamental unit of information. However, compared to a qubit, a bit is downright boring. Although both bits and qubits generate one of two states (a 0 or a 1) as the outcome of a computation, a qubit can simultaneously be in both 0 and 1 states prior to that outcome. If this sounds like quantum superposition, it is. Qubits are quantum systems par excellence.

Just as conventional computers are built bit by bit with transistors that are either On or Off, quantum computers are built qubit by qubit with electrons in spin-states that are either Up or Down (once measured, of course). And just as transistors in On/Off states are strung together to form the logic gates that perform classical computations in digital computers, electrons in Up/Down spin-states are strung together to form the quantum gates that perform quantum calculations in quantum computers. Yet stringing together individual electrons (while preserving their spin states) is far, far easier said than done.

Quantum Algorithms. Source: IBM Research

Where are we today?

While Intel is busy pumping out conventional chips with billions of transistors a piece, the world’s leading experimental computer scientists are still struggling to build a quantum computer “chip” with more than a handful of qubits. Just to give you a sense of how early we are in the history of quantum computing, it was a big deal when recently IBM unveiled the largest quantum computer in the world with an astonishing… wait for it… 50 qubits. Nonetheless, it’s a start, and if anything like Moore’s law applies to quantum computers, we should get into the hundreds in a few years, and the thousands in a few more. A billion? I wouldn’t hold your breath, but then again, you don’t need a billion qubits to outperform the daylights out of a conventional computer in some key categories, such as prime categorization, molecular modeling and a slew of optimization problems that no conventional computer can touch today.

The quantum computers of 2018

All the same, as of right now, nearly every quantum computer is a multi-million dollar borderline mad-scientist project that looks the part. You generally find them in R&D departments at large IT companies like IBM, or in the experimental physics wing of large research universities, like MIT. They have to be super-cooled to a hair above absolute zero (that’s colder than intergalactic space), and experimenters need to use microwaves of a precise frequency to communicate with each qubit in the computer individually. Needless to say, that doesn’t scale. But neither did the vacuum tubes of the earliest conventional computers, so let’s not judge this first generation too harshly.

Roadblocks awaiting breakthroughs

The primary reason that quantum computers haven’t gone mainstream yet is that the best minds and inventors in the world are still struggling with high error rates and low numbers of qubits. As we address these two problems together, we will rapidly increase what IBM calls each computers’ “quantum volume,” a way of visualizing the sheer quantity of useful calculations a quantum computer can perform.

Quantum Volume. Source: IBM Research

In short, for quantum computing to take off and quantum-powered Macbooks to start flying off the shelves, we need far more qubits and far fewer mistakes. That’s going to take time, but at least we know what we’re aiming for, and what we’re up against.

Myths vs explanations

Although we know that quantum computers can easily do things that no conventional computer can dream of doing, we don’t really know how they do it. If this sounds surprising, given that the first-generation of quantum computers already exists, keep in mind the word quantum. We’ve been using quantum mechanics to solve problems for a century now, and we still don’t really know how it works. Quantum computing, as a member of the quantum family, is in the same boat. Michael Nielsen (who basically wrote the book on the subject), has argued convincingly that any explanation of quantum computing is destined to miss the mark. After all, according to Nielsen, if there were a straightforward explanation for how a quantum computer works (that is, something you could visualize), then it could be simulated on a conventional computer. But if it could be simulated on a conventional computer, then it couldn’t be an accurate model of a quantum computer, because a quantum computer by definition does what no conventional computer can do.

According to Nielsen, the most popular myth that pretends to explain quantum computation is called quantum parallelism. Because you’re going to hear the quantum parallelism story a lot, let’s look at it for a moment. The basic idea behind quantum parallelism is that quantum computers, unlike their conventional counterparts, explore the full spectrum of possible computational outcomes/solutions simultaneously (i.e. in a single operation), while digital computers must plod along, looking at each solution in sequence. According to Nielsen, this part of the quantum-parallelism story is roughly right. However, he sharply criticizes the rest of the story, which goes on to say that after surveying the full spectrum of solutions, quantum computers pick out the best one. Now that, according to Nielsen, is a myth. The truth, he insists, is that what quantum computers, like all quantum systems, are really doing behind the scenes is entirely out of our reach. We see the input, and the output, and what happens in between is sealed in mystery.

If you liked this article I would be super excited if you share with your curious friends. I’ve got much more like it coming and if you want to be notified whenever I post a new article you can just subscribe to this blog and have the articles sent to you as soon as I write them! (how awesome?!)

Anyway, thanks again for reading have a great day!

12 Most Influential Books Every Software Engineer Needs to Read — March 16, 2015

12 Most Influential Books Every Software Engineer Needs to Read

This is a question that I get a lot, especially from co-workers or friends that are just beginning their journey as a software craftsman.

What book should I read to become a better developer? Do I need to read books?

I think it’s a great question, and it is one that I asked many of my mentors as I was becoming a software engineer. The problem was that many people suggested different books on different topics. All the books they suggested were great in their own right, but no one was able to give me a list that would be the ESSENTIAL books, the MUST READS, that any engineer with hopes of being great should most certainly read.

Well, I’ve learned a lot from my mentors and realized that I still had a lot to learn with the many different books that were suggested to me. I decided to develop a routine to read one book a month in my profession field (software engineering). Over the years, I’ve aggregated a list that, I believe, to be MUST READS for anyone that wants to be a top tier developer.

Now let me state the obvious – just reading all of these books on the list will not make you a great developer. That will come with years of experience and applying the principles in these books into real practices and developing your problem-solving skills in the real world.

However, reading these books will help you avoid the major pitfalls and mistakes that many developers make early off in their careers. I wish that someone would have told me about these books just starting out, but I was lucky enough to have found and read them over the years. You might have read some of these books in college for your computer science or engineering classes. Maybe at the time, you didn’t think they were important, but I can say first hand that I’ve used and applied many principles from each and every one of these books.

Let me also point out that this is not an exhaustive list. Many great books come out every year. These are just the ones that have had the biggest impact on myself and my career. Also, these are mostly language agnostic, and can be applied using any of the many software languages.  (I will do another post with the best books targeted at certain technology platforms and stacks)

Well, let’s get to it then! (drum roll, please)

THE LIST

(All these are essential, but I put them in descending order from which ones had the biggest impact on me. I have also provided the link (click on the book cover) to where you can purchase the book on Amazon if interested. Read the reviews and decide for yourself!)

download (3)  12. Working Effectively with Legacy Code

I love this book because almost every software developer, at some point in their career, has to support and work with a legacy system. In this book, Michael Feathers offers start-to-finish strategies for working more effectively with large, untested legacy code bases. This book draws on material Michael created for his renowned Object Mentor seminars: techniques Michael has used in mentoring to help hundreds of developers, technical managers, and testers bring their legacy systems under control.

51WIpM70FEL._SL160_  11. The Mythical Man-Month

This book is a classic, but recently revised and corrected. The amazing thing is how relevant the book still is to software product development. If you are involved in software, this book is a must-read. The most valuable part of the book, I believe, is the “plan to throw out” prototype chapter. While the goal is always to make a bigger, better, fast whatever, it is almost an axiom that you WILL build something that has to be discarded and reworked. This happens every time, I can tell you from first-hand experience. Therefore, it is vital to plan to throw out so you can migrate your users to whatever will follow. If you dream that the first product is THE ONE, you risk abandoning them on a product that will inevitably evolve. Planning to throw-away also helps meet the schedule goals by setting reasonable milestones that can be obtained.

download (2)  10. Design Patterns

If you are planning to be an architect or designer of a system, you will most likely be required to read this book. Hailed as one of the greatest software development books ever written, this book goes into great detail on the many different design patterns that have been developed over the years to help software engineers avoid and handle common problems that the industry faces. Following the strategies in this book will allow you to build higher quality, flexible, and maintainable software. This book also goes by the name “Gang of Four” in software groups because of its famous four authors that put this book together.

 pp2e  9. Programming Pearls (2nd Edition)

This book is slightly different from the other books on the list. I would say this book helps a person “think like a programmer”. Programming Pearls is a compendium of 15 columns previously published in Communications of the ACM. The columns cover a broad range of topics related to programming: from requirements gathering to performance tuning. The focus is primarily on coding techniques and algorithms.

Each column has been reorganized as a chapter. Chapters usually start with the presentation of a practical problem. Then various solutions are presented and are used as lessons to be learned. The writing style is clear and fun.

Programming Pearls is not a usual book teaching new programming concepts. Although it contains good and sometimes quite novel ideas, the aim of the book is not to teach something new but to help you become a better problem solver.

31GBgcA5PML._SL160_   8. CODE: The Hidden Language of Computer Hardware and Software

This book cleared up a lot of the “Magic” that goes into creating and developing complex systems. There are so many abstractions these days that the low-level details are sometimes unknown to the developer. Though you may not find yourself using this book 24/7 in practice…I believe it is a good idea to have an understanding of what you are building on top of and how the whole orchestration works. It may come in handy when you need to open up that “Black Box” and deep dive into the software or hardware to fix a pesky bug. “CODE: The Hidden Language of Computer Hardware and Software” by Charles Petzold deals with a number of programming concepts starting from number systems – decimal, octal, binary to high-level languages. The book explains packet based communication protocols and TCP. Many chapters are about hardware concepts, and five chapters are devoted to software and teach about the operating system, floating point arithmetic, and GUIs.

41Jon2rS8nL._SL160_  7.The Art of Computer Programming

This is another classic. This was written by the famous computer scientist Professor Donald Knuth and is highly praised by many of the top programmers in the industry. Even Bill Gates is quoted saying

If you think you’re a really good programmer… read [Knuth’s] Art of Computer Programming… You should definitely send me a resume if you can read the whole thing.”

The book begins with basic programming concepts and techniques, then focuses more particularly on information structures–the representation of information inside a computer, the structural relationships between data elements and how to deal with them efficiently. Elementary applications are given to simulation, numerical methods, symbolic computing, software, and system design.

51T4YZ3HieL._SL160_  6. Refactoring

“Refactoring” by Martin Fowler is about improving the design of existing code. It is the process of changing a software system in such a way that it does not alter the external behavior of the code, yet improves its internal structure. With refactoring, you can even take a bad design and rework it into a good one. This book offers a thorough discussion of the principles of refactoring, including where to spot opportunities for refactoring, and how to set up the required tests. There is also a catalog of more than 40 proven refactorings with details as to when and why to use the refactoring, step by step instructions for implementing it, and an example illustrating how it works The book is written using Java as its principal language, but the ideas apply to any OO language.

41znMZniZ1L._SL160_  5. Clean Code

“Clean Code,” written by Robert C. Martin, is divided into three parts. The first describes the principles, patterns, and practices of writing clean code. The second part consists of several case studies of increasing complexity. Each case study is an exercise in cleaning up code—of transforming a code base that has some problems into one that is sound and efficient. The third part is the payoff: a single chapter containing a list of heuristics and “smells” gathered while creating the case studies. The result is a knowledge base that describes the way we think when we write, read, and clean code.

41kXXE4mAKL._SL160_  4. Introduction to Algorithms

This has to be the single best book for understanding and using algorithms (which you will be doing a lot of in software development). Some books on algorithms are rigorous but incomplete; others cover masses of material but lack rigor. Introduction to Algorithms uniquely combines rigor and comprehensiveness. The book covers a broad range of algorithms in depth, yet makes their design and analysis accessible to all levels of readers. Each chapter is relatively self-contained and can be used as a unit of study. The algorithms are described in English and in a pseudocode designed to be readable by anyone who has done a little programming. The explanations have been kept elementary without sacrificing depth of coverage or mathematical rigor.The first edition became a widely used text in universities worldwide as well as the standard reference for professionals. The second edition featured new chapters on the role of algorithms, probabilistic analysis, and randomized algorithms, and linear programming.

41AJV8G0ZTL._SL160_  3. Structure and Interpretation of Computer Programs

With an analytical and rigorous approach to problem solving and programming techniques, this book is oriented toward engineering. Structure and Interpretation of Computer Programs emphasizes the central role played by different approaches to dealing with time in computational models. Its unique approach makes it appropriate for an introduction to computer science courses, as well as programming languages and program design. The book further explains the four best-known paradigms of programming languages – imperative, object-oriented, logic based and applicative programming.

41HXiIojloL._SL160_  2. Pragmatic Programmer

This was one of the first programming books I read. I had a friend recommend it to me in my first professional job. I’m glad he did. Though the book was written in 1999 (I believe), the concepts are the basis of how we go about developing a complex system in a practical manner. Programmers are craftspeople trained to use a certain set of tools (editors, object managers, version trackers) to generate a certain kind of product (programs) that will operate in some environment (operating systems on hardware assemblies). Like any other craft, computer programming has spawned a body of wisdom, most of which isn’t taught at universities or in certification classes. Most programmers arrive at the so-called tricks of the trade over time, through independent experimentation. In The Pragmatic Programmer, Andrew Hunt and David Thomas codify many of the truths they’ve discovered during their respective careers as designers of software and writers of code.

Some of the authors’ nuggets of pragmatism are concrete, and the path to their implementation is clear. They advise readers to learn one text editor, for example, and use it for everything. They also recommend the use of version-tracking software for even the smallest projects and promote the merits of learning regular expression syntax and a text-manipulation language. Other (perhaps more valuable) advice in the book is more light-hearted. In the debugging section, it is noted that “if you see hoof prints think horses, not zebras.” That is, suspect everything, but start looking for problems in the most prominent places. There are recommendations for making estimates of time and expense, and for integrating testing into the development process. You’ll want a copy of The Pragmatic Programmer for two reasons: it displays your own accumulated wisdom more clearly than you ever bothered to state it, and it introduces you to methods of work that you may not yet have considered.

51nWkLCu1SL._SL160_  1. Code Complete 2

And this is it! The number one book (IMHO) to read if you are going to be a great software engineer. Widely considered one of the best practical guides to programming, Steve McConnell’s original CODE COMPLETE has been helping developers write better software for more than a decade. Now this classic book has been fully updated and revised with leading-edge practices—and hundreds of new code samples—illustrating the art and science of software construction. Capturing the body of knowledge available from research, academia, and everyday commercial practice, McConnell synthesizes the most effective techniques and must-know principles into clear, pragmatic guidance. No matter what your experience level, development environment, or project size, this book will inform and stimulate your thinking—and help you build the highest quality code.

Discover the timeless techniques and strategies that help you:

  • Design for minimum complexity and maximum creativity
  • Reap the benefits of collaborative development
  • Apply defensive programming techniques to reduce and flush out errors
  • Exploit opportunities to refactor—or evolve—code, and do it safely
  • Use construction practices that are right-weight for your project
  • Debug problems quickly and effectively
  • Resolve critical construction issues early and correctly
  • Build quality into the beginning, middle, and end of your project

Well, that’s it for now!

Let me know in the comments if you have read any of these or have any other must-reads for software developers!

If you have enjoyed this post, the biggest compliment you could give would be to share this with someone that you think would enjoy it!

Additionally, if you never want to miss a post, subscribe to this blog by clicking the follow button in the bottom right corner! Thanks for reading, have a great day, and never stop learning!