Search

Abstract We design an algorithm to determine the (minimum) T-count of any n-qubit (n ≥ 1) unitary W of size 2 n × 2 n , over the Clifford+T gate set. The space and time complexity of our algorithm are $$O\left({2}^{2n}\right)$$ O 2 2 n and $$O\left({2}^{2n{{{{\mathcal{T}}}}}_{\epsilon }(W)+4n}\right)$$ O 2 2 n T ϵ ( W ) + 4 n , respectively. $${{{{\mathcal{T}}}}}_{\epsilon }(W)$$ T ϵ ( W ) (ϵ-T-count) is the (minimum) T-count of an exactly implementable unitary U ( $${{{\mathcal{T}}}}(U)$$ T ( U ) ), such that d(U,W) ≤ ϵ and $${{{\mathcal{T}}}}(U)\le {{{\mathcal{T}}}}({U}^{{\prime} })$$ T ( U ) ≤ T ( U ′ ) where $${U}^{{\prime} }$$ U ′ is any exactly implementable unitary with $$d({U}^{{\prime} },W)\le \epsilon$$ d ( U ′ , W ) ≤ ϵ . d(. , .) is the global phase invariant distance. Our algorithm can also be used to determine the (minimum) T-depth as well as the minimum non-Clifford-gate count or depth required to implement any multi-qubit unitary with a finite universal gate set like Clifford+CS, Clifford+V, etc. For small enough ϵ, we can synthesize the optimal circuits.

Abstract We investigate the problem of synthesizing T-depth optimal quantum circuits for exactly implementable unitaries over the Clifford+T gate set. We construct a subset, $${{\mathbb{V}}}_{n}$$ V n , of T-depth 1 unitaries. T-depth-optimal decomposition of unitary U is $${e}^{i\phi }\left({\prod }_{i}{V}_{i}\right)C$$ e i ϕ ∏ i V i C , $${V}_{i}\in {{\mathbb{V}}}_{n}$$ V i ∈ V n , C is Clifford and $$| {{\mathbb{V}}}_{n}| \,\le \,n\cdot {2}^{5.6n}$$ ∣ V n ∣ ≤ n ⋅ 2 5.6 n . We use nested meet-in-the-middle technique to synthesize provably depth-optimal and T-depth-optimal circuits. For the latter, we achieve space and time complexity $$O({({4}^{{n}^{2}})}^{\lceil d/c\rceil })$$ O ( ( 4 n 2 ) ⌈ d / c ⌉ ) and $$O({({4}^{{n}^{2}})}^{(c-1)\lceil d/c\rceil })$$ O ( ( 4 n 2 ) ( c − 1 ) ⌈ d / c ⌉ ) respectively (d is the minimum T-depth, c ≥ 2 a constant). The previous best algorithm had complexity $$O({({3}^{n}\cdot {2}^{k{n}^{2}})}^{\lceil \frac{d}{2}\rceil }\cdot {2}^{k{n}^{2}})$$ O ( ( 3 n ⋅ 2 k n 2 ) ⌈ d 2 ⌉ ⋅ 2 k n 2 ) (k > 2.5 a constant). We design a more efficient algorithm with space and time complexity poly(n, 25.6n , d) (or $${{{\rm{poly}}}}({n}^{\log n},{2}^{5.6n},d)$$ poly ( n log n , 2 5.6 n , d ) with weaker assumptions). The claimed efficiency, optimality depends on conjectures.

Recently Chen and Gao \cite{ChenGao2017} proposed a new quantum algorithm for Boolean polynomial system solving, motivated by the cryptanalysis of some post-quantum cryptosystems. The key idea of their approach is to apply a Quantum Linear System (QLS) algorithm to a Macaulay linear system over $\mathbb{C}$, which is derived from the Boolean polynomial system. The efficiency of their algorithm depends on the condition number of the Macaulay matrix. In this paper, we give a strong lower bound on the condition number as a function of the Hamming weight of the Boolean solution, and show that in many (if not all) cases a Grover-based exhaustive search algorithm outperforms their algorithm. Then, we improve upon Chen and Gao's algorithm by introducing the Boolean Macaulay linear system over $\mathbb{C}$ by reducing the original Macaulay linear system. This improved algorithm could potentially significantly outperform the brute-force algorithm, when the Hamming weight of the solution is logarithmic in the number of Boolean variables. Furthermore, we provide a simple and more elementary proof of correctness for our improved algorithm using a reduction employing the Valiant-Vazirani affine hashing method, and also extend the result to polynomial systems over $\mathbb{F}_q$ improving on subsequent work by Chen, Gao and Yuan \citeChenGao2018. We also suggest a new approach for extracting the solution of the Boolean polynomial system via a generalization of the quantum coupon collector problem \cite{arunachalam2020QuantumCouponCollector}.

Quantum random-access lookup of a string of classical bits is a necessary ingredient in several important quantum algorithms. In some cases, the cost of such quantum random-access memory (qRAM) is the limiting factor in the implementation of the algorithm. In this article, we study the cost of fault-tolerantly implementing a qRAM. We construct and analyze generic families of circuits that function as a qRAM, discuss opportunities for qubit-time tradeoffs, and estimate their resource costs when embedded in a surface code.

Quantum++ is a modern general-purpose multi-threaded quantum computing library written in C++11 and composed solely of header files. The library is not restricted to qubit systems or specific quantum information processing tasks, being capable of simulating arbitrary quantum processes. The main design factors taken in consideration were the ease of use, portability, and performance. The library's simulation capabilities are only restricted by the amount of available physical memory. On a typical machine (Intel i5 8Gb RAM) Quantum++ can successfully simulate the evolution of 25 qubits in a pure state or of 12 qubits in a mixed state reasonably fast. The library also includes support for classical reversible logic, being able to simulate classical reversible operations on billions of bits. This latter feature may be useful in testing quantum circuits composed solely of Toffoli gates, such as certain arithmetic circuits.

We introduce and analyze a new type of decoding algorithm called general color clustering, based on renormalization group methods, to be used in qudit color codes. The performance of this decoder is analyzed under a generalized bit-flip error model, and is used to obtain the first memory threshold estimates for qudit 6-6-6 color codes. The proposed decoder is compared with similar decoding schemes for qudit surface codes as well as the current leading qubit decoders for both sets of codes. We find that, as with surface codes, clustering performs sub-optimally for qubit color codes, giving a threshold of $5.6 \% $ compared to the $8.0 \% $ obtained through surface projection decoding methods. However, the threshold rate increases by up to 112% for large qudit dimensions, plateauing around $11.9 \% $ . All the analysis is performed using https://github.com/jacobmarks/QTop , a new open-source software for simulating and visualizing topological quantum error correcting codes.

We study the robustness of the bucket brigade quantum random access memory model introduced by Giovannetti et al (2008 Phys. Rev. Lett. http://dx.doi.org/10.1103/PhysRevLett.100.160501 100 http://dx.doi.org/10.1103/PhysRevLett.100.160501 ). Due to a result of Regev and Schiff (ICALP ’08 733), we show that for a class of error models the error rate per gate in the bucket brigade quantum memory has to be of order $o({2}^{-n/2})$ (where $N={2}^{n}$ is the size of the memory) whenever the memory is used as an oracle for the quantum searching problem. We conjecture that this is the case for any realistic error model that will be encountered in practice, and that for algorithms with super-polynomially many oracle queries the error rate must be super-polynomially small, which further motivates the need for quantum error correction. By contrast, for algorithms such as matrix inversion Harrow et al (2009 Phys. Rev. Lett. http://dx.doi.org/10.1103/PhysRevLett.103.150502 103 http://dx.doi.org/10.1103/PhysRevLett.103.150502 ) or quantum machine learning Rebentrost et al (2014 Phys. Rev. Lett. http://dx.doi.org/10.1103/PhysRevLett.113.130503 113 http://dx.doi.org/10.1103/PhysRevLett.113.130503 ) that only require a polynomial number of queries, the error rate only needs to be polynomially small and quantum error correction may not be required. We introduce a circuit model for the quantum bucket brigade architecture and argue that quantum error correction for the circuit causes the quantum bucket brigade architecture to lose its primary advantage of a small number of ‘active’ gates, since all components have to be actively error corrected.