What is a quantum-classical algorithm?

A quantum-classical algorithm (or hybrid quantum-classical algorithm) is an algorithm that alternates quantum and classical resources to variationally approximate the solution of a problem.

The term "alternate" indicates that the algorithm performs sequentially a subroutine (or loop) consisting of the instructions:

1. Prepare a quantum state;
2. Measure the quantum state;
3. Run classical computation.

The classical computation is usually an optimization algorithm that instructs the quantum processor to update/prepare a new quantum state, which is then the input of the next subroutine.

The term "variationally" brings to mind numerical techniques in quantum many-body physics, like the density matrix renormalization group (for short, DMRG), but also the history of calculus of variations in mathematical analysis. The term indicates that each subroutine varies some adjustable parameters of its quantum state.

Notice that the definition of a quantum-classical algorithm does not refer to quantum algorithms that require a generic use of classical resources (e.g., classical post-processing in Simon's algorithm). If that were the case, every quantum algorithm would end up to be a quantum-classical algorithm, and so this choice of terminology would be useless.

There are two widely studied examples of quantum-classical algorithms: QAOA and VQE.

• The quantum approximate optimization algorithm (QAOA) solves discrete combinatorial optimization problems (e.g., Max-Cut) [1].
• The variational quantum eigensolver algorithm (VQE) computes energies of Hamiltonians [2].

Fred Chong [3] asks:

Are quantum-classical algorithms candidates to demonstrate quantum advantage on NISQ devices?

Yes, why not: “While quantum computers are (currently) small and unreliable, a great way to exploit their special, but limited, abilities is to adopt a hybrid model which leverages both quantum and classical computation.” But, do we have a proof of advantage? No.

In fact, in 2018, John Preskill wrote [4]:

Will NISQ technology running QAOA or VQE be able to outperform classical algorithms that find approximate solutions to the same problems? Nobody knows, but we’re going to try it and see how well we can do.

Maybe I lost track of the literature, but I don't recall any solid demonstration of this.

In the quest for rigor, I like the following result: Farhi and Harrow [5] showed that classically sampling from even the shallowest depth version of the QAOA can be argued to be difficult for complexity theoretic reasons. This is interesting. The argument reminds to Instantaneous Quantum Polynomial (IQP) computation [6]. Beautiful topics.

As usual, anything that can help understanding the power and limitations of quantum computation is important.

To conclude, here is a note for builders. Given that you are not cool if you don't quote Richard Feynman in a quantum computing post, with the risk of increasing my crackpot index* by a substantial x < 5 points, I will quote Feynman. Here we are:

What I cannot build, I do not understand.

You can build quantum-classical algorithms with Amazon Braket hybrid jobs [7]. This can be done via the Amazon Braket SDK or PennyLane [8] (but you could use TensorFlow and PyTorch or create a custom Docker container image, if you like).

* "5 points for each mention of "Einstien", "Hawkins" or "Feynmann"". John Baez, The Crackpot Index.

[1] E. Farhi, J. Goldstone, & S. Gutmann, arXiv:1411.4028 [quant-ph].

[2] A. Peruzzo, et al. arXiv:1304.3061 [quant-ph].

[3] F. Chong, Hybrid Quantum-Classical Computing, Computer Architecture Today, 9th October, 2018.

[4] J. Preskill, arXiv:1801.00862 [quant-ph].

[5] E. Farhi, A. W. Harrow, arXiv:1602.07674 [quant-ph].

[6] M. J. Bremner, R. Jozsa, D. J. Shepherd, arXiv:1005.1407 [quant-ph].

[7] D. Poccia, Introducing Amazon Braket Hybrid Jobs – Set Up, Monitor, and Efficiently Run Hybrid Quantum-Classical Workloads.

[8] Amazon Braket Hybrid Jobs now supports PennyLane Lightning.