  Quantum computing is gaining popularity across a wide range of scientific
disciplines due to its potential to solve long-standing computational problems
that are considered intractable with classical computers. One promising area
where quantum computing has potential is in the speed-up of NP-hard
optimisation problems that are common in industrial areas such as logistics and
finance. Newcomers to the field of quantum computing who are interested in
using this technology to solve optimisation problems do not have an easily
accessible source of information on the current capabilities of quantum
computers and algorithms. This paper aims to provide a comprehensive overview
of the theory of quantum optimisation techniques and their practical
application, focusing on their near-term potential for noisy intermediate scale
quantum devices. Two main paradigms for quantum hardware are then discussed:
quantum annealing and gate-based quantum computing. While quantum annealers are
effective for some optimisation problems, they have limitations and cannot be
used for universal quantum computation. In contrast, gate-based quantum
computers offer the potential for universal quantum computation, but they face
challenges with hardware limitations and accurate gate implementation. The
paper provides a detailed mathematical discussion with references to key works
in the field, as well as a more practical discussion with relevant examples.
The most popular techniques for quantum optimisation on gate-based quantum
computers, the quantum approximate optimisation (QAO) algorithm and the quantum
alternating operator ansatz (QAOA) framework, are discussed in detail. The
paper concludes with a discussion of the challenges facing quantum optimisation
techniques and the need for further research and development to identify new,
effective methods for achieving quantum advantage.
