Extended Quantum Computing Patterns

Approximate the eigenvalue of a unitary matrix.

Given a unitary matrix \(U\) and one of its eigenstates, the corresponding eigenvalue should be determined. The eigenstate \(\newcommand{\state}[1]{{\left| #1 \right>}}\state{v}\) is given on a register in Basis Encoding. Applying \(U\) to the eigenstate \(\newcommand{\state}[1]{{\left| #1 \right>}}\state{v}\) results in a global phase:

where the eigenvalue \(\lambda = e^{2\pi i \varphi}\) is uniquely determined by \(\varphi \in [0,1]\). Therefore, it is sufficient to estimate \(\varphi\).

–

Use the circuit shown in the pattern sketch to estimate the approximation of \(\theta\). First, a register of \(m\) ancillae is brought into an Uniform Superposition. Next, controlled versions of powers of \(U\) are applied on the register of the eigenstate following the scheme depicted inthe pattern sketch. Each application of a controlled-\(U\) operation results in a phase kickback of the control qubit, i.e., this qubit acquires a relative phase of \(\varphi\). This results in the overall state:

where \(\varphi\) is encoded in the relative phase. To extract this information, the inverse of the quantum fourier transformation is applied on the ancilla register.

If \(\varphi\) is a rational number, the ancilla register contains the eigenvalue in Basis Encoding (assuming a proper number of anchillae). Otherwise, an approximation is produced with a probability of at least \(\frac{4}{\pi}\). Increasing the precision of the approximation by adding more ancillae is costly because this also increases the number of required controlled-\(U\) operations. Because of these demanding hardware requirements, this algorithm is often regarded as non-suitable for NISQ devices.

–

This pattern uses Amplitude Encoding and Matrix Encoding and produces an output in Basis Encoding.

Quantum Phase Estimation is at the heart of many algorithms [Cleve et al. 1998]. One prominent example which we review in a later section is the HHL algorithm [Harrow, Hassidim and Lloyd 2009]. Other QML algorithms follow a similar scheme [Schuld and Petruccione 2018, Duan et al. 2020], e.g., quantum support vector machine (QSVM) [Rebentrost et al. 2014] or quantum principal component analysis (QPCA) [Lloyd et al. 2014]. Qiskit provides an implementation for this pattern.

Shor's Algorithm (PlanQK) HHL Algorithm (PlanQK)

The second register can also be initialized as an arbitrary quantum state which is always a linear combination of eigenvectors. In this case, the algorithm approximates a superposition of eigenvalues for these eigenvectors in the output register. Other variants of this algorithm further improve the depth of the circuit or require fewer measurements.