Quantum Depth in the Random Oracle Model Atul Singh Arora1Andrea Coladangelo2Matthew Coudron3 Alexandru Gheorghiu4Uttam Singh5and Hendrik Waldner6

2025-04-26 0 0 1.83MB 113 页 10玖币
侵权投诉
Quantum Depth in the Random Oracle Model
Atul Singh Arora,1Andrea Coladangelo,2Matthew Coudron,3
Alexandru Gheorghiu,4Uttam Singh,5and Hendrik Waldner6
Abstract
We give a comprehensive characterization of the computational power of shallow quantum circuits
combined with classical computation. Specifically, for classes of search problems, we show that the fol-
lowing statements hold, relative to a random oracle:
(a) BPPQNCBPP ≠BQP. This refutes Jozsa’s conjecture [Joz05] in the random oracle model. As a result,
this gives the first instantiatable separation between the classes by replacing the oracle with a
cryptographic hash function, yielding a resolution to one of Aaronson’s ten semi-grand challenges
in quantum computing [Aar05].
(b) BPPQNC /⊆QNCBPP and QNCBPP /⊆BPPQNC. This shows that there is a subtle interplay between
classical computation and shallow quantum computation. In fact, for the second separation, we
establish that, for some problems, the ability to perform adaptive measurements in a single shallow
quantum circuit, is more useful than the ability to perform polynomially many shallow quantum
circuits without adaptive measurements.
(c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier
to efficiently certify that a prover must be performing a computation of some minimum quantum
depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness
construction by Yamakawa and Zhandry [YZ22].
1Institute for Quantum Information and Matter, California Institute of Technology
Department of Computing and Mathematical Sciences, California Institute of Technology
atul.singh.arora@gmail.com
2University of California, Berkeley
Simons Institute for the Theory of Computing
andrea.coladangelo@gmail.com
3National Institute of Standards and Technology (NIST)/ Joint Center for Quantum Information and Computer Science (QuICS)
Department of Computer Science, University of Maryland
mcoudron@umd.edu
4Department of Computer Science and Engineering, Chalmers University of Technology
Institute for Theoretical Studies, ETH Z¨urich
alexandru.gheorghiu@chalmers.se
5Center for Theoretical Physics, Polish Academy of Sciences
uttam@cft.edu.pl
6Department of Computer Science, University of Maryland
Max Planck Institute for Security and Privacy
hwaldner@umd.edu
arXiv:2210.06454v1 [quant-ph] 12 Oct 2022
Contents
1 Introduction 5
1.1 MainResults ................................................. 6
1.1.1 Lower bounds on quantum depth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.2 Proofs of quantum depth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.3 Tighter bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.4 Separations between hybrid quantum depth classes . . . . . . . . . . . . . . . . . . . . . . 8
1.1.5 Summary ............................................... 9
1.2 Main technical contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Lifting Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.2 A structure theorem for [BKVV20]................................ 10
1.3 Discussion and open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Previouswork................................................. 12
2 Technical Overview 13
2.1 Bounds on quantum depth — BPPQNCBPP ⊊BQP ............................. 13
2.1.1 𝑑-CodeHashing — The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 𝑑-CodeHashing ∉QNC𝑑....................................... 14
2.1.3 𝑑-CodeHashing ∉QNCBPP
𝑑..................................... 16
2.1.4 𝑑-CodeHashing ∉BPPQNC𝑑..................................... 16
2.1.5 𝑑-CodeHashing ∉BPPQNCBPP
𝑑.................................... 18
2.1.6 Proof of quantum depth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.7 Tighter upper bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Separations of hybrid quantum depth classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1 Establishing BPPQNCO(1)⊈QNCBPP
𝑑. ............................... 20
2.2.2 Establishing QNCBPP
O(1)⊈BPPQNC𝑑................................. 21
3 Preliminaries 23
3.1 Models of Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1 The Oracle Versions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 The Random Oracle Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.1 Domain Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.2 Oracle Independent, Uniform and Non-Uniform Adversaries . . . . . . . . . . . . . . . . 27
3.3 Basic Quantum information results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
I Bounds on Quantum Depth 28
4𝑑-Recursive[P]28
4.1 Definition of P................................................ 28
4.2 Definition of 𝑑-Recursive[P] ........................................ 29
4.2.1 Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2.2 Lowerbound............................................. 29
5 Preliminaries 29
6 The 𝑑-CodeHashing Problem 31
6.1 Background — CodeHashing Problem [YZ22].............................. 31
6.2 The Problem — 𝑑-CodeHashing Problem ................................ 31
7 Lower Bounds 32
7.1 Consequence: Jozsa’s conjecture/Aaronson’s challenge . . . . . . . . . . . . . . . . . . . . . . . . 32
7.2 KnownResults ................................................ 32
7.2.1 The O2H lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
7.2.2 O2H adapted to our analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
7.2.3 Elementary results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
7.3 Warm-up — QNC𝑑exclusion........................................ 36
7.3.1 Shadow oracles for QNC𝑑hardness................................ 36
7.3.2 Properties of the shadow oracles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
7.3.3 𝑑-CodeHashing is hard for QNC𝑑................................. 38
7.4 QNCBPP
𝑑exclusion .............................................. 40
7.4.1 Shadow oracles for QCdhardness................................. 40
7.4.2 Properties of the shadow oracles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.4.3 𝑑-CodeHashing is hard for QCd.................................. 41
7.5 BPPQNC𝑑exclusion — Warm up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
7.6 Technical Results II — The sampling argument . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
7.6.1 Warm up — Sampling argument for Permutations . . . . . . . . . . . . . . . . . . . . . . 43
7.6.2 Definitions and Notation — Sampling argument for Injective Shufflers . . . . . . . . . . 45
7.6.3 Statement — Sampling argument for Injective Shufflers . . . . . . . . . . . . . . . . . . . 48
7.6.4 Properties of the 𝛿non-𝛽-uniform injective shuffler . . . . . . . . . . . . . . . . . . . . . . 49
7.7 BPPQNC𝑑exclusion .............................................. 49
7.7.1 Shadow oracles for CQdhardness................................. 49
7.7.2 Properties of the shadow oracles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
7.7.3 𝑑-CodeHashing is hard for CQd.................................. 52
7.8 BPPQNCBPP
𝑑exclusion ............................................. 57
7.8.1 Shadow oracles for CQC𝑑hardness and their properties . . . . . . . . . . . . . . . . . . . 58
7.8.2 𝑑-CodeHashing is hard for CQC𝑑................................. 59
8 Proof of Quantum Depth 63
8.1 TheDefinition ................................................ 63
8.2 Salting and oracle dependent adversaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
8.3 A Proof of 𝑑QuantumDepth ....................................... 65
9 Improved Upper Bound 65
9.1 CollisionHashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
9.2 Jozsa’s conjecture/Aaronson’s challenge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
II Separations of Hybrid Quantum Depth 68
10 BPPQNCO(1)⊈QNCBPP
𝑑68
10.1 Offline Soundness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
10.2 The 𝑑-Ser[P]Problem............................................ 69
10.3Lower-bounds................................................. 69
10.3.1 Exclusion from QNC𝑑........................................ 70
10.3.2 Exclusion from QNCBPP
𝑑...................................... 71
10.4Upper-bounds................................................. 73
10.5Consequences................................................. 74
11 QNCBPP
O(1)⊈BPPQNC𝑑74
11.1TheProblem ................................................. 74
11.2Consequences................................................. 75
11.3 The compressed oracle technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
11.3.1 An informal overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
11.3.2 A formal introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
11.4 𝑑-hCollisionHashing ∉BPPQNC𝑑....................................... 79
11.4.1 A technical lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
11.4.2 The structure of strategies that produce valid equations . . . . . . . . . . . . . . . . . . . 88
11.4.3 The structure of successful CQdstrategies . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
11.4.4 Putting things together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
A The O2H lemma 105
A.1 Proof of Lemma 41 ..............................................105
A.2 Proof of Lemma 42 ..............................................106
3
B Misc calculations 106
B.1 Proof of Claim 56 — Deferred steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
B.1.1 Proof of Equation (6)........................................106
B.2 Proof of Claim 106 ..............................................107
C Sampling argument for Permutations 107
C.1 Sampling argument for Uniformly Distributed Permutations . . . . . . . . . . . . . . . . . . . . . 107
C.1.1 Convex Combination of Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
C.1.2 The “parts” notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
C.1.3 𝛿non-uniform distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
C.1.4 Advice on uniform yields 𝛿non-uniform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
C.1.5 Iterating advice and conditioning on uniform distributions — 𝛿non-𝛽-uniform distri-
butions ................................................110
C.2 Technical results for 𝛿non-uniform distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4
1 Introduction
High depth circuits are believed to be strictly more powerful than low depth circuits, in the sense that having
deeper circuits allows one to solve a larger set of problems. Indeed, this is a well established fact for both
classical and quantum circuits of depth sub-logarithmic in the size of the input [FSS84;Has86;BGK18;
WKST19]. However, for circuits of (poly)logarithmic depth and general polynomial depth, proving any sort
of unconditional separation is challenging [RR94]. In fact, there is not even an unconditional proof that the
set of problems that can be solved by polylog-depth classical circuits, NC, is a strict subset of the set of
problems solvable by poly-depth classical circuits, P(or BPP when allowing for randomness). The same is
believed to be the case for the quantum analogues of these classes, QNC and BQP, respectively. Nevertheless,
the strict containments NC ⊊Pand QNC ⊊BQP are known to hold in the oracle setting and, in particular,
relative to a random oracle [Mil92].1This is a strong indication that there are problems in P(BQP) which
cannot be parallelized so as to be solvable in NC (QNC). Under the random oracle heuristic, by replacing
the random oracle with a cryptographic hash function, one can even provide concrete instantiations of such
problems. A further indication of the separation between low and high depth computations is provided
by certain inherently sequential cryptographic constructions such as time-lock puzzles and verifiable delay
functions [RSW96;BBBF18].
The study of circuit depth can also yield insights into the subtle relationship between quantum and
classical computation by considering hybrid circuit models that combine quantum and classical computa-
tion [CCL20;CM20;AGS22;HG22]. In this setting, one can ask the question: how powerful are poly-depth
classical circuits, when augmented with polylog-depth quantum circuits? Could it be the case that interspers-
ing BPP with QNC computations captures the full power of BQP computations? Jozsa famously conjectured
that the answer is yes [Joz05]. Indeed, there is some evidence to support this conjecture, as the quantum
Fourier transform, a central building block for many quantum algorithms, was shown to be implement-
able with log-depth quantum circuits [CW00]. This also implies that Shor’s algorithm can be performed
by a BPPQNC machine, a polynomial-time classical computer having the ability to invoke a (poly)log depth
quantum computer.2Moreover, in the oracle setting, a number of problems yielding exponential separations
between quantum and classical computation require only constant quantum-depth to solve, providing further
support for Jozsa’s conjecture [Sim97;Aar10;AA15].
Despite the evidence in support of Jozsa’s conjecture, it was recently shown that, in the oracle setting,
the conjecture is false [CCL20;CM20]. Specifically, the results of [CCL20] (hereafter referred to as CCL)
and [CM20] (hereafter referred to as CM) considered two ways of interspersing poly-depth classical computa-
tion with 𝑑-depth quantum computation. The first is BPPQNCd, denoting problems solvable by a BPP machine
that can invoke 𝑑-depth quantum circuits (whose outputs are measured in the computational basis). The
second, QNCdBPP, denotes problems solvable by a 𝑑-depth quantum circuit that can invoke a BPP machine
at each layer in the computation.3Later, borrowing terminology from [CCL20;AGS22], we will refer to the
former circuit model as CQdand the latter as QCd. However, for the purposes of this introduction, we will
stick to the more familiar notation using complexity classes. Intuitively, BPPQNCdcaptures the setting of a
classical computer that can invoke a 𝑑-depth quantum computater several times. Examples of this include
quantum machine learning algorithms such as VQE or QAOA [PMS+14;FGG14], though as mentioned,
Shor’s algorithm is also of this type. On the other hand, QNCdBPP captures a 𝑑-depth measurement-based
quantum computation [RB01;BBD+09], where intermediate measurements are performed after each layer
in the quantum computation. The outcomes of those measurements are processed by a poly-depth classical
computation and the results are “fed” into the next quantum layer. CCL and CM showed that there exists
an oracle relative to which BPPQNCd∪QNCdBPP ⊊BQP, for any 𝑑=polylog(𝑛), with 𝑛denoting the size of
the input. Notably, each work considered a different oracle for showing the separation. For CM, the oracle
is the same one as for Childs’ glued trees problem [CCD+03]. For CCL, the oracle is a modified version
of the oracle used for Simon’s problem [Sim97], where the modification involves performing a sequence of
permutations, allowing them to enforce high quantum depth.
CCL and CM were the first results to provide a convincing counterpoint to Jozsa’s conjecture. However,
the main drawback of the CCL and CM results is that they are relative to oracles that are highly structured
and it is unclear if they can be explicitly instantiated based on some cryptographic assumption. Indeed,
1Technically [Mil92] only shows the strict containment NC ⊊P, relative to a random oracle. However, the quantum version
QNC ⊊BQP can also be shown as a straightforward extension of that result.
2Note that here and throughout the paper, the QNC oracle can output a string, unlike a decision oracle which outputs a bit.
3Note that the BPP oracle is not invoked coherently. Instead, it is invoked on outcomes resulting from intermediate meas-
urements performed in the layers of the QNCdcircuit.
5
摘要：

QuantumDepthintheRandomOracleModelAtulSinghArora,1AndreaColadangelo,2MatthewCoudron,3AlexandruGheorghiu,4UttamSingh,5andHendrikWaldner6AbstractWegiveacomprehensivecharacterizationofthecomputationalpowerofshallowquantumcircuitscombinedwithclassicalcomputation.Speci cally,forclassesofsearchproblems,we...

展开>> 收起<<
Quantum Depth in the Random Oracle Model Atul Singh Arora1Andrea Coladangelo2Matthew Coudron3 Alexandru Gheorghiu4Uttam Singh5and Hendrik Waldner6.pdf

共113页,预览5页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：113 页 大小：1.83MB 格式：PDF 时间：2025-04-26

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 113
评分 收藏
分享
立即下载
客服
关注