At what cost can we simulate large quantum circuits on small quantum computers?

One major challenge of near-term quantum computation is the limited number of available qubits. Suppose we want to run a circuit consisting of 400 qubits, but we only have 100-qubit devices available. What do we do?

Over the course of the past year, the IBM Quantum team has begun researching a host of computational methods called circuit knitting. Circuit knitting techniques allow us to partition large quantum circuits into subcircuits that fit on smaller devices, incorporating classical simulation to “knit” together the results to achieve the target answer. The cost is a simulation overhead that scales exponentially in the number of knitted gates.

Circuit knitting will be important well into the future. Our quantum hardware development team is focused on scaling by connecting smaller processors via classical, and then via quantum links. Due to this planned hardware architecture, circuit knitting will be useful in the near future as we run problems on classically parallelized quantum processors. Techniques that boost the number of available qubits will also be relevant far into the future.

Figure 1: Circuit knitting example: The nonlocal circuit on the left acting on A⊗B can be simulated with local circuits acting only on A or B on the right followed by classical postprocessing.

But first, our team needed to understand how much of a benefit these methods can offer, especially when we knew that the simulation overhead scales exponentially with the number of gates acting between these subcircuits.

We are currently investigating whether classical communication between local quantum computers can help to lower the simulation overhead — as you might see on a pair of classically parallelized IBM Quantum “Heron” processors. Specifically, we realized circuit knitting via a method that has previously gained interest in the fields of error mitigation and classical simulation algorithms, called the quasiprobability simulation technique.

The 133-qubit “Heron” processor, slated for 2023.

We consider three settings to simulate a non-local circuit with local operations. In the first, the two quantum computers can only run their own local operations on their subcircuits without communication between them. In the second the two computers can realize those local operations, with the added ability to send classical information in one direction — from \AlphaA to \BetaB, but not from \BetaB to \AlphaA. In the third, the two quantum computers can run their own local quantum operations and send classical information in either direction between them.

In the local and one-way classical communication settings, one does not necessarily require two separate quantum computers. Instead, one can run the two subcircuits in sequence on the same device. The classical communication in the one-way setting can then be simulated by classically storing the bits sent from \AlphaA and \BetaB. 

Figure 2: Graphical overview of the three scenarios considered to run a nonlocal operation. LO refers to local operations; LO & one way CC refers to local operations and one way classical communication; LOCC refers local operations and classical communication.

In contrast, the two-way communication setting requires two quantum computers that exchange classical information in both directions. We show that for circuit knitting based on quasiprobability simulation, the three settings mentioned above all have a different sampling overhead when applied to circuits with multiple instances of the same non-local gate. 

Our results, available on arXiv, demonstrate that two-way communication can considerably reduce the simulation overhead. For circuits containing n CNOT gates connecting each subcircuit, the incorporation of classical information exchange between the subcircuits reduces the simulation overhead from O(9n) to O(4n) — a reduction that is substantial in practice. It allows us to cut considerably more CNOT gates — that is, the gates that entangle the qubits — for a given fixed simulation overhead.

On a technical level, our results are based on the insight that a simultaneous local preparation of two maximally entangled states, called Bell pairs, is more efficient than locally preparing a single Bell pair twice. The reason is that for a joint preparation we can make use of entanglement between the local subsystems, which is not possible if we prepare the two Bell pairs separately. Using the idea of gate teleportation we can then convert Bell pairs into CNOT gates under local operations and classical communication.

Figure 3: Graphical explanation of how to realize two CNOT gates in a LOCC setting via gate teleportation. By generating the two Bell pairs simultaneously (instead generating twice a single Bell pair), we can reduce the total simulation overhead.

Our results show that classical communication between locally separated quantum computers is beneficial when performing large computations that exceed the number of qubits each quantum device individually has.

Source: ibm.com

Continue reading

What Is Quantum-Safe Cryptography, and Why Do We Need It?

How to prepare for the next era of computing with quantum-safe cryptography.

Cryptography helps to provide security for many everyday tasks. When you send an email, make an online purchase or make a withdrawal from an ATM, cryptography helps keep your data private and authenticate your identity.

Today’s modern cryptographic algorithms derive their strength from the difficulty of solving certain math problems using classical computers or the difficulty of searching for the right secret key or message. Quantum computers, however, work in a fundamentally different way. Solving a problem that might take millions of years on a classical computer could take hours or minutes on a sufficiently large quantum computer, which will have a significant impact on the encryption, hashing and public key algorithms we use today. This is where quantum-safe cryptography comes in.

According to ETSI, “Quantum-safe cryptography refers to efforts to identify algorithms that are resistant to attacks by both classical and quantum computers, to keep information assets secure even after a large-scale quantum computer has been built.”

What is quantum computing?

Quantum computers are not just more powerful supercomputers. Instead of computing with the traditional bit of a 1 or 0, quantum computers use quantum bits, or qubits (CUE-bits). A classical processor uses bits to perform its operations. A quantum computer uses qubits to run multidimensional quantum algorithms. Groups of qubits in superposition can create complex, multidimensional computational spaces. Complex problems can be represented in new ways in these spaces. This increases the number of computations performed and opens up new possibilities to solve challenging problems that classical computers can’t tackle.

There are many exciting applications in the fields of health and science, like molecular simulation that has the potential to speed up the discovery of new life-saving drugs. The problem is, however, quantum computers will also be able to solve the math problems that give many cryptographic algorithms their strength.

How will quantum computing impact cryptography?

Two of the main types of cryptographic algorithms in use today for the protection of data work in different ways:

◉ Symmetric algorithms use the same secret key to encrypt and decrypt data.

◉ Asymmetric algorithms, also known as public key algorithms, use two keys that are mathematically related: a public key and a private key.

The development of public key cryptography in the 1970s was revolutionary, enabling new ways of communicating securely. However, public key algorithms are vulnerable to quantum attacks because they derive their strength from the difficulty of solving the discrete log problem or factoring large integers. As discovered by mathematician Peter Shor, these types of problems can be solved very quickly using a sufficiently strong quantum computer, so in the case of asymmetric or public key cryptography, we need new math that will stand up to quantum attacks because today’s public key algorithms will be completely broken.

Grover’s Algorithm, devised by computer scientist Lov Grover, is a quantum search algorithm. Using Grover’s algorithm, some symmetric algorithms are impacted and some are broken. Key size and message digest size are important considerations that will factor into whether an algorithm is quantum-safe or not. For example, use of Advanced Encryption Standard (AES) with 256-bit keys is considered quantum-safe but Triple DES (TDES) can be broken no matter the key size.

What is being done to address future quantum threats?

The good news is that researchers and standards bodies are moving to address the threat. The National Institute of Standards and Technology (NIST) initiated a Post-Quantum Cryptography Standardization Program to identify new algorithms that can resist threats posed by quantum computers.

After three rounds of evaluation, NIST has identified seven finalists. They plan to select a small number of new quantum-safe algorithms early this year and have new quantum-safe standards in place by 2024. As part of this program, IBM researchers have been involved in the development of three quantum-safe cryptographic algorithms based on lattice cryptography that are in the final round of consideration: CRYSTALS-Kyber, CRYSTALS-Dilithium and Falcon.

How should enterprises be preparing to adopt quantum-safe cryptography?

Fortunately, we have time to implement quantum-safe solutions before the advent of large-scale quantum computers — but not much time. Moving to new cryptography is complex and will require significant time and investment. We don’t know when a large-scale quantum computer capable of breaking public key cryptographic algorithms will be available, but experts predict that this could be possible by the end of the decade.

Also, hackers can harvest encrypted data today and hold it for later when they can decrypt it using a quantum computer, so sensitive data with a long lifespan is already vulnerable. Organizations in the United States and Germany have already issued requirements for government agencies to follow regarding quantum-safe cryptography. BSI, a German federal agency, requires the use of hybrid schemes — where both classical and quantum-safe algorithms are used — for protection in high-security applications. The White House issued a memo requiring federal agencies to begin quantum-safe modernization planning.

How can IBM help?

As we prepare for a quantum world, IBM is committed to developing and deploying new quantum-safe cryptographic technology. Trusted hardware platforms will play a critical role in the adoption of quantum-safe cryptography. And IBM Z has already begun the modernization process. IBM z15 introduced lattice-based digital signatures within the system for digital signing of audit records within z/OS. IBM z15 also provided the ability for application developers to begin experimenting with quantum-safe lattice-based digital signatures. Because we’ve already begun the process, this helps us understand the implications of moving to new algorithms so we can pass on insights about the topic to our clients.

Preparing to adopt quantum-safe standards

When meeting with clients getting started on their journey to quantum safety, we share a few of the key milestones to help them get ready to adopt new quantum-safe standards:

◉ Discover and classify data: The first step involves classifying the value of your data and understanding compliance requirements. This helps you create a data inventory.

◉ Create a crypto inventory: Once you have classified your data, you will need to identify how your data is encrypted, as well as other uses of cryptography to create a crypto inventory that will help you during your migration planning. Your crypto inventory will include information like encryption protocols, symmetric and asymmetric algorithms, key lengths, crypto providers, etc. 

◉ Embrace crypto agility: The transition to quantum-safe standards will be a multi-year journey as standards evolve and vendors move to adopt quantum-safe technology. Use a flexible approach and be prepared to make replacements. Implement a hybrid approach as recommended by industry experts by using both classical and quantum-safe cryptographic algorithms. This maintains compliance with current standards while adding quantum-safe protection.

Many clients across industries have already started experimenting with new quantum-safe algorithms in order to assess the impact of new quantum-safe standards on their businesses:  

◉ Automotive: Clients in the automotive industry use public key technology in connected cars for vehicle-to-everything (V2X) communications and to verify the integrity of the firmware loaded into vehicles. The cars they are designing today will be on the road well into the future, so they are on a tight timeline to adopt quantum-safe technology. Because vehicles have hardware resource constraints, it is critical that automotive clients model and test new quantum-safe algorithms now to make sure they can accommodate the larger key sizes in their use cases.   

◉ Banking: Clients in the banking industry rely heavily on symmetric cryptography to ensure the confidentiality of data in core banking applications. There are many data retention and data confidentiality regulations and agreements that these clients must adhere to, such as retaining tax records for 7–10 years and keeping trade secrets confidential for up to 50 years. Adversaries are starting their attacks today with the intent of disclosing this type of confidential data in the future, so many banking clients have started creating data and crypto inventories to adopt quantum-safe protection for highly sensitive data. Banks also rely on public key cryptography, for example, in digital signatures used for authentication and software verification. It’s important for banking clients to begin modeling new quantum-safe algorithms to understand performance implications and prepare to adopt new standards as they evolve.

Source: ibm.com

Continue reading

The IBM Quantum heavy hex lattice

Overview

As of Aug 8, 2021, the topology of all active IBM Quantum devices will be based around the heavy-hex lattice. The heavy-hex lattice represents the fourth iteration of the topology for IBM Quantum systems and is the basis for the Falcon and Hummingbird quantum processor architectures. Each unit cell of the lattice consists of a hexagonal arrangement of qubits, with an additional qubit on each edge.

Read More: C9560-507: IBM Tivoli Monitoring V6.3 Implementation

The heavy-hex topology is a product of co-design between experiment, theory, and applications, that is scalable and offers reduced error-rates while affording the opportunity to explore error correcting codes. Based on lessons learned from earlier systems, the heavy-hex topology represents a slight reduction in qubit connectivity from previous generation systems, but, crucially, minimizes both qubit frequency collisions and spectator qubit errors that are detrimental to real-world quantum application performance.

In this tech report, we discuss the considerations needed when choosing the architecture for a quantum computer. Based on proven fidelity improvements and manufacturing scalability, we believe that the heavy hex lattice is superior to a square lattice in offering a clear path to quantum advantage, from enabling more accurate near-term experimentation to reaching the critical goal of demonstrating fault tolerant error correction. We demonstrate that the heavy-hex lattice is equivalent to the square lattice up to a constant overhead, and like other constant overheads such as choice of gate set, this cost is insignificant compared to the cost of mapping the problem itself.

Figure 1:

Three unit cells of the heavy-hex lattice. Colors indicate the pattern of three distinct frequencies for control (dark blue) and two sets of target qubits (green and purple).

Physical motivations

IBM Quantum systems make use of fixed-frequency qubits, where the characteristic properties of the qubits are set at the time of fabrication. The two-qubit entangling gate in such systems is the cross-resonance (CR) gate, where the control qubit is driven at the target qubit’s resonance frequency. See Fig. 1 for the layout of control and target qubits in the heavy-hex lattice. These frequencies must be off-resonant with neighboring qubit transition frequencies to prevent undesired interactions call “frequency collisions.”

The larger the qubit connectivity, the more frequency conditions must be satisfied, and degeneracies amongst transition frequencies become more likely. In addition, due to fabrication imperfections, require disabling an edge in the system connectivity (e.g. see Penguin v1 and v2 in Fig. 2)—all of which can effect device performance and add hardware overhead.

Figure 2:

Left to right, evolution of the topologies for IBM Quantum systems, including the average qubit connectivity.

A similar set of frequency collisions appears in flux-tunable qubits as avoided-crossings in implementing flux control. Moreover, tunable qubits come at the cost of introducing flux noise which will reduce coherence, and the flux control adds scaling challenges to larger architectures with increased operational complexity in qubit tune-up and decreased gate fidelity caused by pulse distortions along the flux line.

As shown in Fig. 3, the decrease in qubit connectivity offered by the heavy-hex lattice, as well as the selected pattern of control and target qubit frequencies, gives an order of magnitude increase in zero-frequency collision yield as compared to other choices for system topology.

Figure 3:

Simulations of system yields for collision free devices for heavy-hex and square topologies as a function of qubit frequency variability.

The sparsity of the heavy hex topology with fixed frequency qubits also improves overall gate fidelity by limiting spectator qubit errors: errors generated by qubits that are not directly participating in a given two-qubit gate operation. These errors can degrade system performance and do not present themselves when the gate is performed in isolation; one- and two-qubit benchmarking techniques are not sensitive to these errors.

However, the spectator errors matter severely when we run circuits. The rate of spectator errors is directly related to the system connectivity. The heavy-hex connectivity reduces the occurrence of these spectator errors by placing the control qubit on only those edges connected to the target qubits (Figure 1).

Figure 4 shows the average CNOT error rates for four generations of Penguin quantum processor along with those of the Falcon and Hummingbird families that utilize the heavy-hex topology. The reduction in frequency collisions and spectator errors allow for devices to have better than 1 percent average CNOT error rate across the device, and isolated two-qubit gates approaching 0.5 percent. Additional techniques for improving spectator errors are given in Ref. This represents a factor-of-three decrease compared to the error rates on the best Penguin device with a square layout.

Higher Quantum Volume, higher computing performance

Quantum Volume (QV) is a holistic, hardware-agnostic quantum system benchmark that encapsulates system properties such as the number of qubits, connectivity, as well as gate, spectator errors, and measurement errors into a single numerical value by finding the largest square circuit that a quantum device can reliably calculate.

Figure 4:

Average CNOT gate error rates for Penguin-, Falcon-, and Hummingbird-based IBM Quantum systems.

Higher quantum volumes directly equate to higher processor performance. Gate errors measured by single- or two-qubit benchmarking do not reveal all errors in a circuit, for example crosstalk and spectator errors, and estimating circuit errors from the gate errors is non-trivial. In contrast, QV readily incorporates all possible sources of noise in a system, and measures how good the system is at implementing average quantum circuits. This allows one to find the best system to run their application.

Figure 5 shows the evolution of Quantum Volume over IBM Quantum systems, demonstrating that only heavy-hex based Falcon and Hummingbird systems can achieve QV32 or higher. Parallel improvements in gate design, qubit readout, and control software, such as those in Ref., also play an important role in increasing QV values faster than the anticipated yearly doubling.

Figure 5:

Quantum Volume as a function of system release date for IBM Quantum Penguin (20 qubits), Falcon (27 qubits), and Hummingbird (65 qubits) systems. The Falcon and Hummingbird are based on the heavy-hex topology.

Development of quantum error correcting codes is one of the primary areas of research as gate errors begin to approach fault-tolerant thresholds. The surface code, implemented on a square grid topology, is one such example of this. However as already discussed, and experimentally verified, frequency collisions are common in fixed-frequency qubit systems with square planar layouts. As such, researchers at IBM Quantum developed a new family of hybrid surface and Bacon-Shor subsystem codes that are naturally implemented on the heavy-hex lattice.

Similar to the surface code, the heavy-hex code also requires a four-body syndrome measurement. However, the heavy-hex code reduces the connectivity by implementing a degree four node with two degree three nodes as presented in Fig. 6.

Figure 6:

Reduction of a degree four node into two degree three nodes compatible with the heavy-hex lattice.

Mapping heavy-hex to square lattices

The connectivity of other lattices, such as the square lattice, can be simulated on the heavy-hex lattice with constant overhead by introducing swap operations within a suitably chosen unit cell. The vertices of the desired virtual lattice can be associated to subsets of vertices in the heavy-hex lattice such that nearest-neighbor gates in the virtual lattice can be simulated with additional two-qubit gates.

Taking the square lattice as an example, there are a variety of ways to associate a unit cell of the heavy-hex lattice to the square lattice. If we draw the hexagons as 3x5 rectangles, one natural choice places the qubits of the square lattice on the horizontal edges of the heavy-hex lattice, see Figure 7.

Figure 7:

Direct mapping between heavy-hex and square lattices.

Let's choose the goal of applying an arbitrary two-qubit gate, U(4), between each neighboring qubit in the virtual lattice. This can be accomplished with a constant overhead in depth 14, of which eight steps involve only swap gates. Each qubit individually participates in six swap gates. Alternatively, these swaps might be replaced by teleported gates, at potentially lower constant cost, if the desired interactions correspond to Clifford gates.

Other mappings exist as well and expose new possibilities for tradeoffs and optimizations. For example, an interesting alternative mapping encodes the qubits of the square lattice into 3-qubit repetition codes on the left and right edges of each 3x5 rectangle (Figure 8, Left). This creates an effective heavy-square lattice where encoded qubits are separated by single auxiliary qubit (Figure 8, Right). In this encoding we can apply diagonal interactions in parallel along the vertical or horizontal direction of the heavy-square lattice. Since swaps occur in parallel between these two rounds of interactions, the total depth is only two rounds of swaps and two rounds of diagonal gates.

There are relatively simple circuits for applying single-qubit gates to the repetition code qubits whose cost is roughly equivalent to a swap gate. Since none of these operations is necessarily fault-tolerant, the error rate will increase by as much as a factor of three, but post-selection can be done for phase flip errors while one takes advantage of the gains from fact that the code itself corrects a single bit flip error. As mentioned, the cost of the encodings described above is a constant and is thus on equal footing with other constant overheads such as the choice of gate set used. These should be compared with the cost of mapping the problem itself to the quantum computer, which might have a polynomial overhead.

Figure 8:

Encoding into the 3-qubits repetition code (left) leads to a logical heavy square lattice (right).

Source: ibm.com

Continue reading