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

IACR Communications in Cryptology

New SAT-based Model for Quantum Circuit Decision Problem: Searching for Low-Cost Quantum Implementation

Jingwen Chen, Qun Liu, Yanhong Fan, Lixuan Wu, Boyun Li, Meiqin Wang

Published Apr 9, 2024• 9 citations
Publisher

Abstract

In recent years, quantum technology has been rapidly developed. As security analyses for symmetric ciphers continue to emerge, many require an evaluation of the resources needed for the quantum circuit implementation of the encryption algorithm. In this regard, we propose the quantum circuit decision problem, which requires us to determine whether there exists a quantum circuit for a given permutation f using M ancilla qubits and no more than K quantum gates within the circuit depth D. Firstly, we investigate heuristic algorithms and classical SAT-based models in previous works, revealing their limitations in solving the problem. Hence, we innovatively propose an improved SAT-based model incorporating three metrics of quantum circuits. The model enables us to find the optimal quantum circuit of an arbitrary 3 or 4-bit S-box under a given optimization goal based on SAT solvers, which has proved the optimality of circuits constructed by the tool, LIGHTER-R. Then, by combining different criteria in the model, we find more compact quantum circuit implementations of S-boxes such as RECTANGLE and GIFT. For GIFT S-box, our model provides the optimal quantum circuit that only requires 8 gates with a depth of 31. Furthermore, our model can be generalized to linear layers and improve the previous SAT-based model proposed by Huang et al. in ASIACRYPT 2022 by adding the criteria on the number of qubits and the circuit depth.

DOI
10.62056/anmmp-4c2h

Related papers

Quantum logic synthesis for Satisfiability Problems.

Shuai Yang, Wei Zi, Bujiao Wu +3 more

To demonstrate the advantage of quantum computation, many attempts have been made to attack classically intractable problems, such as the satisfiability problem (SAT), with quantum computer. To use quantum algorithms to solve these NP-hard problems, a quantum oracle with quantum circuit implementation is usually required. In this manuscript, we first introduce a novel algorithm to synthesize quantum logic in the Conjunctive Normal Form (CNF) model. Compared with linear ancillary qubits in the implementation of Qiskit open-source framework, our algorithm can synthesize an m clauses n variables k-CNF with $O(k^2 m^2/n)$ quantum gates by only using three ancillary qubits. Both the size and depth of the circuit can be further compressed with the increase in the number of ancillary qubits. When the number of ancillary qubits is $\Omega(m^\epsilon)$ (for any $\epsilon > 0$), the size of the quantum circuit given by the algorithm is O(km), which is asymptotically optimal. Furthermore, we design another algorithm to optimize the depth of the quantum circuit with only a small increase in the size of the quantum circuit. Experiments show that our algorithms have great improvement in size and depth compared with the previous algorithms.

•Jan 14, 2021•1 citation

Efficient Quantum Circuit Synthesis for SAT-Oracle With Limited Ancillary Qubit

Shuai Yang, Wei Zi, Bujiao Wu +3 more

One of the main concerns in the era of noisy intermediate-scale quantum (NISQ) computing and fault-tolerant quantum computing is the optimization of circuit implementation for quantum oracles, particularly with limited resources. Synthesizing a satisfiability (SAT) oracle, a crucial component in solving SAT problems, presents a significant challenge. The current state-of-the-art implementation of an$m$-clause SAT-oracle necessitates$2m-1$ancillary qubits and a linear number of elementary gates. We develop two efficient and ancilla-adjustable synthesis algorithms to reduce the overall quantum resource usage. Our first quantum oracle algorithm achieves quadratic optimization in the number of ancillary qubits with merely eight times increased circuit size. We also show that using only three ancillary qubits with quadratic circuit size expansion is enough. Our second algorithm optimizes the circuit depth of the SAT oracle to$\tilde {O}(\log m)$using$m$ancillary qubits. By running our algorithms on classical intractable SAT instances featured in SAT competitions, the experiment results show that our required quantum resources align well with our theoretical analysis. Our algorithms highlight the scalability of SAT-oracle-based algorithms in near-term quantum devices, such as Grover’s algorithm.

arXiv:2101.05430•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 19, 2023•5 citations

Constructing resource-efficient quantum circuits for AES

Liang Jiang, Bin‐Bin Cai, Fei Gao +3 more

An efficient quantum implementation of the advanced encryption standard (AES) is crucial for reducing the complexity of implementing an exhaustive key search through Grover’s algorithm. In this paper, we study how to construct resource-efficient quantum circuits for AES. We consider the product of T-gates depth and width (TDW) and the product of full depth and width (FDW) as optimization targets. We propose a generic method, called the controlled control qubit cascade (CCQC) technique, to construct quantum circuits for nonlinear components with reduced TDW and FDW. Using this, we construct a quantum circuit for the AES S-box. Compared with recent work presented at ASIACRYPT 2023, our S-box quantum circuit achieves reductions of 2.3% in TDW and 45.2% in FDW. Additionally, we propose a new key schedule strategy to reduce the full depth of the AES quantum circuit. Finally, the trade-offs between T-gates depth and width and the parallel numbers of S-box and TDW are analyzed.

Frontiers in Physics•Apr 22, 2025•5 citations

A SAT Encoding for Optimal Clifford Circuit Synthesis

Sarah Schneider, Lukas Burgholzer, Robert Wille

Executing quantum algorithms on a quantum computer requires compilation to representations that conform to all restrictions imposed by the device. Due to devices' limited coherence times and gate fidelities, the compilation process has to be optimized as much as possible. To this end, an algorithm's description first has to be synthesized using the device's gate library. In this paper, we consider the optimal synthesis of Clifford circuits---an important subclass of quantum circuits, with various applications. Such techniques are essential to establish lower bounds for (heuristic) synthesis methods and gauging their performance. Due to the huge search space, existing optimal techniques are limited to a maximum of six qubits. The contribution of this work is twofold: First, we propose an optimal synthesis method for Clifford circuits based on encoding the task as a satisfiability (SAT) problem and solving it using a SAT solver in conjunction with a binary search scheme. The resulting tool is demonstrated to synthesize optimal circuits for up to 26 qubits---more than four times as many as the current state of the art. Second, we experimentally show that the overhead introduced by state-of-the-art heuristics exceeds the lower bound by 27 % on average. The resulting tool is publicly available at https://github.com/cda-tum/qmap.

arXiv:2208.11713•Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 16, 2023•30 citations

Efficient quantum circuit implementation of the SM4 S-box

LIU JiaHong, Xiaoqing Tan, LI Ming +1 more

In recent years, the quantum circuit implementation in symmetric cryptography has attracted widespread attention. The SM4 block cipher algorithm is China's first commercial cipher standard and was accepted as an ISO/IEC international standard in 2021. S-box is the most complex component in the SM4 block cipher algorithm. This study investigates the quantum circuit implementation of the SM4 S-box. Based on the algebraic structure, using tower filed decomposition technology, the quantum circuit of the SM4 S-box is built. Based on the number of NCT gate sets, our quantum circuit requires 20 qubits, 52 Toffoli gates, 196 CNOT gates, and 13 X gates. The Toffoli depth of our circuit is 36. Compared with previous literature, the quantum circuit proposed herein requires fewer quantum resources.

Zhongguo kexue. Wulixue Lixue Tianwenxue•Dec 8, 2023•4 citations

New record in the number of qubits for a quantum implementation of AES

Zhenqiang Li, Fei Gao, Su‐Juan Qin +1 more

Optimizing the quantum circuit for implementing Advanced Encryption Standard (AES) is crucial for estimating the necessary resources in attacking AES by the Grover algorithm. Previous studies have reduced the number of qubits required for the quantum circuits of AES-128/-192/-256 from 984/1112/1336 to 270/334/398, which is close to the optimal value of 256/320/384. It becomes a challenging task to further optimize them. AimTaking aim at this task, we find a method for how the quantum circuit of AES S-box can be designed with the help of the automation tool LIGHTER-R. Particularly, the multiplicative inversion in F28 , which is the main part of the S-box, is converted into the multiplicative inversion (and multiplication) in F24 , then the latter can be implemented by LIGHTER-R because its search space is small enough. By this method, we construct the quantum circuits of S-box for mapping |a⟩|0⟩ to |a⟩|S(a)⟩ and |a⟩|b⟩ to |a⟩|b ⊕ S(a)⟩ with 20 qubits instead of 22 in the previous studies. In addition, we introduce new techniques to reduce the number of qubits required by the S-box circuit for mapping |a⟩ to |S(a)⟩ from 22 in the previous studies to 16. Accordingly, we synthesize the quantum circuits of AES-128/-192/-256 with 264/328/392 qubits, which implies a new record.

Frontiers in Physics•Mar 24, 2023•21 citations
In recent years, quantum technology has been rapidly developed. As security analyses for symmetric ciphers continue to emerge, many require an evaluation of the resources needed for the quantum circuit implementation of the encryption algorithm. In this regard, we propose the quantum circuit decision problem, which requires us to determine whether there exists a quantum circuit for a given permutation f using M ancilla qubits and no more than K quantum gates within the circuit depth D. Firstly, we investigate heuristic algorithms and classical SAT-based models in previous works, revealing their limitations in solving the problem. Hence, we innovatively propose an improved SAT-based model incorporating three metrics of quantum circuits. The model enables us to find the optimal quantum circuit of an arbitrary 3 or 4-bit S-box under a given optimization goal based on SAT solvers, which has proved the optimality of circuits constructed by the tool, LIGHTER-R. Then, by combining different criteria in the model, we find more compact quantum circuit implementations of S-boxes such as RECTANGLE and GIFT. For GIFT S-box, our model provides the optimal quantum circuit that only requires 8 gates with a depth of 31. Furthermore, our model can be generalized to linear layers and improve the previous SAT-based model proposed by Huang et al. in ASIACRYPT 2022 by adding the criteria on the number of qubits and the circuit depth.
To demonstrate the advantage of quantum computation, many attempts have been made to attack classically intractable problems, such as the satisfiability problem (SAT), with quantum computer. To use quantum algorithms to solve these NP-hard problems, a quantum oracle with quantum circuit implementation is usually required. In this manuscript, we first introduce a novel algorithm to synthesize quantum logic in the Conjunctive Normal Form (CNF) model. Compared with linear ancillary qubits in the implementation of Qiskit open-source framework, our algorithm can synthesize an m clauses n variables k-CNF with O(k2m2/n)O(k^2 m^2/n)O(k2m2/n) quantum gates by only using three ancillary qubits. Both the size and depth of the circuit can be further compressed with the increase in the number of ancillary qubits. When the number of ancillary qubits is Ω(mϵ)\Omega(m^\epsilon)Ω(mϵ) (for any ϵ>0\epsilon > 0ϵ>0), the size of the quantum circuit given by the algorithm is O(km), which is asymptotically optimal. Furthermore, we design another algorithm to optimize the depth of the quantum circuit with only a small increase in the size of the quantum circuit. Experiments show that our algorithms have great improvement in size and depth compared with the previous algorithms.
One of the main concerns in the era of noisy intermediate-scale quantum (NISQ) computing and fault-tolerant quantum computing is the optimization of circuit implementation for quantum oracles, particularly with limited resources. Synthesizing a satisfiability (SAT) oracle, a crucial component in solving SAT problems, presents a significant challenge. The current state-of-the-art implementation of anmmm-clause SAT-oracle necessitates2m−12m-12m−1ancillary qubits and a linear number of elementary gates. We develop two efficient and ancilla-adjustable synthesis algorithms to reduce the overall quantum resource usage. Our first quantum oracle algorithm achieves quadratic optimization in the number of ancillary qubits with merely eight times increased circuit size. We also show that using only three ancillary qubits with quadratic circuit size expansion is enough. Our second algorithm optimizes the circuit depth of the SAT oracle toO~(log⁡m)\tilde {O}(\log m)O~(logm)usingmmmancillary qubits. By running our algorithms on classical intractable SAT instances featured in SAT competitions, the experiment results show that our required quantum resources align well with our theoretical analysis. Our algorithms highlight the scalability of SAT-oracle-based algorithms in near-term quantum devices, such as Grover’s algorithm.
An efficient quantum implementation of the advanced encryption standard (AES) is crucial for reducing the complexity of implementing an exhaustive key search through Grover’s algorithm. In this paper, we study how to construct resource-efficient quantum circuits for AES. We consider the product of T-gates depth and width (TDW) and the product of full depth and width (FDW) as optimization targets. We propose a generic method, called the controlled control qubit cascade (CCQC) technique, to construct quantum circuits for nonlinear components with reduced TDW and FDW. Using this, we construct a quantum circuit for the AES S-box. Compared with recent work presented at ASIACRYPT 2023, our S-box quantum circuit achieves reductions of 2.3% in TDW and 45.2% in FDW. Additionally, we propose a new key schedule strategy to reduce the full depth of the AES quantum circuit. Finally, the trade-offs between T-gates depth and width and the parallel numbers of S-box and TDW are analyzed.
Executing quantum algorithms on a quantum computer requires compilation to representations that conform to all restrictions imposed by the device. Due to devices' limited coherence times and gate fidelities, the compilation process has to be optimized as much as possible. To this end, an algorithm's description first has to be synthesized using the device's gate library. In this paper, we consider the optimal synthesis of Clifford circuits---an important subclass of quantum circuits, with various applications. Such techniques are essential to establish lower bounds for (heuristic) synthesis methods and gauging their performance. Due to the huge search space, existing optimal techniques are limited to a maximum of six qubits. The contribution of this work is twofold: First, we propose an optimal synthesis method for Clifford circuits based on encoding the task as a satisfiability (SAT) problem and solving it using a SAT solver in conjunction with a binary search scheme. The resulting tool is demonstrated to synthesize optimal circuits for up to 26 qubits---more than four times as many as the current state of the art. Second, we experimentally show that the overhead introduced by state-of-the-art heuristics exceeds the lower bound by 27 % on average. The resulting tool is publicly available at https://github.com/cda-tum/qmap.
In recent years, the quantum circuit implementation in symmetric cryptography has attracted widespread attention. The SM4 block cipher algorithm is China's first commercial cipher standard and was accepted as an ISO/IEC international standard in 2021. S-box is the most complex component in the SM4 block cipher algorithm. This study investigates the quantum circuit implementation of the SM4 S-box. Based on the algebraic structure, using tower filed decomposition technology, the quantum circuit of the SM4 S-box is built. Based on the number of NCT gate sets, our quantum circuit requires 20 qubits, 52 Toffoli gates, 196 CNOT gates, and 13 X gates. The Toffoli depth of our circuit is 36. Compared with previous literature, the quantum circuit proposed herein requires fewer quantum resources.
Optimizing the quantum circuit for implementing Advanced Encryption Standard (AES) is crucial for estimating the necessary resources in attacking AES by the Grover algorithm. Previous studies have reduced the number of qubits required for the quantum circuits of AES-128/-192/-256 from 984/1112/1336 to 270/334/398, which is close to the optimal value of 256/320/384. It becomes a challenging task to further optimize them. AimTaking aim at this task, we find a method for how the quantum circuit of AES S-box can be designed with the help of the automation tool LIGHTER-R. Particularly, the multiplicative inversion in F28 , which is the main part of the S-box, is converted into the multiplicative inversion (and multiplication) in F24 , then the latter can be implemented by LIGHTER-R because its search space is small enough. By this method, we construct the quantum circuits of S-box for mapping |a⟩|0⟩ to |a⟩|S(a)⟩ and |a⟩|b⟩ to |a⟩|b ⊕ S(a)⟩ with 20 qubits instead of 22 in the previous studies. In addition, we introduce new techniques to reduce the number of qubits required by the S-box circuit for mapping |a⟩ to |S(a)⟩ from 22 in the previous studies to 16. Accordingly, we synthesize the quantum circuits of AES-128/-192/-256 with 264/328/392 qubits, which implies a new record.