On the Realistic Worst-Case Analysis of Quantum Arithmetic Circuits

被引:1
作者
Paler A. [1 ,3 ,4 ]
Oumarou O. [2 ]
Basmadjian R. [2 ]
机构
[1] Aalto University, Espoo
[2] Clausthal University of Technology, Clausthal-Zellerfeld
[3] University of Texas at Dallas, Richardson, 75080, TX
[4] Transilvania University, Brasov
来源
IEEE Transactions on Quantum Engineering | 2022年 / 3卷
关键词
31;
D O I
10.1109/TQE.2022.3163624
中图分类号
学科分类号
摘要
We provide evidence that commonly held intuitions when designing quantum circuits can be misleading. In particular, we show that 1) reducing the T-count can increase the total depth; 2) it may be beneficial to trade controlled NOTs for measurements in noisy intermediate-scale quantum (NISQ) circuits; 2) measurement-based uncomputation of relative phase Toffoli ancillae can make up to 30% of a circuit's depth; and 4) area and volume cost metrics can misreport the resource analysis. Our findings assume that qubits are and will remain a very scarce resource. The results are applicable for both NISQ and quantum error-corrected protected circuits. Our method uses multiple ways of decomposing Toffoli gates into Clifford+T gates. We illustrate our method on addition and multiplication circuits using ripple-carry. As a byproduct result, we show systematically that for a practically significant range of circuit widths, ripple-carry addition circuits are more resource-efficient than the carry-lookahead addition ones. The methods and circuits were implemented in the open-source QUANTIFY software. © 2020 IEEE.
引用
收藏
相关论文
共 31 条
  • [1] Barenco A., Et al., Elementary gates for quantum computation, Phys. Rev. A, 52, 5, (1995)
  • [2] Chakrabarti S., Krishna Kumar R., Mazzola G., Stamatopoulos N., Woerner S., Zeng W.J., A threshold for quantum advantage in derivative pricing, Quantum, 5, (2021)
  • [3] Draper T.G., Kutin S.A., Rains E.M., Svore K.M., Alogarithmicdepth quantum carry-lookahead adder, Quantum Inf. Comput., 6, 4, pp. 351-369, (2006)
  • [4] Gheorghiu V., Mosca M., Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes, (2019)
  • [5] Gidney C., Halving the cost of quantum addition, Quantum, 2, (2018)
  • [6] Gidney C., Quantum block lookahead adders and the wait for magic states, (2020)
  • [7] Jones C., Low-overhead constructions for the fault-tolerant Toffoli gate, Phys. Rev. A, 87, (2013)
  • [8] Lin Y., Yu B., Li M., Pan D.Z., Layout synthesis for topological quantum circuits with 1-D and 2-D architectures, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 37, 8, pp. 1574-1587, (2018)
  • [9] Linke N.M., Et al., Experimental comparison of two quantum computing architectures, Proc. Nat. Acad. Sci. USA, 114, 13, pp. 3305-3310, (2017)
  • [10] Litinski D., A game of surface codes: Large-scale quantum computing with lattice surgery, Quantum, 3, (2019)