Almost Optimal Synthesis of Reversible Function in Qudit Model

doi:10.1109/TIT.2025.3640111

CSpace

	Almost Optimal Synthesis of Reversible Function in Qudit Model
	Xu, Buji 1,2; Nie, Junhong 1,2; Sun, Xiaoming 1,2
	2026-02-01
发表期刊	IEEE TRANSACTIONS ON INFORMATION THEORY
ISSN	0018-9448
卷号	72 期号:2 页码:1201-1211
摘要	Quantum oracles are widely adopted in problems, like query oracle in Grover's algorithm, cipher in quantum cryptanalytic and data encoder in quantum machine learning. Notably, the bit-flip oracle, capable of flipping the state based on a given classical function, emerges as a fundamental component in the design and construction of quantum algorithms. Devising methods to optimally implement the bit-flip oracle essentially translates to the efficient synthesis of reversible functions. Prior research has primarily focused on the qubit model, leaving the higher dimensional systems, i.e. qudit model, largely unexplored. By allowing more than two computational bases, qudit model can fully utilize the multi-level nature of the underlying physical mechanism. We propose a method to synthesize even permutations in A(d)n using Theta(d) (n-1) -qudit sub-circuits, which achieve asymptotic optimality in the count of sub-circuits. Moreover, we introduce a technique for synthesizing reversible functions employing O(nd(n)) two-qudit gates and only a single ancilla. This is asymptotically tight in terms of d and asymptotically almost tight in terms of n.
关键词	Logic gates Quantum circuit Qubit Integrated circuit modeling Quantum algorithm Complexity theory S Box Reversible computing Quantum mechanics Finite element analysis Circuit synthesis quantum circuit reversible computing
DOI	10.1109/TIT.2025.3640111
收录类别	SCI
语种	英语
WOS研究方向	Computer Science ; Engineering ; Mathematics
WOS类目	Computer Science, Information Systems ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic ; Mathematics, Applied
WOS记录号	WOS:001671955100036
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/42864
专题	中国科学院计算技术研究所
通讯作者	Sun, Xiaoming
作者单位	1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 100049, Peoples R China
推荐引用方式 GB/T 7714	Xu, Buji,Nie, Junhong,Sun, Xiaoming. Almost Optimal Synthesis of Reversible Function in Qudit Model[J]. IEEE TRANSACTIONS ON INFORMATION THEORY,2026,72(2):1201-1211.
APA	Xu, Buji,Nie, Junhong,&Sun, Xiaoming.(2026).Almost Optimal Synthesis of Reversible Function in Qudit Model.IEEE TRANSACTIONS ON INFORMATION THEORY,72(2),1201-1211.
MLA	Xu, Buji,et al."Almost Optimal Synthesis of Reversible Function in Qudit Model".IEEE TRANSACTIONS ON INFORMATION THEORY 72.2(2026):1201-1211.