Quantum Computing 101: It's a Kind of Magic

As I sat down to write these lines, the first verses of the Queen song: “It's a kind of magic, it's a kind of magic, a kind of magic (No way)”. Before explaining why, it is worth remembering that this is the sixth text in an ongoing series on quantum computing. The previous texts can be found in the corresponding numbering below: 1, 2, 3, 4 e 5.

The foundations of quantum computing were laid in 1981 by physicist Richard Feynman in a legendary lecture. Feynman later elaborated on his speech in an article published in International Journal of Theoretical Physics. There he pointed out that building computing devices based on quantum principles could unlock powers far greater than those of classical computers [1].

Feynman concluded the '81 lecture with a joke that became famous:

“Nature is not classical, hell, if you want to do a simulation of nature, it better be quantum.” Richard Feynman [1]

Almost 30 years ago, Peter Shor introduced us to the first potentially transformative use of quantum computers. To explain, much of the security of the digital world is based on the assumption that factoring large numbers is a challenging and time-consuming task. Shor showed us how to use Qbits to do this in the blink of an eye, at least relative to classical methods.

Shor's algorithm takes advantage of the principles of quantum superposition and entanglement (entanglement) to perform factorization exponentially faster than the best-known classical algorithms [2]. We don't know when it will happen (or even if it will happen), but it is expected that the method demonstrated by Shor will one day “break” the internet. The algorithm has significant implications for cryptography, particularly in relation to widely used methods such as RSA, which depends precisely on the difficulty of factoring large numbers.

But for tasks less glamorous than factorization, it is difficult to say for sure whether quantum methods are superior to classical ones [3]. However, the search for other quantum applications that are as successful as Shor's algorithm has become something of a random game.

This game, which over the last twenty years has brought together physicists, mathematicians and computer scientists in a joint effort to more clearly identify the power of the quantum realm, appears to be starting to bear fruit.

So that the reader can more clearly understand the objective of the effort, it is worth an additional explanation. In the ideal world, what we would like to have is a number that can be assigned to an arrangement of Qbits to know how many of them would be needed to perform a quantum operation. I recognize that said like that, it seems like something loose. Rephrasing the phrase, what we are looking for is a universal quantum metric.

This means that if the number for this metric is low, it would be easy to simulate the calculation on a laptop. If high, the calculated Qbits would represent the basis for solving a computational problem that would be truly beyond the reach of any classical computer. In short, a calculation that can define whether an arrangement of Qbits generates such “quantum supremacy”.

Let us remember that Qbits represent the physical ingredient that is at the origin of the potential power of quantum devices. They are the representation of something that exists in the universe, but is still unknown to us. The term commonly used to describe this potential is “quantumness”.

The original metric of quantumness it is the same one used by Shor in his algorithm: entanglement. Added to the entanglement, we have already managed to find two more. These are the two that evoke the Queen song that I mentioned at the beginning of the text. We call them magic, but allow me to keep the suspense a little longer before I address them.

Each of the three metrics represents a distinct way of separating the quantum and classical realms. In parallel with the development of quantum computers, physicists began to wonder whether any of the other two metrics would appear outside of quantum computing and in what quantities. Preliminary studies have found that all three appear and that they may offer a new way of understanding varied topics in quantum mechanics, such as the phases of quantum matter and the destructive nature of black holes. I will try to show in this text the topography of this three-part quantum realm.

Entanglement is the “man”

In the 1990s, it seemed obvious that the physical ingredient that made quantum computers powerful would be entanglement. Himself Erwin Schrödinger had identified the connection between distant particles as the characteristic feature of quantum mechanics [4].

Remembering what we saw in first text In this series, entanglement is the phenomenon in which two quantum particles form a shared state. It encapsulates what Einstein called “spooky action at a distance” [5]. It was difficult to reproduce artificially in quantum mechanics at the time, and therefore represented what quantum computers could excel at.

When particles are not entangled, it is possible to track them individually. When they are entangled, modifying or manipulating a particle in a system involves taking into account its connections with other entangled particles. This task grows exponentially as more particles are added. To fully specify the state of n entangled Qbits, you need something like 2^n (2 raised to the nth power) of Cbits (the classic bits, remember?). This means that to calculate the effect of adjusting a Qbit, it is necessary to perform around 2^n classical operations. For three Qbits there are only eight steps. But for 10 Qbits we have 1,024. It is the mathematical definition of exponential increase.

In 2003 an article was published in which the authors devised a simple process to use a classical computer to simulate a quantum “circuit”, which is a specific series of operations performed on Qbits by so-called quantum gates (as we saw in fourth text from the series). Jozsa and Linden, the authors, showed that if you gave a classical algorithm some initial arrangement of Qbits, it would be possible to predict the final arrangement of those Qbits after they had passed through the quantum circuit [6]. The authors proved that, as long as the programmed algorithm simulated a circuit that did not entangle Qbits, it could handle increasingly larger numbers of Qbits without exponentially increasing its execution time.

In other words, Jozsa and Linden showed that an entanglement-free quantum circuit was easy to simulate on a classical computer. In a computational sense, the circuit was not intrinsically quantum. The collection of all these unentangled circuits (or, equivalently, all the arrangements of Qbits that could arise from these unentangled circuits) formed a kind of classical island in a vast quantum sea.

In this sea were the states resulting from truly quantum circuits. Those for which a classical simulation could take billions of years to run. For this reason, entanglement has come to be considered not just a quantum property, but a quantum resource. Keeping with the maritime analogy, it was the necessary tool to reach those unknown depths where “root” quantum algorithms like Shor’s resided. Even today, entanglement is one of the most studied quantum resources in computing, especially its relationship with computational complexity.

Ghosh et al., for example, showed that for a specific class of quantum circuits (the tensor network algorithms – tensor network algorithms), entanglement determines how difficult it is to classically simulate the circuit [7]. What the study basically says is that as soon as we manage to generate a certain amount of entanglement, it is possible to prove that there is no classical algorithm that simulates that situation. 

However, the work of Ghosh et al. is only valid for one type of circuit [7]. Even the work of Jozsa and Linden, 20 years ago, already recognized that entanglement alone could not capture the richness of our quantum ocean. The authors wrote (in my free translation):

“Despite the essential role of entanglement, we argue that it is nevertheless misleading to see it as a key resource for quantum computing power.” Jozsa and Linden [6]. 

A pinch of Magic

In 1998, physicist Daniel Gottisman explained that, in a specific type of quantum circuit (a group of tensor products of Pauli matrices e Clifford Gates), the apparently quintessential quantum quantity (the exponential 2^n) was “easy” simulable by a classical computer [8].

Obviously the author did not pose the question in the terms above. In Gottesman's method, the entanglement operation had a computational cost of approximately zero [8]. It cost essentially nothing. This means that we could tangle as many Qbits as we wanted, and a classical computer would still be able to keep up. It was the theorem of Gottesman–Knill (Gottesman discussed his method with mathematician Emanuel Knill, who helped him formalize it). 

The ability to classically simulate entanglement seemed like a miracle, but there was a catch. The algorithm derived from the Gottesman-Knill theorem could not handle all quantum circuits, only those that were trapped in Clifford gates. If we added, for example, a T gate, which is a seemingly innocuous device that rotates a Qbit in a specific way, the circuit would freeze.

Specifically the T gate, it appeared to manufacture some kind of quantum resource that could not be simulated on a classical computer. Before long, a pair of Russian physicists, Sergey Bravyi and Alexei Kitaev, would give the quantum essence produced by the forbidden rotation of the T gate an attractive name: magic [9].

The authors devised two schemes, known as Bravyi-Kitaev, to perform any quantum calculation. We could include T gates in the circuit itself, or we could use a “magic state” of Qbits that have been primed with T gates by another circuit and feed it into a Clifford circuit [9]. Either way, magic was essential to achieving quantum fulfillment.

Em 2016 Bravyi, em conjunto com o físico David In 2016 Bravyi, together with physicist David Gosset, developed an algorithm to simulate circuits with a lower level of magic in classical computers. The authors' method, although it generated an exponential growth in time to run each added T port, managed to limit this temporal growth. This was not as explosive as other cases [10]. They had developed a somewhat efficient method to classically simulate a magic circuit that contained hundreds of Clifford gates and almost 50 T gates [10]. It was already possible to measure the amount of magic in a set of Qbits.  

The importance of a metric to magic cannot be overstated. The more magical an arrangement of Qbits is, the harder it is for a classical computer to simulate it. This second metric quantumness allows magic to be used as a quantum resource. But unlike entanglement, which was already a familiar physical phenomenon before it was applied to quantum computing, it wasn't certain whether the magic worked outside of computers. Recent results suggest so.

In 2021, Ellison et al. identified that some phases of quantum matter, as in the case of entanglement, have specific patterns of magic [11]. With a computational complexity metric based on the magic state, more precision is gained in identifying these phases. For example, Oliviero et al. A few days ago, a study was made available that shows that theoretically it would be possible, with the help of magic metrics, to reconstruct the pages of a diary swallowed by a black hole by observing only the radiation it emits [12]. In the case in question, the black hole would have to have a lower “dose” of magic.

The two metrics opened us up to manipulation quantumness. We already know that to create truly quantum systems, some combination of entanglement and magic is likely to be necessary. We are clear that none of them alone is enough. If a quantum state scores zero on any of the metrics, you can simulate it on your laptop. To do this, you need some Jozsa and Linden [6] (if the entanglement is zero) or Bravyi and Gosset [10] (if the magic is zero).

Still, the dive into this ocean continues. We know that entanglement and magic alone do not guarantee quantumness necessary to make leaps within quantum technology.

With you, Fermionic Magic

It’s time to talk about our third metric quantumness. It began to take shape almost a quarter of a century ago. Still, it is the least developed of the three. 

In 2001, Leslie Valiant discovered a way to simulate a third family of quantum tasks [13]. Just like Jozsa and Linden's technique [6], which focuses on circuits without entangled gates, and the Bravyi-Gosset algorithm [10], which can run on circuits without many T gates, Valiant's algorithm is restricted to circuits that do not have a Swap gate, an operation that takes two Qbits and swaps their positions. 

Valiant showed that as long as we don't swap Qbits, we can tangle them up and infuse them with as much magic as we want and we could still simulate them on a laptop. The point was that when exchanging Qbits with Swap gates, the circuit gained computational power that went far beyond the capacity of any classical computer [13]. Changing just two Qbits opened the door to unimaginable power. Knowing its origin was fundamental.

Alguns meses depois, em 2002, Barbara Terhal e David DiVincenzo [14] descobriram a fonte desse poder. O estudo mostrou que os circuitos livres de Swap gate de Valiant, conhecidos como circuitos “matchgate”, simulavam secretamente uma classe bem conhecida de problemas físicos. Semelhante à forma como os computadores simulavam galáxias em crescimento ou reações nucleares (sem realmente ser uma galáxia ou uma reação nuclear), os circuitos matchgate simulavam um grupo de fermions, a family of elementary particles that contain electrons.

When swap gates are not used, the simulated fermions do not interact. They are “free” and never run into each other. Problems involving free electrons are relatively easy to solve, sometimes even with pencil and paper. Swap gates encourage simulated fermions to interact and, once this happens, problems involving this type of particle become extremely difficult to solve, if not impossible. As matchgate circuits simulate the behavior of free, non-interacting fermions, they can easily be applied to classical computers to simulate this specific quantum situation without generating a runtime error (the famous memory overflow that slows down the computer).

But after the initial discovery, matchgate circuits remained largely unexplored. They were not as relevant to the main quantum computing efforts and were much more difficult to analyze.

In July 2023, the situation changed. Three teams of researchers [15] [16] [17], working on independent projects, coordinated the dissemination of their work on the same day.

All three groups essentially reformulated the mathematical tools that magic metric pioneers developed to explore Clifford circuits and applied them to the domain of matchgate circuits. Joshua Cudby and Sergii Strelchuk [15] focused on mathematically measuring the quantum feature that had delivery circuits. Conceptually, this feature corresponds to “interactivity” or how much simulated fermions can sense each other. No interactivity is classically easy to simulate, additions of interactivity make simulations even more difficult. But how much more difficult does a simulation become with an extra dose of interactivity? Is there any shortcut?

The group of Beatriz Dias and Robert Koenig [16] developed a way to divide a magical state that is more difficult to simulate into a huge sum of easier magical states, while at the same time keeping track of where these easier states cancel each other out and where they added up. The result was a kind of dictionary to “translate” algorithms that classically simulate Clifford circuits into matchgate circuits. With this, there is no longer a need to reinvent all the Clifford algorithms used in magic, just translate them. 

The study by Reardon-Smith et al. [17], in turn, offers an algorithm translated with the Dias-Koenig technique to simulate circuits with some Swap gates on classical computers. As with entanglement and magic, algorithms take exponentially longer to run with the addition of each forbidden gate. Although the inclusion of Swap gates increases the possibility of runtime errors, the effective translation of a Clifford algorithm into a matchgate represents a significant advance.

Reardon-Smith and his collaborators estimate that their algorithm [17] can simulate a circuit with 10 swap gates 3 million times faster than previous methods [13] [14]. This result allows classical computers to advance a little deeper into the quantum ocean, reinforcing our ability to confirm the performance of quantum computers and expanding the region where it is possible to create a quantum app.

There is still no official name for the “interactivity” generating resource produced by Swap gates. Some continue to call it simply magic, others use improvised terms like “non-fermionic stuff”. Strelchuk, one of the authors of the study [15], prefers “fermionic magic”. This is the name I adopted for this text.

And now, what do we have on the horizon?

It is increasingly comfortable to assess the degree of quantumness using the three metrics, each corresponding to one of the three simulation methods. If a collection of Qbits is largely disentangled, has little magic, or simulates nearly free groups of fermions, then it is possible to simulate your results on a laptop. Any quantum circuit with a low score on one of these three metrics can safely be disregarded as Shor's next algorithm.

The more familiar we become with these three ways of measuring how quantum a group of Qbits can be, the more misguided the initial dream of finding a single number that captures all possible quantum aspects seems to be. In a strictly computational sense, any circuit should have a single minimum time required to simulate it using the fastest of all possible algorithms. However, entanglement, magic and fermionic magic are so different from each other that the prospect of unifying them under one grand quantum metric to calculate the shortest running time seems remote. 

The three quantum resources shown in this text are artifacts that use mathematical languages to compress the complexity of the quantum world into simpler structures. Entanglement emerges as a feature when practicing quantum mechanics in the way described by Schrödinger, which uses his equation to predict how a particle's wave function will change in the future. This is the classic version of quantum mechanics, but it is not the only one.

When Gottesman developed his Clifford circuit simulation method [8], he based it on an older variety of quantum mechanics developed by Werner Heisenberg. In Heisenberg's mathematical language, the state of particles does not change. Instead, it is the “operators”, that is, the mathematical objects that we can use to predict the probabilities of some observation, that evolve. Restricting the view to free fermions involves seeing quantum mechanics through another mathematical lens.

Each mathematical language captures certain aspects of quantum states, although the price of this capture is distorting some other property. These awkwardly expressed quantum properties then become the quantum resource in this mathematical structure. That's what happened with entanglement, magic, and fermionic magic.

The search for the fourth metric is already in full swing. My bet is the phases of quantum matter that produce absurd negative probabilities when analyzed in a standard way, as indicated by Feynman [18]. Just like magic, it is possible that this negativity can define certain phases of matter. 

Overcoming the limitation imposed by the distortion generated by formalization and identifying a quantum characteristic to govern them all would require learning all possible mathematical languages to express quantum mechanics and looking for universal characteristics that they can all share. Would it be viable? We don't know, but it is in doubt that humanity walks.

References

[1] Feynman, Richard P. “Simulating Physics with Computers.” International Journal of Theoretical Physics, vol. 21, no 6, June 1982, p. 467–88. SpringerLink, https://doi.org/10.1007/BF02650179.

[2] Shor, Peter W. “Algorithms for quantum computation: discrete logarithms and factoring.” Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994.

[3] Bleicher, Ariel. “Quantum Computers Struggle Against Classical Algorithms”. Quanta Magazine, February 1st, 2018, https://www.quantamagazine.org/quantum-computers-struggle-against-classical-algorithms-20180201/.

[4] Brukner, Časlav; Żukowski, Marek; Zeilinger, Anton. “The essence of entanglement”. Quantum Arrangements: Contributions in Honor of Michael Horne (2021): 117-138.

[5] Stone, A. Douglas. “Einstein and the quantum: the quest of the valiant Swabian”. Princeton University Press, 2016.

[6] Jozsa, Richard; Linden, Noah. “On the role of entanglement in quantum computational speed-up”. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, vol. 459, no 2036, August 2003, p. 2011–32. arXiv.org, https://doi.org/10.1098/rspa.2002.1097.

[7] Ghosh, Soumik; Deshpande, Abhinav; Hangleiter, Dominik; Gorshkov, Alexey V.; Fefferman, Bill. “Sharp complexity phase transitions generated by entanglement”. Physical Review Letters, vol. 131, on July 3rd, 2023, p. 030601. arXiv.org, https://doi.org/10.1103/PhysRevLett.131.030601.

[8] Gottesman, Daniel. “The Heisenberg Representation of Quantum Computers”. Expanded version of a plenary speech at the 1998 International Conference on Group Theoretic Methods in Physics. arXiv, July 1st, 1998. arXiv.org, https://doi.org/10.48550/arXiv.quant-ph/9807006.

[9] Bravyi, Sergey; Kitaev, Alexei. “Universal Quantum Computation with ideal Clifford gates and noisy ancillas”. Physical Review A, vol. 71, on February 2nd, 2005, p. 022316. arXiv.org, https://doi.org/10.1103/PhysRevA.71.022316.

[10] Bravyi, Sergey; Gosset, David. “Improved classical simulation of quantum circuits dominated by Clifford Gates”. Physical Review Letters, vol. 116, no 25, June, 2016, p. 250501. arXiv.org, https://doi.org/10.1103/PhysRevLett.116.250501.

[11] Ellison, Tyler D; Kato, Kohtaro; Liu, Zi-Wen; Hsieh, Timothy H. “Symmetry-Protected Sign Problem and Magic in Quantum Phases of Matter.” Quantum, Vol. 5, December, 2021, p. 612. DOI.org (Crossref), https://doi.org/10.22331/q-2021-12-28-612.

[12] Oliviero, Salvatore F. E; Leone, Lorenzo; Lloyd, Seth; Hamma, Alioscia. “Unscrambling quantum information with Clifford decoders”. arXiv, October 14, 2023. arXiv.org, https://doi.org/10.48550/arXiv.2212.11337.

[13] Valiant, Leslie G. “Quantum computers that can be simulated classically in polynomial time.” Proceedings of the thirty-third annual ACM symposium on Theory of computing. 2001.

[14] Terhal, Barbara M; DiVincenzo, David P. “Classical simulation of noninteracting-fermion quantum circuits.” Physical Review A, vol. 65, no 3, March 2002, p. 032325. arXiv.org, https://doi.org/10.1103/PhysRevA.65.032325.

[15] Cudby, Joshua; Strelchuk, Sergii. “Gaussian decomposition of magic states for matchgate computations”. arXiv, July 25th, 2023. arXiv.org, https://doi.org/10.48550/arXiv.2307.12654.

[16] Dias, Beatriz; Koenig, Robert. “Classical simulation of non-Gaussian fermionic circuits”. arXiv, July 25th, 2023. arXiv.org, https://doi.org/10.48550/arXiv.2307.12912.

[17] Reardon-Smith, Oliver; Oszmaniec, Michał; Korzekwa, Kamil. “Improved simulation of quantum circuits dominated by free fermionic operations”. arXiv, July 25th, 2023. arXiv.org, https://doi.org/10.48550/arXiv.2307.12702.

[18] Feynman, Richard P. “Negative probability.” Quantum implications: essays in honor of David Bohm. P. 235-248. 1987.