Linear Combination of Unitaries (LCU)

The LCU method is a foundational quantum algorithmic primitive that enables the application of a non-unitary operator \(A\), expressed as a weighted sum of unitaries \(U_i\) as \(A=\sum_i\alpha_i U_i\), to a quantum state, by embedding \(A\) into a larger unitary circuit.

This is central to quantum algorithms for Hamiltonian simulation, Linear Combination of Hamiltonian Simulation (LCHS), Quantum Linear Systems (e.g. HHL algorithm), Quantum Signal Processing (QSP), and Quantum Singular Value Transformation (QSVT).

This function implements the prepare-select-unprepare structure, also known as block encoding:

\[\mathrm{LCU} = \mathrm{PREPARE}^\dagger \cdot \mathrm{SELECT} \cdot \mathrm{PREPARE}\]

• PREPARE: Prepares an ancilla variable in a superposition encoding the normalized coefficients \(\alpha_i\) of the target operator

\[\mathrm{PREPARE}|0\rangle=\sum_i\sqrt{\frac{\alpha_i}{\lambda}}|i\rangle\]

• SELECT: Applies the unitary \(U_i\) to the target variable, controlled on the ancilla variable being in state \(|i\rangle\).

\[\mathrm{SELECT}|i\rangle|\psi\rangle=|i\rangle U_i|\psi\rangle\]

• PREPARE$^{\dagger}$: Applies the inverse prepartion to the ancilla.

Note

The LCU protocol is deemed successful only if the ancilla variable is measured in the \(|0\rangle\) state, which occurs with a probability proportional to \(\frac{\langle\psi|A^{\dagger}A|\psi\rangle}{\lambda^2}\) where \(\lambda=\sum_i\alpha_i\). This function does not perform the measurement; it returns the ancilla variable and the transformed target variable.

The success probability depends on the LCU coefficients and the initial state’s properties. Said success probability can be further improved using Oblibious Amplitude Amplification, which applies a series of reflections and controlled operations to amplify the \(\ket{0}\) ancilla component without prior knowledge of the initial state. For implementation details in Qrisp, see qrisp.amplitude_amplification(). Within the LCU implementation this is included as an experimental feature.

For a complete implementation of LCU with the Repeat-Until-Success protocol, see qrisp.LCU().

For more details on the LCU protocol, refer to Childs and Wiebe (2012), or related seminars provided by Nathan Wiebe.

Caution

Nathan’s a cool guy, but do not call the SELECT unitary a qswitch in his presence, or else he might perform the Touch of Death (in reference to the movie The Men Who Stare at Goats). While on the topic, refer to qrisp.qswitch() for more information about how the SELECT operator is implemented efficiently in Qrisp (as qrisp.qswitch()).

Contents

inner_LCU(operand_prep, state_prep, unitaries)	Core implementation of the Linear Combination of Unitaries (LCU) protocol without Repeat-Until-Success (RUS) protocol.
LCU(*trial_args)	Full implementation of the Linear Combination of Unitaries (LCU) algorithmic primitive using the Repeat-Until-Success (RUS) protocol.
view_LCU(operand_prep, state_prep, unitaries)	Generate and return the quantum circuit for the LCU algorithm without utilizing the Repeat-Until-Success (RUS) protocol.