Depth and Width are inconsistent

microsoft / qsharp-runtime

Runtime components for Q#

MIT License

286 stars 93 forks source link

Describe the bug

When qubits are allocated and released during a function call in a loop, the reported depth corresponds to a circuit where all function calls occur in parallel, but the reported width does not account for all qubits that must be simultaneously allocated.

To Reproduce

The following code creates the issue when run with the QTraceSimulator with OptimizeDepth=true in it's configuration.

operation Test(): Unit {
        let blockNum = 4;
        let blockSize = 4;
        use inputs = Qubit[blockSize*blockNum]{
            for i in 0..blockNum - 1 {
                use anc = Qubit[blockSize]{
                    for k in 1..4
                    {
                        for j in 0..blockSize-1 
                        {
                            T(inputs[i*blockSize+j]);
                            T(anc[j]);
                        }

                    }
                }
            }
        }

Expected behavior

The function Test should have T-depth 4 but width of 4*(4+4) = 48. At the very least, the number of T-gates should be at most the product of T-depth and the total width.

Actual behavior

When run on Test, the trace simulator outputs:

initial width = 0
extra width = 20
T-depth = 4
T-count = 128 Notice that the t-depth times the total width (which should be an upper bound on the T-count) is 80, but it claims a T-count of 128

System information

Q# version 0.24.210930
OS: Ubuntu 20.04
.NET Core Version: 6.0.300

Additional context

This is roughly the same bug that was supposed to be fixed here: https://github.com/microsoft/qsharp-runtime/pull/404.

Setting OptimizeDepth=false gives the expected behaviour: extra width is 36, but the T-depth is 16.

This is a critical issue, there is a growing Q# community using the resource estimator in various works in cryptanalysis [1,2,3,4,5] because of its ease of use. Having inconsistent circuit size outputs undermines these works and possible follow ups.

[1] Jaques, S., Naehrig, M., Roetteler, M., Virdia, F. (2020). Implementing Grover Oracles for Quantum Key Search on AES and LowMC. In: Canteaut, A., Ishai, Y. (eds) Advances in Cryptology – EUROCRYPT 2020. EUROCRYPT 2020. Lecture Notes in Computer Science(), vol 12106. Springer, Cham. https://doi.org/10.1007/978-3-030-45724-2_10

[2] Häner, T., Jaques, S., Naehrig, M., Roetteler, M., Soeken, M. (2020). Improved Quantum Circuits for Elliptic Curve Discrete Logarithms. In: Ding, J., Tillich, JP. (eds) Post-Quantum Cryptography. PQCrypto 2020. Lecture Notes in Computer Science(), vol 12100. Springer, Cham. https://doi.org/10.1007/978-3-030-44223-1_23

[3] Davenport, J.H., Pring, B. (2021). Improvements to Quantum Search Techniques for Block-Ciphers, with Applications to AES. In: Dunkelman, O., Jacobson, Jr., M.J., O'Flynn, C. (eds) Selected Areas in Cryptography. SAC 2020. Lecture Notes in Computer Science(), vol 12804. Springer, Cham. https://doi.org/10.1007/978-3-030-81652-0_14

[4] Xavier Bonnetain, Samuel Jaques (2020). Quantum Period Finding against Symmetric Primitives in Practice. https://doi.org/10.48550/arXiv.2011.07022

[5] Zhenyu Huang, Siwei Sun (2022). Synthesizing Quantum Circuits of AES with Lower T-depth and Less Qubits. https://eprint.iacr.org/2022/620

microsoft / qsharp-runtime