Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Springer eBooks

Parallelizing with Limited Number of Ancillae

Hideaki Abe, Shao Chin Sung

Published Jan 1, 2001• 0 citations
Publisher
DOI
10.1007/978-1-4471-0313-4_11

Related papers

Parallelizing gates with high-dimensional ancillas

Brown, Kendon

Conference on Lasers and Electro-Optics•Jan 1, 2012•0 citations

From Leaves to Clusters: Depth-Efficient SAT-Oracle Synthesis Based on the FORM Model

Zhihang Li, Wei Zi, Shuai Yang +7 more

Quantum oracles play a fundamental role in many quantum algorithms, such as Grover's search and quantum counting. In oracle synthesis, reducing the circuit depth under a limited number of ancilla qubits is essential, given the constraints of current quantum devices. However, for satisfiability oracles (SAT-oracles) under a limited ancilla budget, existing synthesis methods fail to fully exploit clause-level parallelism, leading to deep circuits. In practice, evaluating clauses in parallel can quickly exhaust the ancilla budget. To address this issue, we introduce the Clustered Synthesis Tree (CST), a depth-oriented SAT-oracle synthesis framework that exploits clause-level parallelism while respecting the ancilla budget. CST leverages a recursive synthesis tree as the backbone for scheduling clause evaluations and groups its clause leaves into clusters, whose clauses are evaluated in parallel by a reversible oracle called ClausePack. To form the clusters, CST introduces a polynomial-time heuristic called SeedGrow for the NP-hard clause-grouping problem, and the resulting tree is compiled into an executable circuit by CST-Map. Compared with the depth-oriented pAND baseline, CST can reduce the circuit depth by an average of 10.2x and 8.8x-11.0x on SATLIB and random 4-CNF benchmarks, respectively, under the same ancilla budgets, while also outperforming the width-oriented pAND, clause-storing, and qSAT baselines.

quant-pharXiv:2607.11401•Jul 14, 2026•0 citations

SQUARE: Strategic Quantum Ancilla Reuse for Modular Quantum Programs via Cost-Effective Uncomputation

Yongshan Ding, Xin-Chuan Wu, Adam Holmes +4 more

Compiling high-level quantum programs to machines that are size constrained (i.e. limited number of quantum bits) and time constrained (i.e. limited number of quantum operations) is challenging. In this paper, we present SQUARE (Strategic QUantum Ancilla REuse), a compilation infrastructure that tackles allocation and reclamation of scratch qubits (called ancilla) in modular quantum programs. At its core, SQUARE strategically performs uncomputation to create opportunities for qubit reuse.Current Noisy Intermediate-Scale Quantum (NISQ) computers and forward-looking Fault-Tolerant (FT) quantum computers have fundamentally different constraints such as data locality, instruction parallelism, and communication overhead. Our heuristic-based ancilla-reuse algorithm balances these considerations and fits computations into resource-constrained NISQ or FT quantum machines, throttling parallelism when necessary. To precisely capture the workload of a program, we propose an improved metric, the “active quantum volume,” and use this metric to evaluate the effectiveness of our algorithm. Our results show that SQUARE improves the average success rate of NISQ applications by 1. 47X. Surprisingly, the additional gates for uncomputation create ancilla with better locality, and result in substantially fewer swap gates and less gate noise overall. SQUARE also achieves an average reduction of 1. 5X (and up to 9. 6X) in active quantum volume for FT machines.

arXiv:2004.08539•Proceedings - International Symposium on Computer Architecture/Proceedings•May 1, 2020•40 citations

Generation of arbitrary quantum states in cavity-atom systems with a three-level ancilla

Da-Wei Luo, Ting Yu

We generalized the seminal work of Law & Eberly, and propose a protocol to generate arbitrary quantum states with a three-level atom as an ancilla in a more efficient manner. This protocol moves two excitations in parallel in each control step, thus reducing the number of evolution steps by half. Full analytical expressions for the control field strengths and timings are derived. The system dynamics is exposed to less chance of error accumulation in the timing and amplitudes of the control fields, and quantitative study in the context of the quantum speed limit is also considered.

quant-pharXiv:2609.32845•Sep 29, 2026•0 citations

Speed of computation and simulation

Subhash C. Kak

Foundations of Physics•Oct 1, 1996•7 citations

Parallel algorithms for coupled-cluster methods

John D. W. Watts

Parallel Computing•Jul 1, 2000•9 citations
Quantum oracles play a fundamental role in many quantum algorithms, such as Grover's search and quantum counting. In oracle synthesis, reducing the circuit depth under a limited number of ancilla qubits is essential, given the constraints of current quantum devices. However, for satisfiability oracles (SAT-oracles) under a limited ancilla budget, existing synthesis methods fail to fully exploit clause-level parallelism, leading to deep circuits. In practice, evaluating clauses in parallel can quickly exhaust the ancilla budget. To address this issue, we introduce the Clustered Synthesis Tree (CST), a depth-oriented SAT-oracle synthesis framework that exploits clause-level parallelism while respecting the ancilla budget. CST leverages a recursive synthesis tree as the backbone for scheduling clause evaluations and groups its clause leaves into clusters, whose clauses are evaluated in parallel by a reversible oracle called ClausePack. To form the clusters, CST introduces a polynomial-time heuristic called SeedGrow for the NP-hard clause-grouping problem, and the resulting tree is compiled into an executable circuit by CST-Map. Compared with the depth-oriented pAND baseline, CST can reduce the circuit depth by an average of 10.2x and 8.8x-11.0x on SATLIB and random 4-CNF benchmarks, respectively, under the same ancilla budgets, while also outperforming the width-oriented pAND, clause-storing, and qSAT baselines.
Compiling high-level quantum programs to machines that are size constrained (i.e. limited number of quantum bits) and time constrained (i.e. limited number of quantum operations) is challenging. In this paper, we present SQUARE (Strategic QUantum Ancilla REuse), a compilation infrastructure that tackles allocation and reclamation of scratch qubits (called ancilla) in modular quantum programs. At its core, SQUARE strategically performs uncomputation to create opportunities for qubit reuse.Current Noisy Intermediate-Scale Quantum (NISQ) computers and forward-looking Fault-Tolerant (FT) quantum computers have fundamentally different constraints such as data locality, instruction parallelism, and communication overhead. Our heuristic-based ancilla-reuse algorithm balances these considerations and fits computations into resource-constrained NISQ or FT quantum machines, throttling parallelism when necessary. To precisely capture the workload of a program, we propose an improved metric, the “active quantum volume,” and use this metric to evaluate the effectiveness of our algorithm. Our results show that SQUARE improves the average success rate of NISQ applications by 1. 47X. Surprisingly, the additional gates for uncomputation create ancilla with better locality, and result in substantially fewer swap gates and less gate noise overall. SQUARE also achieves an average reduction of 1. 5X (and up to 9. 6X) in active quantum volume for FT machines.
We generalized the seminal work of Law & Eberly, and propose a protocol to generate arbitrary quantum states with a three-level atom as an ancilla in a more efficient manner. This protocol moves two excitations in parallel in each control step, thus reducing the number of evolution steps by half. Full analytical expressions for the control field strengths and timings are derived. The system dynamics is exposed to less chance of error accumulation in the timing and amplitudes of the control fields, and quantitative study in the context of the quantum speed limit is also considered.