論文の概要: Two exact quantum queries use at most six variables
- arxiv url: http://arxiv.org/abs/2610.34079v1
- Date: Sun, 25 Oct 2026 05:38:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-29 19:00:17.365629
- Title: Two exact quantum queries use at most six variables
- Title（参考訳）: 最大6変数で使用する2つの正確な量子クェリ
- Abstract要約: 我々は、全てのブール関数が、少なくとも2つの量子クエリと正確に計算可能であるという直接的な解析的証明を、少なくとも6つの入力変数に依存する。
以前の導出はブール関数の少なくとも4つの変数の数値的な分類に依存していた。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give a direct analytic proof that every total Boolean function computable exactly with at most two quantum queries depends on at most six input variables. This bound is sharp. A previous derivation relied on a numerical classification of Boolean functions on at most four variables; to the best of our knowledge, ours is the first unconditional proof. The main difficulty beyond the one-query case is that query-path vectors need not be mutually orthogonal, so interference prevents the scalar weight-counting argument from applying. We overcome this difficulty by establishing a rigid support-and-branch decomposition: after the coordinates in the first-query support are fixed, the second query induces a family of exact one-query branches. This structural description may be of independent interest.
- Abstract（参考訳）: 我々は、全てのブール関数が、少なくとも2つの量子クエリと正確に計算可能であるという直接的な解析的証明を、少なくとも6つの入力変数に依存する。
この境界は鋭い。
以前の導出はブール関数の少なくとも4つの変数の数値的な分類に依存していた。
クエリパスベクトルは相互直交する必要はないため、干渉によってスカラーウェイトカウントの議論が適用されなくなる。
第1クエリのサポートの座標が固定された後、第2クエリは、正確な1クエリブランチのファミリーを誘導する。
この構造的記述は独立した関心事であるかもしれない。
関連論文リスト
- Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach [19.400202883397537]
定量化ブール式(QBF)の妥当性を検討する。
抽出可能なクラスに到達する前に削除しなければならない節の変数数という新しいパラメータを提案する。
CCバックドアが$k$であるなら、FPT時間でQBFを解くことに興味があります。
論文 参考訳（メタデータ） (2026-05-12T13:00:55Z) - Variational Joint Magnetometry and Gradiometry on Dipolar Spin Chains [14.720429715932829]
本稿では,det(F)を目的とし,ハードウェアを駆動する層状双極回路をアンザッツとする変分フレームワークを提案する。
両方のエンコーディングジェネレータは計算ベースで対角的であり、量子フィッシャー情報ベンチマークの探索を確率-複雑な最適化に還元する。
論文 参考訳（メタデータ） (2026-05-05T15:59:22Z) - Tight Quantum Lower Bound for k-Distinctness [52.10197476419622]
我々は新しい量子クエリローバウンドフレームワークを導入する。
このフレームワークが入力文字列の等しい要素を見つけるという問題に対してどのように振る舞うかを示す。
特に、k-distinctness問題に対する最初の厳密な量子クエリローバウンドを証明することによって、そのパワーを実証する。
論文 参考訳（メタデータ） (2026-04-06T19:52:58Z) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - On Kirkwood--Dirac quasiprobabilities and unravelings of quantum channel assigned to a tight frame [0.0]
与えられた強フレームのベクトルを使って主クラウス作用素を構築すると、興味深い性質を持つ準確率が生成される。
固有値の位置を特徴付けるための新しい不等式が導出される。
提示された不等式の効用は、次元2における対称的な情報的完備な測定で例示される。
論文 参考訳（メタデータ） (2023-04-27T09:11:11Z) - Polynomial representation of general partial Boolean functions with a
single quantum query [0.0]
1992年初頭、Deutsch-Jozsaアルゴリズムは1つの量子クエリを持つ対称部分ブール関数を計算した。
本稿では,3つの新たな結果の証明と発見を行う。
論文 参考訳（メタデータ） (2021-12-23T08:45:06Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳（メタデータ） (2020-11-24T18:44:57Z) - A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
より弱い仮定として, 2$-adjacency faithfulness を提案します。
より弱い仮定の下で適用可能な因果発見のための音方向規則を提案する。
論文 参考訳（メタデータ） (2020-10-27T13:04:08Z) - Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
確率感性決定図は、解離ゲートの入力が確率値によってアノテートされる論理回路である。
我々は、局所確率を質量関数のクレーダル集合に置き換えることができる確率の一般化である、クレーダル感性決定図を開発する。
まず,ノイズの多い7セグメント表示画像に基づく簡単なアプリケーションについて検討する。
論文 参考訳（メタデータ） (2020-08-19T16:04:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。