Time Complexity Reduction for Gate-Model Quantum Computers

A method is defined for the time complexity reduction of near-term gate-model quantum computers. The proposed solution evaluates the reduced time complexity equivalent of a reference quantum circuit and recovers the reference output quantum system of the reference quantum circuit via quantum operations on the output of the reduced time complexity quantum circuit. We prove the complexity of the proposed quantum algorithm and the achievable reduction in time complexity. We define the auxiliary cost of the proposed quantum algorithm and show that it is significantly lower than the gainable reduction in time complexity. The algorithm provides a tractable solution to reduce both time complexity and the economic cost of implementing the physical-layer quantum computer by reducing quantum hardware elements. The results are useful for experimental gate-model quantum computations and the near-term quantum devices of the quantum Internet.