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

Chinese Science Bulletin (Chinese Version)

Shor整数分解量子算法的加速实现

皖苏 鲍, 向群 付, 淳 周

Published Feb 1, 2010• 2 citations
Publisher

Abstract

基于半经典量子Fourier变换的实现方法, 提出了整数k的3元二进制表示生成向量和生成函数概念, 构造了生成函数的真值表, 证明了由其逐比特生成的整数k的3元二进制表示向量是整数k的一种NAF表示, 且表示中非0元个数的最大值为[([logk]+1)/2], 并基于此重新设计了Shor算法的量子实现线路. 与Parker的Shor算法量子实现线路相比, 计算资源大体相同(所需的基本量子门数量均为O([logN]3), 所需的量子比特数量前者较后者多2量子比特), 但实现速度提高了2倍.

DOI
10.1360/csb2010-55-4-5-322

Related papers

t 比特半经典量子Fourier 变换

淳 周, 向群 付, 皖苏 鲍 +1 more

针对目前大维数量子寄存器生成的困难性, 研究了基于小维数量子寄存器实现大维数量子Fourier 变换的方法. 首先, 定义了t 比特半经典量子Fourier 变换, 从几率幅的角度证明该变换可以实现量子Fourier 变换, 且所需2 位量子门的规模显著降低, 并设计了该变换的量子实现线路. 然后基于t 比特半经典量子Fourier 变换, 将经典固定窗口法与Shor 算法实现方法相融合, 重新设计了Shor 整数分解量子算法的实现线路, 与Parker 等人的实现线路相比, 计算资源大体相同(所需的基本量子门均为所需量子寄存器的维数前者较后者多t -1维), 而实现速度提高了t2 倍, t 是窗口宽度.

Chinese Science Bulletin (Chinese Version)•Sep 1, 2011•1 citation

Towards a Refinement of Krylov Complexity: Scrambling, Classical Operator Growth and Replicas

Hugo A. Camargo, Yichao Fu, Keun-Young Kim +1 more

We propose and test logarithmic Krylov (logK) complexity, an operator growth measure akin to Krylov complexity defined through a replica approach, as a viable probe of early-time operator scrambling without false positives. In finite-dimensional quantum systems, such as the Lipkin--Meshkov--Glick (LMG) model and the mixed-field Ising model at the chaotic point, we provide numerical evidence that logK-complexity discriminates between genuine and saddle-dominated scrambling at early times, correctly avoiding the exponential contribution coming from the unstable saddle in the former case, and closely tracking the conventional Krylov complexity in the latter. In integrable quantum systems admitting infinite-dimensional Krylov subspaces, such as the SYK$_{2}$ model and the quantum inverted harmonic oscillator, we show that by modifying the Krylov spreading operator, obtained through generalizing the analytic continuation procedure in the replica trick, the logK complexity can be refined to capture the integrable properties of the theories. We supplement these analyses by extending the Krylov formalism in classical dynamical systems and defining classical versions of these operator growth measures, showing that the false positives arising from unstable saddles in classical phase space are non-existent.

hep-thCross-listedarXiv:2603.19359•Mar 23, 2026•0 citations

脉冲Fourier变换次谐波核磁共振

朝辉 叶

在相距为ω_0的相邻能级之间,同时吸收或发射能量为ω_0/n的n个量子的多量子过程,称为次谐波共振(SHR). 通常该能对之间不存在实际的中间能级,跃迁是容许的,在脉冲激励情形下可以直接观测. 然而,由于激励频率远离共振,激发效率很差,需要高阶微扰论处理. 具有中间能级的多量子跃迁,在一级微扰论近似下是禁阻的,在脉冲激励情形下通常不能直接观测. 这两种多量子跃迁都需要比单量子过程强得多的辐射场,以获得可以观测的效应.

Chinese Science Bulletin (Chinese Version)•Jul 1, 1984•0 citations

Shorの素因数分解アルゴリズムにおける計算量の精密な評価 (応用函数解析としての情報数理の研究)

Ken Kuriyama, Shintaro Sano, Shigeru Furuichi

•Oct 1, 2005•0 citations

Compression for Qubit Clocks

Yuxiang Yang, Giulio Chiribella, Masahito Hayashi

Two-Ievel (qubit) clock systems are often used to perform precise measurement of time. In this work, we propose a compression protocol for n identically prepared states of qubit clocks. The protocol faithfully encodes the states into (1/2) logn qubits and (1/2) logn classical bits and works even in the presence of noise. If the purity of the clock states is fixed, (1/2) logn qubits are sufficient. We also prove that this protocol requires the minimum amount of total memory among all protocols with vanishing error in the large n limit.

arXiv:2209.06519•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•0 citations

Quantum Guessing via Deutsch-Jozsa

Michael Nathanson

We examine the "Guessing Secrets" problem arising in internet routing, in which the goal is to discover two or more objects from a known finite set. We propose a quantum algorithm using O(1) calls to an O(logN) oracle. This improves upon the best known classical result, which uses O(logN) questions and requires an additional O(logN^3) steps to produce the answer. In showing the possibilities of this algorithm, we extend the types of questions and function oracles that the Deutsch-Jozsa algorithm can be used to solve.

arXiv:quant-ph/0301025•Jan 7, 2003•1 citation
基于半经典量子Fourier变换的实现方法, 提出了整数k的3元二进制表示生成向量和生成函数概念, 构造了生成函数的真值表, 证明了由其逐比特生成的整数k的3元二进制表示向量是整数k的一种NAF表示, 且表示中非0元个数的最大值为[([logk]+1)/2], 并基于此重新设计了Shor算法的量子实现线路. 与Parker的Shor算法量子实现线路相比, 计算资源大体相同(所需的基本量子门数量均为O([logN]3), 所需的量子比特数量前者较后者多2量子比特), 但实现速度提高了2倍.
针对目前大维数量子寄存器生成的困难性, 研究了基于小维数量子寄存器实现大维数量子Fourier 变换的方法. 首先, 定义了t 比特半经典量子Fourier 变换, 从几率幅的角度证明该变换可以实现量子Fourier 变换, 且所需2 位量子门的规模显著降低, 并设计了该变换的量子实现线路. 然后基于t 比特半经典量子Fourier 变换, 将经典固定窗口法与Shor 算法实现方法相融合, 重新设计了Shor 整数分解量子算法的实现线路, 与Parker 等人的实现线路相比, 计算资源大体相同(所需的基本量子门均为所需量子寄存器的维数前者较后者多t -1维), 而实现速度提高了t2 倍, t 是窗口宽度.
We propose and test logarithmic Krylov (logK) complexity, an operator growth measure akin to Krylov complexity defined through a replica approach, as a viable probe of early-time operator scrambling without false positives. In finite-dimensional quantum systems, such as the Lipkin--Meshkov--Glick (LMG) model and the mixed-field Ising model at the chaotic point, we provide numerical evidence that logK-complexity discriminates between genuine and saddle-dominated scrambling at early times, correctly avoiding the exponential contribution coming from the unstable saddle in the former case, and closely tracking the conventional Krylov complexity in the latter. In integrable quantum systems admitting infinite-dimensional Krylov subspaces, such as the SYK2_{2}2​ model and the quantum inverted harmonic oscillator, we show that by modifying the Krylov spreading operator, obtained through generalizing the analytic continuation procedure in the replica trick, the logK complexity can be refined to capture the integrable properties of the theories. We supplement these analyses by extending the Krylov formalism in classical dynamical systems and defining classical versions of these operator growth measures, showing that the false positives arising from unstable saddles in classical phase space are non-existent.
在相距为ω_0的相邻能级之间,同时吸收或发射能量为ω_0/n的n个量子的多量子过程,称为次谐波共振(SHR). 通常该能对之间不存在实际的中间能级,跃迁是容许的,在脉冲激励情形下可以直接观测. 然而,由于激励频率远离共振,激发效率很差,需要高阶微扰论处理. 具有中间能级的多量子跃迁,在一级微扰论近似下是禁阻的,在脉冲激励情形下通常不能直接观测. 这两种多量子跃迁都需要比单量子过程强得多的辐射场,以获得可以观测的效应.
Two-Ievel (qubit) clock systems are often used to perform precise measurement of time. In this work, we propose a compression protocol for n identically prepared states of qubit clocks. The protocol faithfully encodes the states into (1/2) logn qubits and (1/2) logn classical bits and works even in the presence of noise. If the purity of the clock states is fixed, (1/2) logn qubits are sufficient. We also prove that this protocol requires the minimum amount of total memory among all protocols with vanishing error in the large n limit.
We examine the "Guessing Secrets" problem arising in internet routing, in which the goal is to discover two or more objects from a known finite set. We propose a quantum algorithm using O(1) calls to an O(logN) oracle. This improves upon the best known classical result, which uses O(logN) questions and requires an additional O(logN^3) steps to produce the answer. In showing the possibilities of this algorithm, we extend the types of questions and function oracles that the Deutsch-Jozsa algorithm can be used to solve.