論文の概要: HUBO and QUBO models for Prime factorization
- arxiv url: http://arxiv.org/abs/2301.06738v1
- Date: Tue, 17 Jan 2023 07:49:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-18 14:36:11.240896
- Title: HUBO and QUBO models for Prime factorization
- Title（参考訳）: 素因数分解のためのHUBOモデルとQUBOモデル
- Authors: Kyungtaek Jun
- Abstract要約: RSA暗号システムのセキュリティは、N=p*qを満たす素数 p と q に大数 N を分解することの難しさに基づいている。
本稿では,RSA暗号システムを脅かすことができるD-Wave量子コンピュータを用いた素因数分解法を提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The security of the RSA cryptosystem is based on the difficulty of factoring
a large number N into prime numbers p and q satisfying N=p*q . This paper
presents a prime factoriaation method using D-Wave quantum computer that can
threaten the RSA cryptosystem. The starting point for this method is very
simple, representing two prime numbers as qubits. Then, set the difference
between the product of two prime numbers expressed in qubits and N as a cost
function, and find the solution when the cost function becomes the minimum.
D-Wave's quantum annealer can find the minimum value of any quadratic problem.
However, the cost function is to be a higher-order unconstrained optimiaation
(HUBO) model because it contains the second or higher order terms. We used a
hybrid solver and dimod package provided by -Wave Ocean software development
kit (SDK) to solve the HUBO problem. We also successfully factoriaed
102,454,763 with 26 logical qubits. In addition, we factoriaed
1,000,070,001,221 using the range dependent Hamiltonian algorithm.
- Abstract（参考訳）: RSA暗号システムのセキュリティは、N=p*q を満たす素数 p と q に大数 N を分解することの難しさに基づいている。
本稿では,rsa暗号を脅かすd波量子コンピュータを用いた素因数分解法を提案する。
この方法の出発点は非常に単純で、2つの素数を量子ビットとして表す。
次に、qubitsとnで表される2つの素数の積の差をコスト関数として設定し、コスト関数が最小になったときに解を見つける。
D-Waveの量子アニールは、任意の二次問題の最小値を見つけることができる。
しかし、コスト関数は2階またはそれ以上の項を含むため、高階非制約最適化(HUBO)モデルである。
我々は、-wave ocean software development kit (sdk) が提供するハイブリッドソルバとdimodパッケージを使用して、hubo問題を解決した。
また,論理キュービット26個で102,454,763個を分解した。
さらに,距離依存ハミルトンアルゴリズムを用いて1000,070,001,221の因子を推定した。
関連論文リスト
- Quantum inspired factorization up to 100-bit RSA number in polynomial time [0.0]
我々はシュノーアの数学的枠組みに基づくRSA因子化ビルディングを攻撃した。
我々は、量子システムにおける最適化問題を符号化する最大256ビットのRSA数を分解する。
結果は現在の通信インフラのセキュリティを損なうものではない。
論文 参考訳（メタデータ） (2024-10-21T18:00:00Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Integer Factorization by Quantum Measurements [0.0]
量子アルゴリズムは、古典的コンピュータでは解けない計算問題を解くために量子力学を使うことが進行中の努力の中心である。
既知の量子アルゴリズムの中で、特別な役割はShorアルゴリズム、すなわち整数分解のための量子時間アルゴリズムによって演じられる。
ここでは、別の真の量子特性(量子計測)に基づく整数分解の異なるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-19T17:00:01Z) - A comment on "Factoring integers with sublinear resources on a
superconducting quantum processor" [0.0]
そこで我々はSchnorr's lattice-based integer factorizationアルゴリズムのオープンソース実装について述べる。
我々の実装は、シュノーラーの整数を70ビットまでしか持たないハイブリッド量子+古典版に対する主張された部分線型格子次元が示している。
我々は、我々の実装が、他のハイブリッド量子/古典的整数分解アルゴリズムのアイデアをテストするための、コミュニティの場として機能することを願っている。
論文 参考訳（メタデータ） (2023-07-18T21:46:54Z) - Quasi-binary encoding based quantum alternating operator ansatz [7.681120805934572]
本稿では, 離散変数を持つ2次最適化モデルを解くための準バイナリ符号化に基づくアルゴリズムを提案する。
QAOAフレームワークの他の部分では、CVaR-QAOAやパラメータスケジューリング手法といったアイデアもQAOAアルゴリズムに取り入れています。
論文 参考訳（メタデータ） (2023-04-14T03:49:26Z) - An Efficient Quantum Decoder for Prime-Power Fields [1.0878040851638]
ブロックサイズ$n$に対して$p$が小さい$q = pm$の場合、時間内の問題を解く量子アルゴリズムが存在することを示す。
一方、古典的アルゴリズムはこの問題をはるかに小さな逆因子に対してのみ効率的に解くことができる。
論文 参考訳（メタデータ） (2022-10-20T19:35:50Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。