Is useful quantum computing possible in the NISQ era?

We are now in the era of Noisy Intermediate Scale Quantum devices (NISQ). As explained in an earlier blog the quantum devices available today have few qubits and high error rates. Quantum error correction may not be feasible on NISQ devices because of the extra overhead of detecting and correcting errors. There is a wide divergence of expert opinions about whether any useful quantum computations can be carried out in the NISQ era, with some arguing that we must wait many years for larger, fully error corrected quantum devices.

Here I will assess the Variational family of Quantum algorithms (VQA), quantum annealing and photonic quantum computers, to see if these might be useful in the NISQ era.

Variational Quantum algorithms

In a 2021 review paper Marco Cerezo and others describe different variational quantum algorithms and their use cases. Readers of this blog may not have time to read the full paper, with its 293 references, so I will summarise the key points below.

A common feature of all algorithms in the VQA family is a cost function which must be minimised. For example, in an optimization problem the cost function is simply the quantity to be minimised, and might also include constraints. In quantum chemistry the cost function is often the energy of the molecule being studied. Many machine learning problems require optimization of a loss function that measures the quality of the prediction. In VQA the cost function is mapped to a quantum circuit with tunable parameters. Designing a quantum circuit for a particular cost function is a challenge, but fortunately there are already several existing circuit architectures. “Problem-dependent” architectures are designed for a particular problem whilst “problem-agnostic” architectures are more general.

If the cost function is parameterised by two parameters it can be visualised as the height above ground of a three-dimensional surface made up of a range of hills and valleys, just as shown in the diagram below. The aim is to find the lowest point of the surface. With more than two parameters unfortunately the cost function is less easy to visualise but the same principle applies. The output of the quantum circuit is measured, usually many times, to find the cost function, and the results passed to a classical optimiser to calculate new parameters for the quantum circuit. Often the optimiser uses a gradient descent approach and the next parameters are lower down the local slope. If necessary the process is repeated until the outputs of successive iterations are sufficiently close, when it is assumed that the minimum of the cost function has been found. This is very similar to how deep-learning networks are optimised.

Quantum Approximate Optimization Algorithm (QAOA)

An early example of an algorithm from the VQA family is the Quantum Approximate Optimization Algorithm (QAOA), originally introduced to obtain approximate solutions for “combinatorial optimization” problems. An example of these problems is the Max-Cut problem, where vertices of a network need to be divided into two sets in a way that maximises the number of edges cut when the two sets are separated by a curve. In the example shown below we find by trial and error that the maximum edges that a line can cut is five. The solution can be written out by listing the vertices in one of the sets as {Vertex 0 = ‘True’, Vertex 1 = ‘False’, Vertex 2 = ‘False’, Vertex3 = ‘True’, Vertex4 = ‘True’} or by simply writing the bit string 10011. Solving Max-Cut is equivalent to maximising a cost function that depends on an input bit string. Although this example might seem abstract, these types of problems are very relevant to a wide range of real-world optimization use cases.

In a promising paper that appeared in Nature in 2021, Matt Harrigan and others at Google demonstrated the QAOA optimisation algorithm on a Google Sycamore superconducting qubit quantum device. Although the results were no better than classical techniques, the paper shows that good progress is being made, even on quantum devices where each qubit is only connected to four other qubits.

Another early example of an algorithm from the VQA family is the Variational Quantum Eigensolver (VQE). This algorithm finds the ground state energy of a molecule in quantum chemistry problems and uses the fact that quantum hardware can store a global quantum state with exponentially fewer resources than required by classical hardware. In this case the cost function represents the energy of a molecule and the parameterised circuit is modified until the energy is minimised. There is a good VQE tutorial using Qiskit.

VQA has also been used in machine learning and there are some promising results. We will cover this topic in a future blog. Use cases include:

• classifiers which are trained to predict the label of each input
• autoencoders, which compress quantum data,
• generative models which learn the probability distribution that generates a given data set
• Generative Adversarial Networks (GANs) where two neural networks, a generator and a discriminator, work together. The discriminator is trained to recognise an image and the generator produces spoof images, and tries to convince the discriminator that these are real
• Quantum Neural Networks where each node in the neural network is replaced by a qubit

To deliver these use cases there are three challenges that VQAs need to overcome: barren plateaus, local minima and the coupling of the quantum and classical computers. Let’s look at each of these in turn.

Challenges to be addressed

Barren plateaus

A challenge for VQA is that there can be “barren plateaus” in the cost function where a solution can’t easily be reached. A barren plateau is a flat area of the cost function where there is no slope to lead the optimiser to a lower point.

There are two approaches to overcome barren plateaus. Firstly, the circuits used need to be carefully designed. For example, “hardware efficient” circuits are optimised for different quantum devices. Secondly, the initial parameters used are not chosen at random. For example, in a 2021 paper Alejandro Perdomo-Ortiz and colleagues from Zapata, showed significant improvements by learning the structure of successful parameters from a training set of related problems. Seeding the initial parameters may be especially useful for optimisation problems that need to be solved repeatedly, for example, to optimise traffic flow in real time. Arthur Pesah and others analysed quantum convolutional neural networks (QCNNs) and found these do not exhibit barren plateaus.

Local minima

A second challenge is that there can be “local minima” where the cost function is at a low point, like a valley, but this is not the “ global minimum” or true lowest point in the landscape. The optimiser can get stuck at this local minimum, and never find the global minimum. Fortunately, there are possible solutions to this challenge.

For example, in a 2021 paper Stefan Sack and Maksym Serbyn explain how to initialise the parameters for a QAOA algorithm to reduce the chance of the optimiser getting stuck in a local minima. They used a “Trotterized quantum annealing” (TQA) protocol to seed the initial parameters, in contrast to the machine learning approach of Alejandro Perdomo-Ortiz’s team discussed above. In another significant 2022 paper David Amaro and colleagues at Cambridge Quantum Computing introduce F-VQE, a special case of Quantum Variation Filtering (QVF), and argue that it is relevant for current quantum devices because of its low quantum hardware requirements. David explained to me that their experiments show that in combinatorial optimization problems “F-VQE” does not get stuck in local minima as much as the other algorithms VQE or QAOAs because it filters out sub-optimal solutions. In another 2021 paper Javier Rivera-Dean and others propose coupling the output of the quantum circuit to a classical neural network to escape local minima and suggest that relaxing the cost landscape may improve near-term quantum computing algorithms.

Coupling of quantum and classical devices

Another potential challenge is that the quantum devices need to be closely coupled to a classical device, so time is not wasted sending messages back and forth in the feedback loop. IBM’s quantum road map anticipates this requirement and envisages quantum devices woven seamless together with classical CPUs and GPUs. Digital Catapult is working with leading UK quantum companies including BT, ORCA Computing and Riverlane to build a quantum data centre of the future which will also help address this challenge. Nvida recently announced quantum optimized device architecture (QODA), an “open programming model that aims to make hybrid quantum-classical programming more accessible” and a series of partnerships with quantum hardware providers.

Other opportunities

In another 2021 review paper Kishor Bharti and others review quantum annealing and photonics, as well as VQA.

In a quantum annealer qubits are linked together and the strength of the links are varied to match the problem. “Quadratic Unconstrained Binary Optimization” (QUBO) problems similar to the MaxCut example above work well with this architecture. The system is allowed to settle to the lowest energy state, which is hopefully a solution to the problem. In 2021 D-Wave, a Canadian firm, announced the launch of Advantage quantum system, with more than 5000 qubits and 15-way qubit connectivity. They list some impressive optimisation proof of concepts.

Photonic devices can also be used for quantum computing. In these devices phase shifters and beam splitters are used to manipulate the quantum states of particles of light or photons. There is a good notebook explaining photonic devices on the Pennylane website. In 2020 Han-Sen Zhong and colleagues claimed that their Jiuzhang photonic device could not be simulated on a classical computer, opening the way to later quantum advantage, where it is cheaper and easier to solve a problem on a photonic device than a classical computer. In a 2021 paper Kamil Bradler and Hugo Wallner at ORCA Computing showed that photonic quantum devices could be used to solve the small Max Cut optimization problems described above and optimise portfolio assets. A simulator can be found on GitHub. An advantage of ORCA and other photonic devices is that they can run at room temperature.

To conclude…

At present we are not aware of any instances where a quantum computer is being used commercially in preference to a classical computer. However, we think it is very plausible that in the next few years quantum devices will perform useful computations more cheaply than classical computers. We base this on the promising proof of concepts we have seen, and expected future improvements in both quantum devices and algorithms. Variational Quantum Algorithms, quantum annealing, and photonic computers seem the most promising technologies for the near term.

Many thanks to Kris Kaczmarek and William Clements at ORCA computing, David Amaro at Cambridge Quantum Computers, Matt Harrigan at Google Quantum AI, and Javier Rivera-Dean at ICFO for valuable input.