Quantumly controlled measurement, Hermitian conjugation and normalization in matrix-manipulation algorithms

Technical Summary: Quantumly Controlled Measurement, Hermitian Conjugation, and Normalization in Matrix-Manipulation Algorithms

Problem Statement
The paper addresses three critical limitations in existing quantum algorithms for matrix manipulation (specifically those based on encoding matrix elements into the probability amplitudes of a pure superposition state, as proposed in Refs. [33–35]):

1. Post-Selection Inefficiency: Current algorithms rely on measuring a single-qubit ancilla to filter out "garbage" states and select the desired result. This process suffers from a small success probability that decreases polynomially or exponentially with the matrix dimension. Consequently, the algorithm requires multiple runs to achieve the desired outcome, severely reducing efficiency.
2. Inability to Handle Hermitian Conjugation: While these algorithms generally handle complex matrices, specific operations like Hermitian conjugation cannot be realized within the standard encoding framework, restricting the variety of algebraic manipulations.
3. Strict Normalization Constraints: The encoding of matrix elements into a pure quantum state imposes a strict normalization condition ($\sum |a_{jk}|^2 = 1$). This limits the modulus of matrix elements, requiring specific scaling that may not be optimal for all applications.

Methodology
The authors propose three distinct extensions to the matrix-manipulation framework:

1. Quantumly Controlled Measurement (QCM):

   • Instead of a standard projective measurement on a single ancilla qubit ($B_1$), the authors introduce a two-qubit ancilla system ($B_1$ and $B_2$).
   • The state of the first qubit ($B_1$) acts as a control for a measurement operator applied to the second qubit ($B_2$).
   • Specifically, if the system is in a superposition where the "useful" term is entangled with $|1\rangle_{B_1}$ and the "garbage" with $|0\rangle_{B_1}$, a C-NOT gate entangles $B_1$ with $B_2$. A controlled measurement operator $W^{(3)}_{B_1B_2} = |1\rangle_{B_1}\langle 1| \otimes M_{B_2} + |0\rangle_{B_1}\langle 0| \otimes I_{B_2}$ is then applied.
   • This mechanism ensures that if the useful component exists ($\alpha \neq 0$), the measurement on $B_2$ is triggered deterministically, collapsing the system to the desired state without the probabilistic failure associated with standard post-selection.

2. Separate Encoding of Real and Imaginary Parts:

   • To enable Hermitian conjugation, the authors propose encoding the real and imaginary parts of complex matrix elements into two orthogonal subspaces using an additional one-qubit subsystem ($M$).
   • The state $|0\rangle_M$ labels the real part, and $|1\rangle_M$ labels the imaginary part.
   • Hermitian conjugation is then realized via a SWAP operation on the row/column registers combined with a $\sigma_z$ operation on the $M$ register, effectively performing transposition and complex conjugation.

3. Weakened Normalization Constraint:

   • The authors introduce an additional auxiliary qubit ($K$) to the encoding scheme.
   • The initial state is modified to include an extra term with amplitude $b$ associated with the state $|0\rangle_K$, while the matrix elements are associated with $|1\rangle_K$.
   • This changes the normalization condition from an equality ($\sum |a_{jk}|^2 = 1$) to an inequality ($\sum |a_{jk}|^2 \leq 1$), allowing for greater flexibility in the magnitude of matrix elements.

Key Contributions and Results

• Implementation in Matrix Multiplication: The authors integrate QCM and the two encoding extensions into a matrix multiplication algorithm. They demonstrate that the algorithm can perform standard multiplication as well as operations involving Hermitian conjugates (e.g., $A^\dagger B$, $A B^\dagger$).
• Circuit Construction: Detailed quantum circuits are presented for:
  • The QCM subroutine.
  • The Hermitian conjugation operator.
  • The modified matrix multiplication algorithm incorporating all three extensions.
• Complexity Analysis:
  • Space: The modifications require only a constant number of additional qubits (specifically, four additional qubits for the encoding extensions and one for the QCM ancilla in the multiplication context). The space complexity remains $O(n)$, where $N=2^n$ is the matrix dimension.
  • Depth: The circuit depth remains $O(n)$. The authors note that while the total runtime of previous algorithms was effectively $O(2^n n)$ due to the need for repeated runs to overcome low success probabilities, the QCM-based algorithm achieves the result in a single run, maintaining the $O(n)$ depth characteristic of the circuit itself.
• Normalization Retrieval: The authors acknowledge that QCM removes the probabilistic information regarding the normalization constant $G$ (which was previously derived from the success probability of the measurement). They propose a method to probabilistically measure $G$ by running the algorithm multiple times to measure the probability of the auxiliary state $|0\rangle_K$, though this requires separate runs from the single-shot result generation.

Significance and Claims
The paper claims that the introduction of Quantumly Controlled Measurement (QCM) fundamentally resolves the "post-selection problem" inherent in measurement-based quantum matrix algorithms. By replacing the probabilistic filtering of garbage states with a deterministic, quantum-controlled process, the algorithm eliminates the exponential overhead associated with repeated runs.

The authors emphasize that QCM is not merely an amplitude amplification technique (like Grover's algorithm) but a distinct operator combining quantum control with classical measurement, potentially offering a new type of "quantum-classical control."

Furthermore, the extensions regarding Hermitian conjugation and relaxed normalization constraints broaden the applicability of matrix-manipulation algorithms to a wider class of complex matrices and data encoding scenarios. The authors state that while the practical physical realization of QCM is not yet fully detailed in terms of standard quantum/classical operators, its theoretical formulation provides a justification for the reality of quantum superposition states and offers a pathway to more efficient quantum linear algebra.

The paper concludes that these modifications can be applied not only to matrix multiplication but also to other algorithms discussed in Refs. [34, 35], including matrix addition, determinant calculation, inversion, and linear system solvers, as well as other measurement-based quantum algorithms.