Fugu-MT 論文翻訳(概要): Nearly optimal quantum circuits for Boolean oracles

論文の概要: Nearly optimal quantum circuits for Boolean oracles

arxiv url: http://arxiv.org/abs/2607.28402v1
Date: Thu, 30 Jul 2026 15:51:53 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-31 21:37:00.644957
Title: Nearly optimal quantum circuits for Boolean oracles
Title（参考訳）: ブールオラクルのほぼ最適量子回路
Abstract要約: 3種類のブール関数の量子オラクルに対して,回路サイズ,回路深さ,アンシラ数間のほぼ最適なトレードオフを提案する。これらの結果をQROM実装や量子アルゴリズム設計手順などの量子回路に組み込む必要があることを願っている。
参考スコア（独自算出の注目度）: 0.3580891736370874
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Quantum oracle of Boolean functions is one of the central bridges between classical and quantum algorithms, but the study focusing at quantum circuit optimization of such oracle is yet closed. In this paper, we propose nearly optimal tradeoffs among circuit size, circuit depth and ancilla count, for quantum oracles of three kinds of Boolean functions: general total Boolean functions with output size $b$: with $1\le m\leΘ\left(\frac{2^n}{n}\right)$ ancilla, size $\mathcal{O}\left(\frac{b2^n}{\log(n+m)}\right)$, depth $\mathcal{O}\left(\frac{b2^n}{n+m}\right)$; partial Boolean functions of effective support size $d$ and output size $b$: with $Θ\left(\log d\right)\le m\le Θ\left(d\right)$ ancilla, size $\mathcal{O}\left(n\log d+bd\right)$, depth $\mathcal{O}\left(\frac{n\log n\log d}{n+m}+\log n+\frac{d(\log d+b\log m)}{m}\right)$; sparse Boolean functions of true input size $d$: with $Θ\left(\log n+\log d\right)\le m\leΘ\left(\frac{nd}{\log d}\right)$ ancilla, size $\mathcal{O}\left(n^2\log d+\frac{nd}{\log(\log d+m/n)}\right)$, depth $\mathcal{O}\left(\frac{n^2\log n\log d}{n+m}+\log n+\frac{nd}{m}\right)$. All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.
Abstract（参考訳）: ブール関数の量子オラクルは古典的アルゴリズムと量子的アルゴリズムの間の中心的なブリッジの1つであるが、そのようなオラクルの量子回路最適化に焦点をあてる研究はまだ閉ざされていない。本稿では, 回路サイズ, 回路深さ, アンシラ数の間のほぼ最適なトレードオフについて, 3種類のブール関数の量子オラクルについて提案する: 総総総ブール関数$b$:$ $1\le m\le \left(\frac{2^n}{n}\right)$ ancilla, size $\mathcal{O}\left(\frac{b2^n}{\log(n+m)}\right)$, depth $\mathcal{O}\left(\frac{b2^n}{n+m}\right)$; partial Boolean function of effective support size$d$: with $\left(\log d\right)\le m\le \le \left(\frac{2^n}{n}\right)$ ancilla, size $\mathcal{O}\left(\frac{b2^n}{n+m\right)$; depth $\mathcal{O}\left(\frac{b2^n}{n+m\right)$; $d$:$\left(\frac{n+n+m\right)$; 有効サポート関数$d$と出力サイズ$d$d$の半ブール関数。すべてのサイズと深さ境界は、対応するアシラ数領域の対数係数まで漸近的に最適である。これらの結果は、QROM実装や量子アルゴリズム設計など、古典的な手順を量子回路に組み込む必要があるシナリオに応用できることを期待している。

関連論文リスト

Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文参考訳（メタデータ） (2026-07-08T17:49:40Z)
Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
論文参考訳（メタデータ） (2026-01-07T22:07:44Z)
Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
論文参考訳（メタデータ） (2025-09-25T07:39:25Z)
Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
論文参考訳（メタデータ） (2025-08-28T17:04:18Z)
Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
我々は、$s$非ゼロ振幅を持つ$n$量子ビットスパース量子状態の準備を検討し、2つのアルゴリズムを提案する。最初のアルゴリズムは$O(ns/log n + n)$ gatesを使用し、以前のメソッドを$O(log n)$で改善する。 2番目のアルゴリズムは、短いハミルトニアンパスを示す二進弦向けに調整されている。
論文参考訳（メタデータ） (2024-04-08T02:13:40Z)
Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
論文参考訳（メタデータ） (2024-02-14T13:44:16Z)
Polylogarithmic-depth controlled-NOT gates without ancilla qubits [0.0]
制御された演算は量子アルゴリズムの基本的な構成要素である。 n$-control-NOT ゲートを任意の単一量子ビットと CNOT ゲートに分解することは重要な作業である。
論文参考訳（メタデータ） (2023-12-20T17:23:11Z)
Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates [40.56175933029223]
本稿では,一様制御ゲート実装のための2種類の定数深度構造を提案する。我々は、リードオンリーおよびリードライトメモリデバイスの量子対数に対して、一定の深さの回路を得る。
論文参考訳（メタデータ） (2023-08-16T17:54:56Z)
Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文参考訳（メタデータ） (2023-03-03T18:23:20Z)
Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy [0.0]
しきい値回路$C$ of size $s$, depth $d$, energy $e$ and weight $w$ satisfies $log (rk(M_C)) le ed。離散化ReLE回路や復号化シグモノイド回路などの他のニューラルネットワークのモデルに対しては、同様の不等式が離散化回路の$C$についても成り立つことを証明している。
論文参考訳（メタデータ） (2021-07-01T05:37:53Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)
Revisiting EXTRA for Smooth Distributed Optimization [70.65867695317633]
改良された$Oleft(left(fracLmu+frac11-sigma_2(W)right)logfrac1epsilon (1-sigma_2(W))right)$。高速化されたEXTRAの通信複雑性は、$left(logfracLmu (1-sigma_2(W))right)$と$left(logfrac1epsilon (1。
論文参考訳（メタデータ） (2020-02-24T08:07:08Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。