論文の概要: Quantum Backtracking in Qrisp Applied to Sudoku Problems
- arxiv url: http://arxiv.org/abs/2402.10060v3
- Date: Wed, 4 Sep 2024 14:59:16 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-07 03:56:02.593648
- Title: Quantum Backtracking in Qrisp Applied to Sudoku Problems
- Title（参考訳）: 数独問題に応用したQrispの量子バックトラッキング
- Authors: Raphael Seidel, René Zander, Matic Petrič, Niklas Steinmann, David Q. Liu, Nikolay Tcholtchev, Manfred Hauswirth,
- Abstract要約: 任意のバックトラックインスタンスに対して量子ステップ演算子を実装するための詳細な命令を提供する。
深さnのバイナリバックトラックツリーの単一の制御ディフューザに対して、我々の実装では、たった6n+14$ CXゲートしか必要としない。
これは、この一般化のコンパイル可能な実装の最初の例であり、量子ソフトウェア工学における重要な、そしてエキサイティングな進歩を示している。
- 参考スコア（独自算出の注目度）: 0.52197339162908
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The quantum backtracking algorithm proposed by Ashley Montanaro raised considerable interest, as it provides a quantum speed-up for a large class of classical optimization algorithms. It does not suffer from Barren-Plateaus and transfers well into the fault-tolerant era, as it requires only a limited number of arbitrary angle gates. Despite its potential, the algorithm has seen limited implementation efforts, presumably due to its abstract formulation. In this work, we provide a detailed instruction on implementing the quantum step operator for arbitrary backtracking instances. For a single controlled diffuser of a binary backtracking tree with depth n, our implementation requires only $6n+14$ CX gates. We detail the process of constructing accept and reject oracles for Sudoku problems using our interface to quantum backtracking. The presented code is written using Qrisp, a high-level quantum programming language, making it executable on most current physical backends and simulators. Subsequently, we perform several simulator based experiments and demonstrate solving 4x4 Sudoku instances with up to 9 empty fields. This is, to the best of our knowledge, the first instance of a compilable implementation of this generality, marking a significant and exciting step forward in quantum software engineering.
- Abstract（参考訳）: アシュリー・モンタナロによって提案された量子バックトラックアルゴリズムは、古典最適化アルゴリズムの大規模なクラスに対して量子スピードアップを提供するため、かなりの関心を集めている。
Barren-Plateaus に苦しめられず、任意の角度ゲートの限られた数しか必要としないため、フォールトトレラント時代にうまく移行する。
その可能性にもかかわらず、アルゴリズムは、おそらくその抽象的な定式化のために、実装の努力が限られている。
本研究では、任意のバックトラックインスタンスに対して量子ステップ演算子を実装するための詳細な命令を提供する。
深さnのバイナリバックトラックツリーの単一の制御ディフューザに対して、我々の実装では、たった6n+14$ CXゲートしか必要としない。
本稿では, 量子バックトラックのためのインタフェースを用いて, 数独問題に対するアクセプション・アンド・リジェクションのプロセスについて詳述する。
提示されたコードは高レベルな量子プログラミング言語であるQrispを使って書かれており、現在のほとんどの物理バックエンドやシミュレータ上で実行可能である。
その後、いくつかのシミュレータによる実験を行い、最大9つの空場を持つ4x4のSudokuインスタンスを解くことを実証した。
これは、私たちの知る限りでは、この一般化のコンパイル可能な実装の最初の例であり、量子ソフトウェアエンジニアリングにおける重要な、そしてエキサイティングな一歩である。
関連論文リスト
- How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing [0.2184775414778289]
空間複雑性の利点は,従来のストリーミングモデルよりも量子アルゴリズムの方が優れていることを示す。
これらすべての結果を包含する簡単な量子スケッチを提供し、量子スケッチをブラックボックスとして使用して、完全に古典的なアルゴリズムから導出できるようにします。
論文 参考訳（メタデータ） (2024-10-24T17:11:37Z) - Limitations of Noisy Quantum Devices in Computational and Entangling
Power [5.178527492542246]
回路深さが$O(log n)$以上のノイズ量子デバイスは、いかなる量子アルゴリズムにも利点がないことを示す。
また、ノイズ量子デバイスが1次元および2次元の量子ビット接続の下で生成できる最大エンタングルメントについても検討する。
論文 参考訳（メタデータ） (2023-06-05T12:29:55Z) - One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。
これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
論文 参考訳（メタデータ） (2023-01-05T11:05:22Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Quantum communication complexity of linear regression [0.05076419064097732]
量子コンピュータは、いくつかの基本的な線形代数問題に対する通信の観点から、証明可能かつ指数関数的なスピードアップを持つことを示す。
本稿では,量子特異値変換のための効率的な量子プロトコルを提案する。
論文 参考訳（メタデータ） (2022-10-04T13:27:01Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum State Preparation with Optimal Circuit Depth: Implementations
and Applications [10.436969366019015]
我々は、$Theta(n)$-depth回路は、$O(ndlog d)$ acillary qubitsを持つ$Theta(log(nd))で作成可能であることを示す。
我々は、ハミルトンシミュレーション、方程式の線形系解法、量子ランダムアクセスメモリの実現など、異なる量子コンピューティングタスクにおける結果の適用について論じる。
論文 参考訳（メタデータ） (2022-01-27T13:16:30Z) - Quantum walk processes in quantum devices [55.41644538483948]
グラフ上の量子ウォークを量子回路として表現する方法を研究する。
提案手法は,量子ウォークアルゴリズムを量子コンピュータ上で効率的に実装する方法である。
論文 参考訳（メタデータ） (2020-12-28T18:04:16Z) - Advanced Equivalence Checking for Quantum Circuits [4.265279817927261]
本稿では,量子回路の等価性チェックのための高度な手法を提案する。
量子回路の可逆性を利用して、複雑性を維持できることが示される。
古典的な領域とは対照的に、シミュレーションは量子回路の検証に非常に強力である。
論文 参考訳（メタデータ） (2020-04-17T18:56:23Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。