Resource-Efficient Synthesis of Sparse Quantum States

The gist: The authors propose a novel methodology for constructing resource-efficient quantum circuits to prepare sparse quantum states, demonstrating that circuit depth and non-Clifford count can be linear in sparsity when access to arbitrary-angled rotations is given.

Resource Efficiency Metrics

The proposed quantum circuit has specific resource bounds: our quantum circuit has O(s maxmax(s, n)) size, O(s + maxmax(s, n)) depth, O(s) non-Clifford count, and maxmax(s, n) − n ancillary qubits (Page 2). This construction is highlighted as having depth and non-Clifford count; both of which are better than the state-of-the-art (Page 2). The depth is described as (additively) linear in both sparsity s and number of qubit n, while the non-Clifford count is linear in sparsity s, while being independent on the number of qubit (Page 2).

Construction Methodology

The methodology is divided into two main parts:

1. A quantum circuit for preparing a generalization of a special quantum state called W-state (which they can already find in [26]) (Page 2).

2. A classically reversible quantum circuit which transforms the terms of the W-state to those of the target sparse quantum state (Page 2).

The first part involves building a generalized W-state, and the second part is a classically reversible circuit which transforms the terms of the W-state to those of the sparse quantum state (Page 2). The former comprises solely CX and CRY gates, while the latter comprises X, CX and CCX gates (Page 2). The goal in both cases is to primarily attempt to reduce the number of non-Clifford gates, i.e., CRY and CCX, while also optimizing gate parallelization, which leads to a linear depth (Page 2).

Matrix Diagonalization Approach

The synthesis problem is reduced to the diagonalization of a binary matrix, using a specific set of elementary matrix operations corresponding to the classical reversible gates (Page 2). They solve this using a new version of Gauss-Jordan elimination, that minimizes the circuit complexities including circuit depth using parallel elimination steps (Page 2). A key observation is that all occurrences of (the expensive) Toffoli gates can all be replaced by adaptive Clifford circuits, leading to a better non-Clifford count when the circuit is applied in one direction (Page 2).

W-State Preparation and Tree Construction

The paper introduces a construction for mapping each ei⟩ to a target classical state using Theorem 1, which states that there exists a unitary Uχ such that "Uχ: ei⟩ ⊗ 0 ⊗ m−s⟩ → χi⟩ ⊗ 0 ⊗ m−n> and which can be implemented by a circuit with O(s) T-count, O(s+n) depth, and O(s(s+n)) gate-count" (Page 5). This construction relies on building an m × s matrix Mχ whose columns are the target states padded with zeros (Page 6). The goal is to turn this matrix into the identity matrix using classical reversible gates (X, CX and CCX) (Page 6).

For preparing weighted W-states, they use a tree-based construction where the circuit C(t) maps 1⟩ to W(⃗α)⟩ (Page 9). The depth of this circuit is O(h(t)) and its gate count is O(n) (Page 9). For any n qubits and arbitrary weights, the result shows that W(⃗α)⟩ can be prepared by a circuit with O(n) size, O(log2 (n)) depth, and O(n) non-Clifford gates" (Page 10).

Fault-Tolerant Compilation

When compiling down to the Clifford+T gate set, several constructions are provided for increasingly better T-count and depth at the expense of a larger number of ancillae (Page 1). The most optimised construction for T-count reaches O(s log2(1/ϵ) + log2(1/ϵ)) T gates for error ϵ, a result on par with an optimal construction for full state preparation by Gosset et al. [23] (Page 1). This is shown in Table 2, where the T-count reaches O p s log2(1/ϵ) + log2(1/ϵ) for one of the constructions (Page 3).

Sparse State Synthesis Results

The final synthesis result shows that an s-sparse, n-qubit state ψ⟩ can be exactly prepared using a circuit with O(s(s + n)) circuit size, O(s + n) circuit depth, O(s) non-Clifford gates, and maxmax(0, s − n) ancillary qubits (Page 5). When compiling down to the Clifford+T gate set, one construction yields O p s log2(1/ϵ) + log2(1/ϵ) T-count and O (s + n + log2(s) log2(1/ϵ)) maxmax(0, s − n) depth (Page 5).

Uniform W-State Optimization

For uniform W states, Corollary 8 shows that Wn⟩ can be prepared by a circuit with O(n) circuit size, O(log2 (n)) circuit depth, O(n) T gates, and O(log2 (n)) nonClifford+T gates (Page 10). Furthermore, Corollary 15 states that any s-sparse n-qubit state with non-zero values in the set of states whose non-zero entries are in the set of states whose non-zero entries are in a complete set of four phases up to renormalisation can be prepared exactly by a circuit with O(√s) T-gates, O(s 2) dirty ancillae, O(s + n) depth and success probability > 1/2" (Page 15).

Conclusion

The paper concludes that the sparse state construction is divided into the generation of sparse state coefficients via the weighted W-state, and then using the circuits for mapping the ei⟩ states to the target states (Page 6). They conjecture that the above construction is optimal in T-count whatever the sparsity s (Page 12). The authors also suggest that investigating whether the synthesis of W-states can be generalized to that of another special state called Dicke-states, which is a further generalization of W-states could lead to a more compact synthesis (Page 13).

C Synthesis Algorithms

The paper provides algorithms for matrix manipulation: Algorithm 1, AntiDiagRemoval, and Algorithm 2, UpElimComp (Page 21). These algorithms detail the process of removing anti-diagonals of U and performing row additions or column swaps to achieve the desired transformation (Page 21). The details on how to build the permutation P are provided in Section A (Page 7).

T-Gate Implementation Details

The circuit Fp, which implements a rotation, can be implemented in the Clifford+T gate set iff p ∈ [0, 1/2, 1] (Page 18). When p = 1/2, the RY gate can be replaced by the CH gate, which indeed is in Clifford+T (Page 18). In other cases, Fp requires non-Clifford+T gates to be built exactly (Page 18). This implies that for worst-case scenarios, they can always use [14, 42] to compile down to Clifford+T up to some epsilon error (Page 18).

Final Resource Bounds

The most T-wise optimised construction yields O p s log2(1/ϵ) + log2(1/ϵ) T-count, which is on par with the optimality result from [23] for full-state preparation (Page 6). This is conjectured to be optimal for sparse states (Page 6). The final construction reaches the same T-count as the full-state preparation from [23], but where sparsity replaces the overall number of entries (Page 11).

Success Probability

For uniform W states, Corollary 12 demonstrates that "W(⃗α)⟩ can be prepared exactly by a circuit with O(√n) T-gates, O(n 2) dirty ancillae, O(log2 (n 2)) depth and success probability > 1/2 (Page 19). This is achieved through a circuit involving a comparator and postselection measurement (Page 19). The phase gates are implemented using a layer of Clifford phase gates, followed by a layer of identities and T-gates" (Page 20).

Compilation to Clifford+T

Theorem 14 shows that for an s-sparse, n-qubit state ψ⟩, it can be prepared up to error epsilon > 0 using one of three circuits with varying metrics (Page 12). The last construction reaches the same T-count as the full-state preparation from [23], but where sparsity replaces the overall number of entries (Page 12). This construction is conjectured to be optimal in T-count whatever the sparsity s (Page 12).

1. The improved AI system can prepare an arbitrary sparse quantum state in a circuit with size O(s max(s, n)), depth O(s + max(s, n)), and non-Clifford count O(s), which is linear in sparsity s and independent of the number of qubits n.

2. The system can achieve T-count complexity of O p s log2(1/epsilon) + log2(1/epsilon) when compiled to the Clifford+T gate set, matching the optimality result for full state preparation [23].

3. For uniform W states, the system can prepare Wn⟩ exactly with O(√n) T-gates, O(log2(n)) depth, and success probability > 1/2 (Corollary 15).

4. The system can prepare sparse states whose non-zero entries are in specific sets of phase angles using O(√s) T-gates, where s is the number of non-zero entries.

Preparing a quantum circuit that implements a given sparse state is an important building block that is necessary for many different quantum algorithms. In the context of fault-tolerant quantum computing, the so-called non-Clifford gates are much more expensive to perform than the Clifford ones. We hence provide an algorithm for synthesizing sparse quantum states with a special care for quantum resources. The circuit depth, ancilla count, and crucially non-Clifford count of the circuit produced by the algorithm are all linear in the sparsity when access to arbitrary-angled rotations is given. When compiled down to the standard Clifford+T gate set, several constructions can be given for increasingly better T-count and depth at the expense of a larger number of ancillae. The most optimised construction for T-count reaches O (s+ 2(1/ε)) T gates for error ε. The constructions are broken into two parts, one that synthesises a generalized W-state, well studied in the literature; and the second which is a classical reversible circuit implementing a permutation that maps the basis states of the W-state to those of the target sparse quantum state. We reduce this problem to the diagonalization of a binary matrix, using a specific set of elementary matrix operations corresponding to the classical reversible gates. We then solve this problem using a new version of Gauss-Jordan elimination, that minimizes the circuit complexities including circuit depth using parallel elimination steps. When the circuit is applied in one direction, we notice that all occurrences of (the expensive) Toffoli gates can all be replaced by adaptive Clifford circuits, leading to a better non-Clifford count.