Qubit

A classical computer works based on two distinct states, 0 and 1. Classical computers use transistors to create the absence or presence of an electric signal which represents 0 or 1, respectively. Fundamentally, it is all transistors, even in most modern supercomputers.

With qubits in quantum computers, this fundamental paradigm shifts, which leads to extraordinary speeds at which quantum computers can operate. A qubit is the state of physical atomic particles, for example, a spin on an electron. A qubit can be in a superposition of two states 0 and 1 simultaneously. The speedup rises exponentially as more qubits are added. Eight bits together in a classical computer are called a byte. In the quantum computing world, eight qubits together are called a qubyte.

Imagine 4 bits in a classical computer. These bits can have 16 possible states and can only be input sequentially. However, in a quantum computer, 4 qubits can be in a superposition of all 16 possible states and thus be input simultaneously Instead of the classical version, where 4 bits do have 16 possible states but can only be input sequentially. This phenomenon is called quantum parallelism and is the key to speeding up certain types of problems that are intractable on classical computers.

There are many ways to build a qubit physically. These techniques include trapped ions, photons, neutral atom, NMR, and several others.

Dirac notation is used to represent qubits. Qubits are represented as ∣0⟩ and ∣1⟩,as compared to classical 0 and 1. The difference is that a qubit can be in a linear combination of states called superpositions. A qubit can be a superposition of, for example, an electron with spin-up or spin-down or a photon with +45-degree polarization or –45-degree polarization and many other ways.

Dirac notation is used to represent quantum states and their superpositions. Dirac notation has the form ∣0⟩ +  ∣ 1⟩ where 0 and 1 are states.

A qubit can be in a quantum state ∣ψ⟩ = α ∣ 0⟩ + β ∣ 1⟩ where α, β ∈ C (complex amplitudes) and |α|² + |β|² = 1. This means that the state of a single qubit is represented by ∣ψ⟩ = α ∣ 0⟩ + β ∣ 1⟩, and the probability condition is |α|² + |β|² = 1. This probability condition means that the values that α, β can take are limited, and in any case, both must add to one. C represents complex numbers.

Other than Dirac notation, we can also use vector representations. A single vector can represent the state containing amplitudes α and β:

and

∣0⟩ = [1 0 ] and ∣1⟩ = [0 1 ]

A qubit can be visualized using a Bloch sphere, as shown in Figure 9-1.

A Bloch sphere has a 3-D plane with origin at the center of the sphere. A line from the origin extends to psi. The marked angles are theta and phi.

We can describe a single qubit as a point on the surface of the Bloch sphere. The North pole represents state ∣0⟩, and the South pole represents state ∣1⟩. Qubit angles are θ the latitude and ϕ the longitude. When a single gate operation is performed on the qubit, the state ψ (the qubit) rotates to another point on the Bloch sphere.

Superposition

Superposition is a fundamental principle of quantum mechanics. Superposition means that quantum states can be added together to get another valid quantum state. This is analogous to classical mechanics, where waves can be added together. Added quantum states are so-called “superposed.” Superposition is the key to extraordinary speedup as it allows many computation paths to be explored simultaneously.

Entanglement

Entanglement is an incredibly strong correlation that exists between particles, which allows two or more particles to inseparably link with each other. It allows any two quantum particles to exist in a shared state. Any action on one particle instantly affects the other particle even at massive distances. Entanglement is usually performed by bringing two qubits close together, performing an operation to entangle them, and, once entangled, moving them apart again. They will remain entangled even if one of them is on earth and the other is moved to outer space at a vast distance.

There are two features of entanglement which makes it particularly suitable for a large range of applications: maximal coordination and monogamy.

Hadamard

This gate transforms a basis state into an even superposition of the two basis states. Fundamentally, it allows us to create superpositions. It operates on one qubit and is denoted by the symbol shown in Figure 9-2.

An illustration of the quantum gates includes the Hadamard gate, Z gate, C NOT gate, C C NOT gate, T gate, NOT gate, and swap gate.

T

The T gate induces a pi/4 phase between contributing basis states. The symbol shown in Figure 9-2 represents the T gate. Relative phase rotation is by 45 degrees in T gate.

CNOT

This gate is called the controlled NOT. It is the same as the classical XOR gate, but with the property of reversibility. It works with two qubits. The first qubit serves as the control qubit, and the second qubit acts as the target qubit. It changes the state of the target qubit only if the first qubit is in a specific state. This gate can be used to create an entangled state in a two or more qubit system.

Toffoli (CCNOT)

This is the controlled-controlled NOT gate. It operates on three qubits. It switches the third bit of a three-bit state where the first two bits are 1, that is, it switches ∣110⟩ to ∣111⟩ and vice versa. It is represented by the symbol shown in Figure 9-2. In other words, if the first two bits are 1, the third bit inverts.

Z

It is a phase shift gate. It maps 1 to –1 and keeps 0 as 0. In other words, the amplitude of ∣1⟩ is negated. Fundamentally, it rotates the phase by 180 degrees. It is represented in the circuit with the symbol Z in a box, as shown in Figure 9-2.

NOT

This gate switches ∣1⟩ to ∣1⟩ and vice versa. It is an analogue of the classical NOT gate.

Swap Gate

The swap gate swaps two qubits. It can be visualized in Figure 9-2. Of course, there are many quantum gates, but we have introduced those which are commonly used and will help us to understand the algorithms later in this chapter.

All these gates can be visualized in Figure 9-2.

Measurement

In addition to gates, another important element is measurements. A measurement takes a quantum state and collapses it into one of the basis states. We can visualize this in Figure 9-3.

An illustration of the measurement. A quantum state enters measurement and a classical state is produced.

Teleportation Circuit

Can we transfer a quantum state from one quantum device to another? Yes, we can; for this purpose, teleportation is used, which uses entanglement to move a quantum state from one quantum device to another.

In Figure 9-5, a teleportation circuit is shown, which can transport a quantum state from one party to another.

A teleportation circuit includes 3 qubits, 2 Hadamard gates, 3 C NOT gates, two measurements, and a controlled Z gate.

Some applications of teleportation are state transportation between quantum systems. This can be valuable in quantum distributed systems where state transfer between nodes can enable applications like quantum state machine replication.

GHZ Circuit

The Greenberger-Horne-Zeilinger (GHZ) state is an entangled state of three or more qubits. If three or more particles get into an entangled state, it’s called a multipartite entanglement.

Figure 9-6 visualizes this circuit.

A G H Z circuit includes 3 qubits, a Hadamard gate, and 2 C NOT gates.

GHZ states have been shown to be useful in quantum cryptography and quantum Byzantine agreement (consensus) algorithms, as we’ll explore later in this chapter.

W State Circuit

The W state circuit is another way to achieve entanglement of three particles. The difference with GHZ is that in the W state if one qubit is lost out of three, then the remaining two will remain entangled. GHZ however does not have this property. The circuit is shown in Figure 9-7.

A W state circuit includes 3 qubits, an R y gate, a controlled Hadamard gate, two C NOT gates, and an x gate.

The W state circuit has application in leader election algorithms, as we’ll see later in this chapter.

P – Polynomial

A polynomial time class categorizes problems which are solvable in polynomial time, that is, a reasonable amount of time.

NP – Nondeterministic Polynomial

An NP class means that the solution to the problem can be checked quicker, that is, in polynomial time. One example of P is multiplication, whereas factorization is NP. For example, the multiplication of two numbers is in class P, whereas factoring (finding which two numbers were multiplied) is in class NP. However, if the solution is there, then it’s quick to verify the solution; hence, it is in the NP class.

NP-complete problems are those if they are in NP and all NP problems are “polynomial time” reducible to the NP problem under consideration. NP hard problems are those if we know that any NP problems are reducible to the possibly NP problem under consideration, but we do not know if the problem is in NP. In other words, NP-complete are those if any NP problem can be reduced to these problems, and NP hard means they’re reducible to NP but don’t know if they are in NP. One famous example of an NP-complete problem is the travelling salesman problem.

BPP – Bounded Error Probabilistic Polynomial Time

This class contains P. These problems are solvable in polynomial time with probability > ½. Problems in BPP are either solvable deterministically in polynomial time or probabilistically correctly more than one-thirds of the time.

BQP – Bounded Error Quantum Polynomial Time

This new class emerged with quantum computing. A problem is in BQP if it is solvable correctly on a quantum computer in polynomial time with probability > ½, that is, high probability. In other words, this class includes problems that are thought to be hard for classical computers, but easy for quantum computers.

Figure 9-9 shows complexity classes.

An illustration of complexity classes. From the innermost, the layers are N P complete, N P, P, B P P, B O P, and P space.

PSPACE – Polynomial Space

This class is concerned with memory utilization, instead of time. Problems in PSPACE require a polynomial size of memory.

There is also a concept of hypercomputation that has come to limelight with quantum computing. The idea of hypercomputation is that it can even solve problems which are Turing incomplete, for example, the halting problem. It has, however, been shown that a quantum computer could be much faster than a classical one, but it cannot solve every problem that a classical computer cannot. The idea is that even on quantum computers, Turing-incomplete problems cannot be solved. However, research continues in this regard to study infinite state superposition and infinite state Turing machines which can lead to building hypercomputers.

With this we complete our discussion on complexity.

Quantum Networks

Quantum networks are like classical networks with the same routing strategies and topologies. The key difference is that nodes can implement quantum computations and relevant quantum processes. Channels between quantum devices in a quantum network can be quantum or classical.

Quantum Internet

Just as the ARPANET from 1969 with just four nodes became the Internet of today with billions of entities² on it, it is expected that small experimental scale quantum networks will become a quantum Internet of tomorrow.

It is envisioned that a quantum network infrastructure will be developed to interconnect remote quantum devices and enable quantum communication between them. The quantum Internet is governed by laws of quantum mechanics. It transfers qubits and distributes entangled quantum states. As the number of nodes grows in the quantum Internet, so does the quantum power. This is so because, as the number of qubits scales linearly with the number of quantum devices on the network, the quantum Internet could enable an exponential quantum speedup, resulting in a “virtual quantum computer” capable of solving previously impossible problems.

However, quantum teleportation can be used to transmit qubits. Quantum teleportation is realized using a quantum feature called entanglement, which we discussed earlier. Using entanglement, instantaneous transfer of the quantum state encoded in a qubit at a sender to a qubit stored at a receiver is possible. The surprising thing is that this transfer occurs without physical transfer of the qubit at the sender. Entanglement is the core enabler of the quantum Internet.

A quantum Internet enables several exotic applications such as blind computing, secure communications, and noiseless communications.

Quantum Distributed Systems – Distributed Quantum Computing

With the availability of the quantum Internet, it is not difficult to envisage that quantum nodes will also engage in communication with each other to cooperate and collectively solve some problem using the distributed computing approach. This development will inevitably lead to the emergence of distributed quantum systems or distributed quantum computing.

We can think of a layered approach where at the lowest layer we have a network layer composed of classical and quantum links. Then we have a layer of quantum computers running on the next layer. Next up are local and remote operations, which include local quantum operations and remote operations on qubits. By combining all operations and computing layers underneath, a virtual quantum computer can be imagined, which combines all the qubits and results in a scalable virtual quantum computer. A controller or distributed quantum compiler is then required to translate quantum algorithms into a sequence of local and remote operations. Finally, we have a layer on top which runs quantum algorithms. This layered approach can be visualized in Figure 9-10.

A blockchain ecosystem has 6 layers. Quantum algorithms, distributed compiler, virtual processors, operations, quantum computers, and networks.

Quantum Blockchain

Inevitably with the quantum Internet and quantum distributed systems, we can envisage a quantum blockchain that utilizes quantum computers as nodes and the underlying quantum Internet as the communication layer.

There are two facets of blockchains in the quantum world. The first one is the pure quantum blockchains running on top of the quantum Internet. Some work has been done in this regard, and an innovative proposal by Rajan and Visser is to encode blockchains into a temporal GHZ state.

The other aspect is the existence of classical blockchains in the post-quantum world. Quantum computers can impact the security of blockchains and consensus adversely due to the ability to break classical cryptography. More on this later in this chapter in the last section.

A quantum blockchain can comprise several elements. The quantum blockchain can have both classical and quantum channels and devices. It can exist as a quantum algorithm, among others, in the “distributed quantum algorithm” layer in the distributed quantum computing ecosystem discussed in the previous section.

We elaborated a layered approach in the previous section. We can envisage blockchains and other algorithms running on the top layer. This whole layer approach represents quantum Internet–based distributed quantum computing ecosystem.

Another element could be a quantum transaction coordinator responsible for transaction ordering and dissemination. On the other hand, by using blind computing, quantum blockchains can immediately realize the unparalleled privacy which will enable quantum scale blockchain applications that require privacy, for example, finance, health, and government-related applications.

Quantum Cryptography

Quantum cryptography is indeed the most talked-about aspect of quantum computing, especially from the point of view of the impact that it can have on existing cryptography.

There are two dimensions here; one is quantum cryptography, and the other is post-quantum cryptography. Quantum cryptography refers to cryptography primitives or techniques that are based on properties of quantum mechanics. For example, quantum key distribution, quantum coin flipping, and quantum commitment. Using quantum properties, a new type of unconditionally secure mechanisms can be developed, which have no counterpart in the classical world. Quantum key distribution (QKD) protocols, such as BB84, were proposed by Bennett and Brassard in 1984, which allow two parties to construct private keys securely using qubits. The benefit of this quantum scheme is that due to superposition any adversary trying to eavesdrop will inevitably be detected.

The other dimension of the study of quantum cryptography is the impact of quantum computers on classical cryptography. We know that using Shor’s algorithm, the discrete log problem can be solved, and integer factorization can be sped up, which can result in breaking commonly used public key cryptography schemes, such as RSA and elliptic curve cryptography. Not so much impact is expected on symmetric cryptography because simply key lengths can be increased to ensure that exhaustive searches O(n) in the classic world and using quantum techniques made possible by Grover’s algorithm or similar no longer are effective.

Several approaches have been studied for post-quantum cryptography, including lattice-based cryptography, code-based cryptography, multivariate cryptography, hash-based cryptography, and isogeny-based cryptography.

As blockchain consensus mechanisms use cryptography, which is known to be impacted by quantum computing, it is essential that the blocks produced today are quantum resistant so that when quantum computers can do so, they cannot rewrite the entire history of a blockchain. For example, Bitcoin uses the digital signature scheme ECDSA, which quantum computers can break. If quantum technology becomes capable of breaking ECDSA even in ten years, they can still move funds around due to broken ECDSA. Therefore, there is a need to address this issue and apply some quantum resistance to already produced and future blocks. If quantum technology becomes capable of breaking ECDSA in future, an adversary cannot rewrite the block history. Bitcoin generally is not quantum safe, and Lamport signatures have been proposed to alleviate this issue. Note that Bitcoin is secure for the foreseeable future, and the quantum computer required to break ECC is still decades away. To break the 256-bit ECC encryption within one hour, 317 × 10⁶ physical qubits³ are required. However, currently the most qubits we have today are only 127 on IBM’s 127-qubit Eagle processor. So breaking elliptic curve cryptography is not going to be a reality any time soon.

So far, we have discussed what quantum computing is and what effect it can have on classical computing. We also covered some applications of quantum computing and relevant technical details such as gates and circuits. One thing is clear: quantum computing is going to revolutionize the world soon, and a tremendous effort is already being put into making the technology grow and become mainstream.

With all this revolutionary advancement in quantum computing, a natural question arises whether it is possible to harness this power and apply it to solve distributed computing problems, especially the consensus problem. Can we make consensus faster, can we circumvent FLP in some novel way, or does FLP even apply in the quantum world? Is there a quantum solution for the Byzantine generals problem? How can quantum computing help in distributed systems? Can it increase its efficiency? Can quantum consensus tolerate any number of dishonest parties, and no usual lower bounds apply? Can blockchains benefit from this advancement and improve blockchain consensus and other aspects of blockchains, such as cryptography, security, efficiency, and scalability? We answer these questions in the next section.

Fast Quantum Byzantine Agreement

The system model comprises of n nodes, and each pair of nodes is connected through a separate two-way quantum channel. The protocol works in rounds, and each round has two phases. In the first phase, all processors send and receive messages, and the second phase is the computation phase where nodes do local computation to process received messages and decide what messages to send.

Remember we discussed coin flip randomized protocols earlier in Chapter 6. Especially, we discussed Ben-Or’s algorithm where coin flipping was used to achieve an agreement. Fundamentally, the agreement problem is reduced to weak global coin flipping.

The idea in the quantum world is that instead of obtaining a weak global coin by classical means, we use quantum techniques to obtain a weak global coin. With this quantum technique, it is possible to tolerate Byzantine failures under synchrony if n > 3t in O(1) expected rounds. Consensus however is still impossible if n < 3t, but there’s an improvement of achieving O(1) rounds.

In an asynchronous model, a quantum algorithm exists if >3t; however, it is impossible if n < 3t.

The protocol for fail-stop faults works as described in the following:

(C represents a coin, L represents a leader, and the state is GHZ.)

GHZ state is

Each process P_i runs:

Using this algorithm, a weak global coin is obtained. The probability for either common outcome is at least if 3t < n. The protocol works for crash faults.

Another protocol for Byzantine faults is presented in the paper, which can tolerate up to faulty nodes under an asynchronous environment.

How to Refute FLP Impossibility

An interesting claim is made in [by Louie Helm] that distributed consensus can be achieved under asynchrony even in the presence of faults, which appears to contradict FLP impossibility.

This is so because the quantum entanglement here guarantees that entangled qubits collapse to the same state. This means that all nodes will end up with the same state, which means an agreement.

The GHZ state is used to realize this scheme. The key assumption made here is that each node receives a qubit during the setup phase and then later measures it, which results in the same collapsed state at all nodes.

An agreement is provided simply because measuring any single full entangled qubit in the GHZ state causes all other qubits in the same GHZ state to collapse to the same basis state. Validity is achieved because when the measurement is made on the first node, it’s effectively proposing either a ∣0⟩ or ∣1⟩.

This protocol can tolerate network delays because even if a qubit arrives late on a quantum node, the other nodes will keep working without any impact. When the late qubit arrives at any time, it will already contain the agreed-upon value, again due to entanglement. The fundamental reason why FLP can be refuted using this algorithm is because it requires one-way broadcast, and no classical response is required. Even if a single process does not measure its qubit, it will not impact the overall outcome of the computation, that is, even if that single measurement is not available, the other correct nodes will continue to operate even if one qubit is missing. This algorithm will work if the distribution of the original GHZ state completes successfully. Once that’s complete, missing measurements won’t impact the protocol from there onward. In case of Byzantine faults, the algorithm is also resilient. Any malicious party cannot tamper with the value the algorithm will eventually choose. This is so because any measurement does not impact the correlation of other qubits in the system. This means that any adversary measuring the qubits cannot impact the final chosen value. Due to the quantum nature, the qubit will always end up as 0 or 1. This always means that the decision will eventually be made regardless of Byzantine faults. This achieves termination.

Enhanced Distributed Consensus

Seet and Griffin proposed how quantum computing can speed up an agreement on a distributed network. They proposed a novel quantum consensus mechanism. The work presented in the paper focuses on the scalability and speed of distributed consensus.

By removing the need for multicast replies, the consensus speed and scalability is accomplished. Moreover, using quantum properties, it is ensured that only a single multicast is required. The key idea for achieving consensus is to aggregate the wave function of the received qubits (from other nodes) and local qubits of a quantum node.

In the paper, this algorithm is expanded to a multiqubit system. Also, several improvements over the classical model are achieved such as reducing the time complexity of state verification by half. This is achieved by utilizing entanglement where the verifier only needs to receive the entangled qubit, after which verification can be done locally, by comparing the state of all qubits. This contrasts with a classical high complexity request-response style of message passing, which increases time and communication complexity. With quantum properties, this complexity is reduced, and consensus can be reached in half the time as compared to the classical consensus. Such efficiency gains can be utilized in blockchains to increase scalability. Moreover, any attempt of manipulation of the original and the sent state in isolation is immediately detectable due to entanglement, thus resulting in increased security of the system. The paper also proposes several scalability, privacy, and performance enhancements addressing the blockchain trilemma.

Quantum Leader Election and Consensus

Ellie D’Hondt and Prakash Panangaden presented a quantum solution for a totally correct leader election in quantum networks, which is considered difficult in the classical world.

For electing a leader using quantum properties, the use of the W state is proposed. In an anonymous network, if quantum nodes share the W state the leader election problem can be solved trivially.

Remember we discussed the W state earlier. For example, the entangled W state of three qubits is

This protocol has time complexity of O(1), that is, constant, and there is no message passing required. This is in complete contrast with the classical world where multiround protocols with higher complexity are usually common. This quantum protocol works in asynchronous networks too.

Also, a simple algorithm for consensus is presented. Leader election was based on symmetry breaking; however, this algorithm is dependent on symmetry preservation.

The idea is that to achieve totally correct anonymous quantum distributed consensus where each process has one qubit initially, the processors are required to be entangled in a GHZ state. It is shown that not only is it necessary but also a sufficient condition.

The core idea of the protocol is to share the GHZ entangled state between all nodes participating in the consensus. This allows to create symmetry in one step.

The GHZ state for three qubits is given as

Again, this protocol has time complexity of O(1), and no message passing is needed. This protocol works under different communication topologies and under asynchrony.

The result in the paper shows that GHZ for consensus is necessary and sufficient. Moreover, W is necessary and sufficient for leader election.

Other Algorithms

There is a wide range of quantum consensus algorithms and relevant proposals. It’s not possible to cover them all here in detail; however, this section summarizes some of the prominent results.

Luca Mazzarella, Alain Sarlette, and Francesco Ticozzi in “Consensus for Quantum Networks: From Symmetry to Gossip Iterations” extend the classical distributed computing problem to networks of quantum systems. They proposed a general framework to study the consensus problem in the quantum world. Also, a quantum gossip–style algorithm is presented in the paper.

“Reaching Agreement in Quantum Hybrid Networks” is proposed by Guodong Shi, Bo Li, Zibo Miao, Peter M. Dower, and Matthew R. James. The problem considered in the paper is to drive a quantum hybrid network composed of quantum nodes holding qubits to a common state, thus achieving consensus. The key idea is that quantum nodes measure the qubits, and the results of the measurement are exchanged through classical communication links.

It has been shown that the classical Byzantine generals problem is unsolvable even if pairwise quantum channels are used. However, a variation of the Byzantine agreement problem called the detectable Byzantine agreement (DBA) can be solved by using quantum properties. The DBA protocol ensures that either all generals agree on an order or all abort, that is, the agreement property, and if all generals are loyal, they agree on an order, that is, validity.

“Multi-party Quantum Byzantine Agreement Without Entanglement” is proposed by Xin Sun, Piotr Kulicki, and Mirek Sopek. Usually, an entanglement property is used in the quantum consensus algorithm. But this algorithm is different where entanglement is not used. Instead, the protocol relies on quantum key distribution and its unconditional security. The protocol relies on sequences of correlated numbers shared between semihonest quantum key distributors.

There are other proposals where a concept of the quantum blockchain using temporal GHZ is introduced.

There are quite a few innovative results regarding quantum consensus, and researchers are presenting more and more developments. We introduced some of these results earlier. The quantum algorithms that can enhance classical distributed consensus results are of particular importance as they can impact classical distributed systems in the near future. Other pure quantum results are also fascinating but will be fully useful only in the future when quantum Internet and relevant quantum ecosystems become a reality.