Recognition: unknown
Optimal ancilla-free Clifford+T approximation of z-rotations
read the original abstract
We consider the problem of approximating arbitrary single-qubit z-rotations by ancilla-free Clifford+T circuits, up to given epsilon. We present a fast new probabilistic algorithm for solving this problem optimally, i.e., for finding the shortest possible circuit whatsoever for the given problem instance. The algorithm requires a factoring oracle (such as a quantum computer). Even in the absence of a factoring oracle, the algorithm is still near-optimal under a mild number-theoretic hypothesis. In this case, the algorithm finds a solution of T-count m + O(log(log(1/epsilon))), where m is the T-count of the second-to-optimal solution. In the typical case, this yields circuit approximations of T-count 3log_2(1/epsilon) + O(log(log(1/epsilon))). Our algorithm is efficient in practice, and provably efficient under the above-mentioned number-theoretic hypothesis, in the sense that its expected runtime is O(polylog(1/epsilon)).
This paper has not been read by Pith yet.
Forward citations
Cited by 17 Pith papers
-
Design automation and space-time reduction for surface-code logical operations using a SAT-based EDA kernel compatible with general encodings
KOVAL-Q uses SAT solving to optimize and verify surface-code logical operations with general encodings, finding d-cycle CNOTs and 2d-cycle rotations that reduce FTQC application runtime by about 10 percent.
-
Magic state cultivation: growing T states as cheap as CNOT gates
Magic state cultivation prepares high-fidelity T states with an order of magnitude fewer qubit-rounds than prior distillation methods by gradually growing them within a surface code under depolarizing noise.
-
C-Phase-Aware Compilation for Efficient Fault-Tolerant Quantum Execution
A microarchitecture-aware compiler for lattice surgery that exploits C-Phase commutativity to enable concurrent multi-target operations and dynamic event-driven scheduling, cutting execution time by up to 59.7 times v...
-
Price and Payoff: Non-Determinism in Fault Tolerant Quantum Computation
Stochastic magic-state production in fault-tolerant quantum computing inflates execution time but reduces peak resource demand, allowing stochastic-aware factory allocation to cut space-time volume by up to 27% and fa...
-
Quantum Magic in early FTQC: From Diagonal Clifford Hierarchy No-Go Theorems to Architecture Design Blueprints
No-go theorems prove hierarchy level and state-independent sequences cannot maximize operational magic in early FTQC, requiring state-aware differentiable optimization and nonlinear phases for scalable magic generation.
-
FTPrimitiveBench: A Benchmark Suite For Logical Computation Under Hardware-Motivated and Biased Noise Models
FTPrimitiveBench is a new benchmark suite for testing surface-code logical primitives under Pauli-biased, measurement-biased, and spatially non-uniform noise models, revealing that noise structure interacts distinctly...
-
From Characterization To Construction: Generative Quantum Circuit Synthesis from Gate Set Tomography Data
A generative QMLC framework tokenizes GST data, embeds it via curriculum-trained set-vision transformers into a context-aware latent space, and uses diffusion models to synthesize circuits conditioned on desired measu...
-
Fault-Tolerant Resource Comparison of Qudit and Qubit Encodings for Diagonal Quadratic Operators
Qudit encodings for quadratic diagonal evolutions require exponentially stronger synthesis advantages than qubits to win asymptotically in product formulas but can yield constant-factor savings in LCU at low d.
-
INJEQT: Improved Magic-State Injection Protocol for Fault-Tolerant Quantum Extractor Architectures
INJEQT reduces synthillation error by up to 22x, wall-clock time by 13x, and space-time cost by 7.2x in extractor FTQC architectures via auxiliary Rz synthesis and pre-fetching.
-
Assessing System Capabilities and Bottlenecks of an Early Fault-Tolerant Bicycle Architecture
Syn@fac optimization reduces estimated circuit failure probability by a factor of 9 on average across non-Clifford benchmarks for bivariate bicycle code modular FTQC architectures, with additional gains from transvect...
-
Architecting Early Fault Tolerant Neutral Atoms Systems with Quantum Advantage
A teleportation-based parallelization architecture for neutral-atom quantum error correction delivers up to 3x speedup over extractor methods at fixed space cost and enables simulated quantum advantage at 11,495 atoms...
-
Fault-Tolerant Quantum Computing with Trapped Ions: The Walking Cat Architecture
A trapped-ion architecture based on LDPC codes and cat-state factories achieves 110 logical qubits and one million T gates per day using 2514 physical qubits, with estimates for Heisenberg model simulation on 100 site...
-
O3LS: Optimizing Lattice Surgery via Automatic Layout Searching and Loose Scheduling
O3LS reduces space overhead by up to 46.7% and time overhead by up to 36% in lattice surgery while suppressing logical error rates by up to an order of magnitude compared with prior layout and scheduling approaches.
-
When T-Depth Misleads: Predicting Fault-Tolerant Quantum Execution Slowdown under Magic-State Delivery Constraints
Delta_max outperforms T-depth as a predictor of slowdown under magic-state constraints and supplies a tight lower bound on makespan with zero violations across 4,904 test instances.
-
Ether of Orbifolds
Orbifold lattices incur m^4 Trotter overhead, m^2 contamination, and mandatory mass extrapolation, rendering them 10^4 to 10^10 times costlier than alternatives for a 10^3 calculation.
-
FTPrimitiveBench: A Benchmark Suite For Logical Computation Under Hardware-Motivated and Biased Noise Models
FTPrimitiveBench is an open-source pipeline that connects parameterized hardware-motivated noise models to surface-code logical primitive circuits, enabling reproducible cross-primitive QEC benchmarking under Pauli bi...
-
Benchmarking and Resource Analysis for Augmented-Lagrangian Quantum Hamiltonian Descent
AL-QHD benchmarks on nonconvex test functions and ACOPF power problems show useful accuracy at fixed qubit cost but require roughly 10^8 T gates for realistic instances.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.