An Efficient Quantum Circuit Construction Method for Mutually Unbiased Bases in $n$-Qubit Systems

Mutually unbiased bases (MUBs) play a crucial role in numerous applications within quantum information science, such as quantum state tomography, error correction, entanglement detection, and quantum cryptography. Utilizing \(2^n + 1\) MUB circuits provides a minimal and optimal measurement strategy for reconstructing all \(n\)-qubit unknown states. It significantly reduces the number of measurements compared to the traditional \(4^n\) Pauli observables, also enhancing the robustness of quantum key distribution (QKD) protocols. Previous circuit designs that rely on a single generator can result in exponential gate costs for some MUB circuits. In this work, we present an efficient algorithm to generate each of the \(2^n + 1\) quantum MUB circuits on \(n\)-qubit systems within \(O(n^3)\) time. The algorithm features a three-stage structure, and we have calculated the average number of different gates for random sampling. Additionally, we have identified two linear properties: the entanglement part can be directly defined into \(2n - 3\) fixed sub-parts, and the knowledge of \(n\) special MUB circuits is sufficient to construct all \(2^n + 1\) MUB circuits. This new efficient and simple circuit construction paves the way for the implementation of a complete set of MUBs in diverse quantum information processing tasks on high-dimensional quantum systems.