## Introduction

Welcome to QNLP 2019, a workshop dedicated to the exciting field of near-term quantum computing. In this article, we will explore the main points discussed in a YouTube video by Jens Eisert titled “Rigorous statements on near-term quantum computing” and delve into rigorous statements and proof pockets in this field.

## Background

Near-term quantum computing is currently receiving a lot of attention and excitement as researchers race to explore the potential of this emerging technology. However, amidst the excitement, it can be challenging to fully grasp what is really achievable and the specific ways in which quantum computing can offer speedups.

While it may not be possible to answer all the important questions surrounding near-term quantum computing in this article, we can discuss the idea of making rigorous statements in this largely heuristic-driven field. By examining three instances of rigorous statements, we can gain a better understanding of the current progress and potential of near-term quantum computing.

## The Vision of Fully Fledged Quantum Computers

The guiding vision in this field is the idea of a fully fledged quantum computer capable of solving NP problems in polynomial time. The famous Shor’s algorithm and other hidden subgroup problems are prominent examples of this vision. However, the reality is that large-scale, fault-tolerant quantum computers are still a distant possibility.

## Current State: Small and Noisy Quantum Computers

Currently, we have small and noisy quantum computers, which may not have high average gate fidelities but still hold immense potential. Companies like IBM and Google have made significant progress in building quantum devices with qubit counts of up to 72. These devices, although small, were considered science-fiction not too long ago.

The focus now is on maximizing the capabilities of these small quantum computers by leveraging classical computers to perform most of the computations. Parametrized circuits with adjustable parameters are used, and classical computations are made based on the measured values obtained from these circuits. The parameters are then updated iteratively to improve the performance of the quantum computation.

Variational quantum circuits are a simple yet powerful method used in this setting. These circuits have knobs that can be tuned, and the aim is to minimize the expectation value of a tunable Hamiltonian. This approach has proven to be effective in areas like quantum chemistry and condensed matter physics.

## Quantum Approximate Optimization Algorithms (QAOA)

Another variation of variational algorithms is the Quantum Approximate Optimization Algorithm (QAOA). QAOA focuses on solving combinatorial optimization problems, such as Max Cut, using quantum computers. By representing the objective function as a Hamiltonian, quantum gates are applied to approximate the solution. Although QAOA has shown promise, more research is needed to understand its performance for multi-layer settings.

## Seeking Rigorous Answers

While the ideas and evidence discussed so far are exciting, there is a need to put them on a more systematic basis to make further progress. The goal is to understand quantum algorithms with guaranteed performance improvements and speed-ups. Before achieving this, it is essential to identify key building blocks and understand their functioning in a precise and rigorous manner.

Proof pockets, as they are sometimes called, are key building blocks in near-term quantum algorithms. They offer a quantitative and rigorous understanding of the performance of specific parts of the algorithm. By examining and connecting these proof pockets, a more comprehensive and systematic picture of near-term computing can be obtained.

## Stochastic or Quantum Doubly Stochastic Gradient Descent

One example of a proof pocket is the stochastic or quantum doubly stochastic gradient descent. This method is inspired by stochastic gradient methods commonly used in machine learning. The idea is to replace the usual gradient update rule with an update rule that contains a stochastic component.

In this context, measurements are made in the lab, and the goal is to estimate the gradient of the cost function. To simplify the process, the parameter shift rule is often used, which allows the partial derivatives of expectation values to be expressed as linear combinations of the same expectation values with slightly shifted parameters.

Rather than running the circuit many times to obtain precise expectation values, a simpler approach is taken. Instead, a limited number of measurements are made, and these measurements provide unbiased estimators of the expectation values. These estimators can then be used to estimate the gradient, resulting in a stochastic gradient descent method that offers improved efficiency.

## Conclusion

In this article, we explored the field of near-term quantum computing and discussed the main points highlighted in a YouTube video by Jens Eisert. We learned about the current state of small and noisy quantum computers, the use of variational quantum circuits, and the promise of Quantum Approximate Optimization Algorithms (QAOA).

We also discussed the importance of making rigorous statements and identifying proof pockets in near-term quantum algorithms. By focusing on these key building blocks and understanding their functioning in a quantitative and rigorous manner, we can make further progress and gain a more comprehensive understanding of near-term quantum computing.

While there is still much work to be done in this field, the rapid advancements and increasing interest in near-term quantum computing make it an exciting area of research. By combining rigorous analysis with the exploration of new algorithms and techniques, researchers can continue pushing the boundaries of what is achievable in the near term.

Stay tuned for more updates and exciting developments in the field of near-term quantum computing!

This article is inspired by the YouTube video “Rigorous statements on near-term quantum computing” by Jens Eisert, available at: https://www.youtube.com/watch?v=tns-01155