Explicit Separations for One-Query Unitary Synthesis Fangqi Dong Princeton
Alex Lombardi Princeton
Fermi Ma NYU
July 28, 2026
arXiv:2607.26478v1 [quant-ph] 29 Jul 2026
Abstract The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every 𝑛qubit unitary 𝑈 is computable by poly(𝑛)-size quantum circuits relative to some classical oracle 𝑓 = 𝑓𝑈 depending on 𝑈 . Recently, it was proved (Lombardi-Ma-Wright, STOC 2024) that Haar-random unitaries cannot be efficiently synthesized by algorithms that make one query (or poly(𝑛) parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of different variants of unitary synthesis. Our results include the following: • One-query vs. two-query unitary synthesis: we prove one-query lower bounds for synthesizing random permutation unitaries 𝑃 |𝑥⟩ = |𝜋(𝑥)⟩, as well as random alternating-basis phase unitaries 𝐹2 · 𝐻 ⊗𝑛 · 𝐹1 . This gives one-query lower bounds for “explicit” families of unitaries that have efficient (even two-query) unitary synthesis algorithms. • Upper bound for complex phase unitaries: we also consider complex phase unitaries |𝑥⟩ ↦→ 𝛼𝑥 |𝑥⟩, which (similarly to permutations) have a clean two-query synthesis algorithm with no obvious one-query algorithm. However, in this case, we prove an upper bound: there are one-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our one-query lower bounds, we depart from prior work by introducing and analyzing two new cryptographic games – the oracle state search game and the oracle Choi state game – that serve as sources of hardness for unitary synthesis. As compared to the pseudorandomness-based approach of prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not “fully random.” As a bonus, we obtain a simplification of the state-of-the-art lower bound for general-purpose unitary synthesis. Finally, we also use the oracle state search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between one-query unitary synthesis and quantum programs.
Contents 1 Introduction 1.1 This work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 The oracle state search and Choi state games . . . . . . . . . . . . . . . . . . . . . . 1.4 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 2 3 4 6
2 Technical Overview 6 2.1 Recap of LMW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 What goes wrong for other unitaries? . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 From decision to search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4 Search game hardness beyond the random case . . . . . . . . . . . . . . . . . . . . . 11 3 Preliminaries 3.1 The unitary synthesis problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 One-query normal form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 The weight vector decomposition relative to an input distribution . . . . . . . . . . . 3.4 Useful concentration inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13 13 16 16 17
4 The Oracle State Search and Choi State Games 4.1 Relationship to Unitary Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The Oracle Choi State Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Relationship to Quantum Cryptography . . . . . . . . . . . . . . . . . . . . . . . . .
18 19 19 22
5 Main Theorems
23
6 A Generic Search Reduction 24 6.1 Generic spectral relaxation under identical marginals . . . . . . . . . . . . . . . . . . 24 6.2 Description of 𝑀𝑅 for subspace-uniform state families . . . . . . . . . . . . . . . . . 25 7 One-query lower bound for permutation unitaries 7.1 A one-query distinguishing attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Search formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Rewriting 𝑀𝜋 as a combinatorial matrix sum . . . . . . . . . . . . . . . . . . . . . . 7.4 Parameter estimates for the combinatorial matrix sum . . . . . . . . . . . . . . . . . 7.5 Upper bounding the search game winning probability . . . . . . . . . . . . . . . . . . 7.6 One-query lower bound with classical advice . . . . . . . . . . . . . . . . . . . . . . .
27 27 29 30 31 32 32
8 One-query lower bound for 𝐹2 𝐻𝐹1 8.1 Search formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Conditioning on 𝑓1 : a matrix Rademacher series . . . . . . . . . . . . . . . . . . . . 8.3 Bounding E𝑓1 ‖E𝑓2 [𝑀𝑅 𝑀𝑅† ]‖ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Bounding E𝑓1 ‖E𝑓2 [𝑀𝑅† 𝑀𝑅 ]‖ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5 Final bound on the search success probability . . . . . . . . . . . . . . . . . . . . . . 8.6 One-query lower bound with classical advice . . . . . . . . . . . . . . . . . . . . . . . 8.7 One-query lower bound for 𝐹𝑡 𝐻𝐹𝑡−1 𝐻 · · · 𝐹2 𝐻𝐹1 . . . . . . . . . . . . . . . . . . . .
33 33 34 34 36 37 37 38
9 One-query synthesis for phase unitaries with constant correctness 9.1 Phase unitary setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 The special case 𝑞 = 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3 General 𝑞 via rounding to the nearest quadrant . . . . . . . . . . . . . . . . . . . . .
39 39 40 41
10 Quantum advice lower bound for 𝐹 𝐻 |𝑘⟩ 10.1 Search formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2 Reduction to alternating measurement game . . . . . . . . . . . . . . . . . . . . . . . 10.3 Upper-bounding the alternating measurement game . . . . . . . . . . . . . . . . . . 10.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.5 Matching Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42 43 44 45 48 49
References
49
A Simple search game upper bounds 51 A.1 Random binary phase states . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 A.2 Haar-random unitaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 B Unitary search game is hardest on Haar random unitaries 55 B.1 (𝑀, 𝜀)-hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 B.2 (𝑀, 𝜀, 𝛿)-hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 C Hardness of the oracle Choi state game C.1 Theorem statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.2 General setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.3 Permutation lower bound in the oracle Choi state game . . . . . . . . . . . . . . . . C.4 𝐹2 𝑈0 𝐹1 lower bound in the oracle Choi state game . . . . . . . . . . . . . . . . . . .
57 57 57 58 61
1
Introduction
The unitary synthesis problem, introduced by Aaronson and Kuperberg in 2007 [AK07, Aar16], asks whether every 𝑛-qubit unitary 𝑈 is computable by poly(𝑛)-size quantum circuits relative to some classical oracle 𝑓 = 𝑓𝑈 depending on 𝑈 . Informally, this question asks: does the task of implementing an arbitrary unitary efficiently reduce to that of implementing Boolean functions? A negative answer to this question, as conjectured by [Aar16, LMW24], would have far-reaching implications for the fields of unitary complexity theory [BEM+ 26] — necessitating the study of unitary complexity classes with no correspondence to classical complexity or computability theory — and quantum cryptography [Kre21, LMW24], raising the possibility of computational quantum cryptography that does not rely on separating any traditional complexity classes. Despite the question’s importance, progress on resolving it has been relatively limited [AK07, Aar16, Ros21, INN+ 22, Ros24, LMW24], with two main results to date: • State synthesis, or the task of constructing an arbitrary 𝑛-qubit quantum state |𝜓⟩, is easy relative to a ( |𝜓⟩-dependent) classical oracle [Aar16, INN+ 22, Ros24]; in fact, there are algorithms making only a single query to a classical oracle [Ros24]. • Full-fledged unitary synthesis is impossible for algorithms that make a single query to a classical oracle, provided that the input length of the query is 𝑜(2𝑛 ) [AK07, LMW24]. While lower bounds against single-query algorithms may appear limited at first glance, the freedom to query an arbitrary classical oracle makes this class of algorithms very powerful. Aside from solving state synthesis, they also easily simulate algorithms making a polynomial number of parallel quantum queries to any classical oracle, including on entangled inputs [Yue22, LMW24]. Which families of unitaries are subject to the [LMW24] one-query lower bound? Roughly speaking, the answer to keep in mind is “Haar-random unitaries,” or at least “unitaries with very large (2𝜔(𝑛) ) randomness complexity.”1 These unitaries are so (apparently) hard to compute that synthesizing them could require as many as 2𝑛/2 sequential classical oracle queries [Ros21]. In contrast, in this work, we investigate the following question. Can we prove lower bounds for synthesizing explicit families of unitaries? By “explicit”, we mean families of unitaries that have poly(𝑛)-query synthesis algorithms, so they are explicit (in the usual sense) relative to some classical oracle.2 Proving such lower bounds would separate efficient unitary synthesis from 1-query unitary synthesis, and therefore demonstrate the power of adaptivity in unitary synthesis algorithms. More speculatively, new one-query lower bounds might be useful for resolving the full unitary synthesis question. The intuition is as follows. The [LMW24] bound says that a Haar-random unitary cannot be synthesized in one query. But can a Haar-random unitary be synthesized in, say, two queries? A natural idea is to try to invoke the [LMW24] one-query lower bound twice. The problem, however, is that after the algorithm has performed one query, the operation it must implement on the second query may be “less random” than a fully Haar-random unitary, since 𝑛
1
Technically, [LMW24] study “reflections about a highly random subspace 𝑆 ⊂ C2 ,” where 𝑆 = Span{ |𝜓1 ⟩ , . . . , |𝜓𝐾 ⟩} for i.i.d. states |𝜓1 ⟩ , . . . |𝜓𝐾 ⟩ that are either Haar-random or uniform binary phase states. The former setting also rules out synthesizing Haar-random unitaries. 2 Of course, fully explicit unitaries have poly(𝑛)-size quantum circuits, i.e., trivial 0-query synthesis algorithms.
1
the algorithm has already made progress toward the target Haar-random unitary. Thus, it seems plausible that proving lower bounds against “less-than-Haar-random” unitaries could be a stepping stone toward an adaptive query lower bound.
1.1
This work
In this work, we answer this question by studying three natural explicit families of unitaries described below. • Permutation unitaries: for any permutation 𝜋 of {0, 1}𝑛 , we consider the unitary 𝑃 = 𝑃𝜋 described by 𝑃 |𝑥⟩ = |𝜋(𝑥)⟩ that applies the permutation 𝜋 to the standard basis. • Alternating-basis binary phase unitaries: for boolean functions 𝑓1 , . . . , 𝑓𝑡 : {0, 1}𝑛 → {0, 1}, we study unitaries of the form 𝐹𝑡 · 𝐻 ⊗𝑛 · . . . · 𝐹2 · 𝐻 ⊗𝑛 · 𝐹1 , where 𝐹𝑖 |𝑥⟩ = (−1)𝑓𝑖 (𝑥) |𝑥⟩ and 𝐻 ⊗𝑛 is the 𝑛-qubit Hadamard transform. • Complex phase unitaries: for any function 𝛼 : {0, 1}𝑛 → 𝑆 1 ⊂ C mapping strings to unit-norm complex numbers, we consider the unitary described by 𝐹 |𝑥⟩ = 𝛼(𝑥) |𝑥⟩ . It is easy to see that all of these unitary families are explicit. The second family has a trivial 𝑡-query synthesis algorithm, as querying a binary phase oracle is algorithmically equivalent to querying a Boolean function. The first and third families both have two-query algorithms. For permutations, compute 𝜋
𝜋 −1
SWAP
|𝑥⟩ |0⟩ ↦→ |𝑥⟩ |𝜋(𝑥)⟩ ↦→ |0⟩ |𝜋(𝑥)⟩ ↦→
|𝜋(𝑥)⟩ |0⟩ ,
where the first step queries 𝜋 (XORing the answer onto an auxiliary register initialized to |0⟩) and the second step queries 𝜋 −1 to erase the original input. For complex phase unitaries, compute 𝜃
𝜃
ctrl-𝑅
1:𝑛 1:𝑛 𝑖·𝜃(𝑥)1:𝑛 |𝑥⟩ |0⟩ ↦→ |𝑥⟩ |𝜃(𝑥)1...𝑛 ⟩ ↦→ 𝑒𝑖·𝜃(𝑥)1:𝑛 |𝑥⟩ |𝜃(𝑥)1:𝑛 ⟩ ↦→ 𝑒 |𝑥⟩ |0⟩ ≈ 𝛼(𝑥) |𝑥⟩ |0⟩ ,
where 𝜃(𝑥) ∈ [0, 2𝜋) is the angle satisfying 𝑒𝑖·𝜃(𝑥) = 𝛼(𝑥) and 𝜃(𝑥)1:𝑛 denotes its 𝑛-bit truncation. These are both two-query algorithms by the previously mentioned observation about simulating parallel queries. We ask whether there are one-query synthesis algorithms for all three of these unitary families. Indeed, all three variants capture natural questions about the nature of quantum query algorithms: • For 𝐹2 𝐻𝐹1 , this is asking whether inserting a Hadamard change of basis between two phase queries makes them “inherently sequential.” • For 𝑃 as well as complex phase 𝐹 , this is asking whether the sequential process of “computethen-uncompute” can be shortcut through the use of a cleverly chosen classical oracle. 2
• Finally, for complex phase 𝐹 , this relates to another question about the [LMW24] technique for one-query lower bounds: their approach necessarily rules out one-query synthesis algorithms relative to arbitrary phase oracles, and thus intrinsically cannot separate complex phase unitaries from binary phase unitaries. Can they be separated in some other way?
1.2
Our results
We prove several results on the synthesis of these three unitary families. For our main results, we prove one-query lower bounds for synthesizing permutation unitaries as well as unitaries of the form 𝐹2 𝐻𝐹1 . Theorem 1.1 (informal, see Theorem 5.1). There is no efficient one-query unitary synthesis algorithm for random 𝑛-qubit permutation unitaries. Theorem 1.2 (informal, see Theorem 5.2). There is no efficient one-query unitary synthesis algorithm for unitaries of the form 𝐹2 𝐻𝐹1 for random 𝐹1 , 𝐹2 . These results both demonstrate separations between the power of one- and two-query unitary synthesis algorithms. Moreover, Theorem 1.2 easily extends to one-query lower bounds for unitaries 𝐹𝑡 𝐻 . . . 𝐹2 𝐻𝐹1 with more alternations. Theorem 1.3 (informal, see Corollary 5.3). There is no efficient one-query unitary synthesis algorithm for unitaries of the form 𝐹𝑡 𝐻 . . . 𝐹2 𝐻𝐹1 for random 𝐹1 , 𝐹2 , . . . , 𝐹𝑡 . We remark that in general, it is natural to ask whether more 𝐹 𝐻 alternations make the unitary harder to synthesize. Most aggressively, one could ask: Question 1.4. Does synthesizing 𝐹𝑡 𝐻 . . . 𝐹2 𝐻𝐹1 require 𝑡 sequential queries? We prove this for 𝑡 = 2. A positive answer to this question for all 𝑡 = poly(𝑛) would prove the unitary synthesis conjecture. Extension to other interleaving unitaries. In Appendix C, we extend Theorem 1.2 to the case of alternations 𝐹2 𝑈0 𝐹1 for a fixed unitary 𝑈0 (Theorem C.2). Of course, if 𝑈0 is close to the identity then such unitaries can be approximately synthesized in one query. On the other hand, we prove that if all of the entries of 𝑈0 are small (for example, if 𝑈0 is a tensor power of any one-qubit unitary with all four entries bounded away from 0), such unitaries cannot be synthesized in one query. We refer the reader to Appendix C for more details. Upper bound for phase unitaries. On the other hand, we give a constant-factor unitary synthesis approximation algorithm in the case of (non-Boolean) phase unitaries! Theorem 1.5 (informal, see Theorem 5.5). There is a Ω(1)-approximate (in diamond distance, see Definition 3.4) one-query unitary synthesis algorithm for arbitrary diagonal phase unitaries. Since existing lower bound techniques also rule out approximation algorithms, this explains why they do not apply to complex phase unitaries! In addition, through the use of a simple composition theorem, we conclude that to some level of approximation, unitary synthesis algorithms with binary and arbitrary complex phase oracles have the same computational power. 3
Corollary 1.6. Any family of unitaries with a (3/4+𝜀) correct 1-query unitary synthesis algorithm relative to the class of complex phase unitaries also has an Ω(𝜀2 )-correct 1-query unitary synthesis algorithm relative to binary phase unitaries (or Boolean functions). We next describe important conceptual tools used to prove our results — the oracle state search game and its cousin, the oracle Choi state game — which allows us to re-state the above theorems as well as discuss two additional results.
1.3
The oracle state search and Choi state games
The existing one-query unitary synthesis lower bound of [LMW24] can be thought of as deriving unitary synthesis lower bounds for a unitary 𝑈 from upper bounds on the maximum win probability of a distinguishing task. Letting [𝐾] ⊂ [𝑁 ] denote a subset, the task is to distinguish the following two mixed states: 1. 𝐾1
∑︀
𝑘∈[𝐾] |𝜓𝑘 ⟩⟨𝜓𝑘 | for |𝜓𝑘 ⟩ = 𝑈
† |𝑘⟩ and [𝐾] ⊂ [𝑁 ] some fixed subset,
2. the maximally mixed 𝑛-qubit state. Just as in the unitary synthesis problem, the algorithm (or “adversary”) is allowed to make a single function query. Thus, [LMW24] derive unitary synthesis lower bounds from pseudorandomness results. Unfortunately, this approach seems to fail (or at least run into serious difficulties) for all of the questions addressed in this paper! We refer the reader to the technical overview (Section 2.2) for more details, but the upshot is that state pseudorandomness does not seem to naturally capture the hardness of these unitary synthesis tasks. Instead, we introduce a new source of “cryptographic hardness” to prove our results, called the “oracle state search game.” Definition 1.7 (see Definition 4.1). For a collection of states { |𝜓𝑘 ⟩}𝑘∈[𝐾] , the oracle state search game is a challenger-adversary game in which: • The challenger samples a classical string 𝑘 ← [𝐾] and sends |𝜓𝑘 ⟩ to the adversary. • The adversary returns a string 𝑘 ′ to the challenger and wins if 𝑘 ′ = 𝑘. For all of the main results/settings of this paper, the states |𝜓𝑘 ⟩ are mutually orthogonal, so an all-powerful adversary can in fact win this game with probability 1. We prove our one-query unitary synthesis lower bounds by proving that for appropriate families of |𝜓𝑘 ⟩, one-query adversaries can only win the state search game with negligible probability. This can be seen as proving the security of a “single-copy” variant of a one-way state generator [MY22] against one-query adversaries; the variant we consider is powerful enough to imply quantum bit commitment [BCQ23], thus having similar implications for quantum cryptography as the pseudorandomness notion from [LMW24]. While most of our results are derived using the oracle state search game, we also introduce an even harder-to-win cryptographic game whose hardness still rules out unitary synthesis: the oracle Choi state game. Definition 1.8 (see Definition 4.7). For a unitary 𝑈 , the oracle Choi state game is a challengeradversary game in which: 4
• The challenger prepares the state |𝜓⟩𝑈 † = √1𝑁 to the adversary.
∑︀
𝑥∈[𝑁 ] 𝑈
† |𝑥⟩ ⊗ |𝑥⟩ and sends the first register
• The adversary performs some quantum channel and returns the same register back to the challener. • To decide if the adversary wins, the challenger measures whether the two-register state is the ∑︀ EPR state √1𝑁 𝑥∈[𝑁 ] |𝑥⟩ ⊗ |𝑥⟩. We consider the Choi state game to be the weakest natural formulation of average-case unitary synthesis hardness and observe (see Section 4.2) that (1) it is at least as hard as the search game using states |𝜓𝑘 ⟩ = 𝑈 |𝑘⟩ and (2) its hardness still suffices to construct quantum bit commitments. While almost all of our results are proved using the search game, we prove Theorem C.2 using the Choi state game, provide some alternative proofs of our main results using the Choi state game in Appendix C, and more generally believe the game to be worthy of future study. 1.3.1
Search game formulations of our results
Our main one-query lower bounds follow from bounds on the probability of winning the oracle state search game. Theorem 1.9 (see Theorem 5.1). Let 𝑃 be the permutation unitary associated with a uniformly random permutation 𝜋 on {0, 1}𝑛 , and consider the search game for the state family {𝑃 𝐻 |𝑘⟩}𝑘∈[𝐾]∖{0} . Then every one-query adversary with workspace dimension 𝑀 satisfies log2 𝑀 log2 𝐾 E𝜋 Win(𝒜 | 𝜋) = 𝑂 𝐾 (︃
[︀
]︀
)︃
.
Theorem 1.10 (see Theorem 5.2). Let 𝑓1 , 𝑓2 : {0, 1}𝑛 → {0, 1} be uniformly random Boolean ∑︀ functions, and let 𝐹𝑗 = 𝑥 (−1)𝑓𝑗 (𝑥) |𝑥⟩⟨𝑥| for 𝑗 ∈ {1, 2}. For the search game on the family {𝐹2 𝐻𝐹1 𝐻 |𝑘⟩}𝑘∈[𝐾] , every one-query adversary with workspace dimension 𝑀 satisfies E𝑓1 ,𝑓2 Win(𝒜 | 𝑓1 , 𝑓2 ) = 𝑂 [︀
]︀
(︂
log 𝑀 · log(𝑀 𝑁 ) . 𝐾 )︂
Interestingly, in the case of permutations, we show that the same state family fails to be pseudorandom in the sense of [LMW24], demonstrating the utility of the search game: Theorem 1.11 (see Theorem 5.4). There exists a one-query adversary 𝒜 such that for every permutation unitary 𝑃 there is a classical oracle 𝑓𝜋 for which 𝒜𝑓𝜋 distinguishes the ensemble {𝑃 𝐻 |𝑘⟩}𝑘∈[2𝑛/2 ] from Haar-random input with constant advantage. New proof of [LMW24]. Another consequence of our approach, which we describe in the technical overview as well as Appendix A, is a simple proof of the hardness of general-purpose one-query unitary synthesis as in [LMW24]. This is accomplished by proving the hardness of the ∑︀ oracle state search game for i.i.d. random binary phase states |𝜓𝑅,𝑘 ⟩ = √1𝑁 𝑥 𝑅(𝑘, 𝑥) |𝑥⟩; indeed, we can prove:
5
Theorem 1.12 (see Theorem A.1). For i.i.d. binary phase states |𝜓𝑅,𝑘 ⟩, any one-query adversary 𝒜 with workspace dimension 𝑀 wins the oracle state search game with probability at most 2 log 𝑀 +𝑂(1) . 𝐾 With a little more work, this simple analysis also extends to the oracle state search game with states |𝜓𝑘 ⟩ = 𝑈 |𝑘⟩ defined by a Haar-random unitary (see Theorem A.4). Unitary Synthesis vs. Quantum Programs. Finally, we consider the state search game for ∑︀ extremely simple phase unitaries 𝐹 = 𝑥 (−1)𝑓 (𝑥) |𝑥⟩⟨𝑥| and |𝜓𝑘 ⟩ = 𝐹 𝐻 |𝑘⟩ (analogous to the 𝑡 = 2 setting above), and prove its hardness for zero-query algorithms with quantum advice about 𝑓 . In other words, this is a quantitative separation between 1-query unitary synthesis and (approximation by) “quantum programs,” or (approximately) synthesizing unitaries relative to an advice state. Theorem 1.13 (see Theorem 5.7). Let 𝑓 : {0, 1}𝑛 → {0, 1} be uniformly random. Suppose a (zero-query) non-uniform algorithm uses 𝑆 qubits of advice depending on 𝑓 and outputs 𝑘 from one copy of 𝐹 𝐻 |𝑘⟩ with success probability 𝜀, for 𝑘 ← [𝐾]. Then, 𝜀 ≤ 𝑂(𝑆/𝐾). Theorem 1.13 is tight up to constants when 𝐾 = Ω(𝑁 ), as a trivial algorithm without advice wins the search game with probability 1/𝑁 while memorizing the 𝑁 -size truth table of 𝑓 would allow for winning the search game with probability 1. In fact, we show in Section 10.5 that the lower bound is tight over the entire range of 𝑆. Notably, this search game is asymptotically harder to win than for the classical states |𝜓𝑥,𝑦 ⟩ = |𝑥⟩ |𝑦 ⊕ 𝑓 (𝑥)⟩. This is because the “classical” search game has a trivial algorithm whose win probability is equal to 2−ℓ , where ℓ is the output length of 𝑓 , which is always much larger than 2−(𝑛+ℓ) (one over the relevant Hilbert space dimension). An open question. With these results in mind, a natural “frontier question” on the boundary of our current understanding is proving a one-query lower bound against algorithms that additionally receive quantum advice (before making their query); our proofs are currently limited to handling classical advice. This question is open for any family of unitaries, including permutations, 𝐹2 𝐻 ⊗𝑛 𝐹1 , and Haar-random 𝑈 .
1.4
Acknowledgements
We thank William Kretschmer, Gregory Rosenthal, and John Wright for many helpful discussions, and in particular for posing the questions of whether there are one-query algorithms for permutation synthesis and complex phase unitary synthesis. F.D., A.L., and F.M. were all supported in part by a grant from the UC Noyce Initiative to the Simons Institute for the Theory of Computing. F.D. and A.L. were supported in part by NSF CAREER award CNS-2541300 and an E. Lawrence Keyes, Jr./Emerson Electric Co. Faculty Award.
2
Technical Overview
We begin with a recap of the approach of [LMW24] and why it does not appear capable of proving Theorems 1.1 and 1.2, including a discussion of Theorem 1.11. 6
Then, we introduce the oracle state search game and prove that it is hard when the input states are i.i.d. binary phase states. As a bonus, this gives an alternative proof of the original 1-query unitary synthesis lower bound, which we believe is simpler than the proof from [LMW24]. Finally, we discuss how to extend this new approach to prove Theorems 1.1 and 1.2. We leave discussion of Theorems 1.5 and 1.13 to the body of the paper.
2.1
Recap of LMW
As discussed in the introduction, [LMW24] prove their unitary synthesis lower bound by studying a distinguishing task for families of states { |𝜓𝑅,𝑘 ⟩}𝑘∈[𝐾] defined relative to an oracle 𝑅. The task, which corresponds to the security of single-copy pseudorandom states [JLS18], is to distinguish •
𝑘∈[𝐾] |𝜓𝑅,𝑘 ⟩⟨𝜓𝑅,𝑘 | from
∑︀
• the maximally mixed state in an attack model where the adversary can make one Boolean function oracle query. If this game is hard for some 𝐾 < 𝑁/2, then implementing the reflection about Span{ |𝜓𝑅,𝑘 ⟩} must be hard. In [LMW24], they considered the case where 1 ∑︁ |𝜓𝑅,𝑘 ⟩ = √ 𝑅(𝑘, 𝑥) |𝑥⟩ 𝑁 𝑥∈[𝑁 ] is a binary phase state, where 𝑅(·, ·) assigns an independent random sign to each input (or, alternatively, each 𝑅(𝑘, 𝑥) could be an independent complex Gaussian). To analyze the maximum win probability in this game, they modeled an arbitrary adversary as having the form Π · 𝒪𝑓 · 𝑉 , where 𝑉 : C𝑁 → C𝑀 is a fixed isometry, (Π, I − Π) is a fixed binary projective measurement, and 𝒪𝑓 = 𝒪𝑓𝑅 is a binary phase oracle that can depend on the choice of 𝑅. Then, the adversary’s win probability (for a fixed 𝑅) is given by max
⃒ ⃒ ⃒ E
𝑓 :[𝑀 ]→{0,1} 𝑘←[𝐾]
⃒ ⃒
⟨𝜓𝑅,𝑘 | 𝑉 † 𝒪𝑓 Π𝒪𝑓 𝑉 |𝜓𝑅,𝑘 ⟩ − E ⟨𝜓| 𝑉 † 𝒪𝑓 Π𝒪𝑓 𝑉 |𝜓⟩ ⃒. |𝜓⟩
To analyze this optimization problem, using the intuition that the states |𝜓𝑅,𝑘 ⟩ (for a random choice of 𝑅) are Haar-random, [LMW24] introduce a weight vector decomposition 𝑉 |𝜓𝑅,𝑘 ⟩ = 𝐷𝑅,𝑘 · |wt𝑉 ⟩ , where |wt𝑉 ⟩ is a fixed “weight vector” whose coordinates track the expected weight when 𝑉 is applied to a Haar-random state, and 𝐷𝑅,𝑘 is an (𝑅, 𝑘)-dependent rescaling matrix whose entries are linear functions of the variables {𝑅(𝑘, 𝑥)}𝑥 . The above expression can then be upper bounded by a spectral norm ⃒⃒ ⃒⃒ ⃒⃒ ⃒⃒ † † ⃒⃒ E 𝐷𝑅,𝑘 Π𝐷𝑅,𝑘 − E 𝐷R Π𝐷R ⃒⃒, R
𝑘←[𝐾]
where 𝐷R = 𝐷R,𝑘 denotes the rescaling matrix distribution for a random R (which is independent of 𝑘). This matrix norm can then be bounded — either in expectation or with high probability over 𝑅 — in one of two ways, but both methods crucially rely on the fact that the variables 𝑅(𝑘, ·) are independent across different choices of 𝑘. 7
• A matrix Bernstein inequality can bound the expression using only independence across different 𝑘 as well as a bound on ||𝐷𝑅,𝑘 || with high probability over 𝑅. † • Sharper bounds were proved by first “decoupling” the 𝐷𝑅,𝑘 from the 𝐷𝑅,𝑘 (even before passing to the spectral relaxation), which is only possible for very specific distributions over 𝑅 (such as i.i.d. Gaussian or binary phase).
2.2
What goes wrong for other unitaries?
Suppose that we now want to prove lower bounds for synthesizing some family of unitaries 𝑈 , such as 𝑈 = 𝑃 or 𝑈 = 𝐹2 𝐻 ⊗𝑛 𝐹1 . Following [LMW24], the natural idea would be to describe a family of states |𝜓𝑈,𝑘 ⟩ exhibiting pseudorandomness properties. Unfortunately, we immediately run into an issue: for a given 𝑈 , what family of states |𝜓𝑈,𝑘 ⟩ should we consider? A natural choice would be |𝜓𝑈,𝑘 ⟩ = 𝑈 |𝑘⟩ (which works for Haar-random 𝑈 ), but for both 𝑈 = 𝑃 and 𝑈 = 𝐹2 𝐻 ⊗𝑛 𝐹1 such families fail to be pseudorandom for very simple reasons: • For permutations, it is easy to distinguish 𝑃 |𝑘⟩ = |𝜋(𝑘)⟩ for 𝑘 ← [𝐾] from Haar-random with just a single query to 𝜋 −1 : on input |𝑥⟩, compute 𝜋 −1 (𝑥) and check whether it lies in the range [𝐾]. • For 𝐹2 𝐻𝐹1 , the state 𝐹2 𝐻𝐹1 |𝑘⟩ = (−1)𝑓1 (𝑘) · 𝐹2 𝐻 ⊗𝑛 |𝑘⟩ can be synthesized (and therefore recognized) with a single query to 𝐹2 . So in both cases, the distinguishing game with state family |𝜓𝑈,𝑘 ⟩ = 𝑈 |𝑘⟩ is (possibly) much easier than the full-fledged synthesis task. On the other hand, there is a natural alternative proposal for the state family: instead define |𝜓𝑈,𝑘 ⟩ = 𝑈 𝐻 ⊗𝑛 |𝑘⟩. At first glance, this choice appears to be promising, as the trivial attacks above (for our cases of interest) no longer apply. Unfortunately, it is completely unclear how to analyze the spectral norm of the matrix † † Π𝐷R Π𝐷𝑅,𝑘 − E 𝐷R E 𝐷𝑅,𝑘 R
𝑘←[𝐾]
arising from the [LMW24] argument. Superficially, the reason for this is that the matrices {𝐷𝑅,𝑘 }𝑘 , whose entries describe the amplitudes of the state 𝑉 |𝜓𝑈,𝑘 ⟩, are now highly dependent across different choices of 𝑘. This rules out approaches based on Bernstein’s inequality, and more generally, it seems very unclear how to argue about the concentration of such a random matrix. An attack. In fact, this uncertainty is warranted, because we have a non-trivial attack on this pseudorandomness property! Specifically, we consider the permutation case, with states 1 ∑︁ 1 ∑︁ −1 𝑃 𝐻 ⊗𝑛 |𝑘⟩ = √ (−1)⟨𝑘,𝑥⟩ |𝜋(𝑥)⟩ = √ (−1)⟨𝑘,𝜋 (𝑥)⟩ |𝑥⟩ . 𝑁 𝑥∈[𝑁 ] 𝑁 𝑥∈[𝑁 ] √ We claim that it is easy, with one function query, to distinguish 𝑃 𝐻 ⊗𝑛 |𝑘⟩ for 𝑘 ← [ 𝑁 ] from a maximally mixed state. Specifically, we prove this when identifying [𝑁 ] = {0, 1}𝑛 , [𝐾] = {0𝑛/2 } × 8
{0, 1}𝑛/2 via binary representation. In this case, we re-name 𝑘 ∈ [𝐾] as (0𝑛/2 , 𝑘) ∈ {0, 1}𝑛 and define 𝜋 −1 (𝑥) = (𝑔1 (𝑥), 𝑔2 (𝑥)) ∈ {0, 1}𝑛/2 × {0, 1}𝑛/2 , and write ∑︁ 1 𝑃 𝐻 ⊗𝑛 |𝑘⟩ = √ (−1)⟨𝑘,𝑔2 (𝑥)⟩ |𝑥⟩ 𝑁 𝑥∈{0,1}𝑛 ∑︁ ∑︁ 1 =√ (−1)⟨𝑘,𝑦⟩ · |𝑥⟩ 𝑁 𝑦∈{0,1}𝑛/2 𝑥:𝑔2 (𝑥)=𝑦
:=
1
∑︁
𝑁 1/4
𝑦
(−1)⟨𝑘,𝑦⟩ · |𝜑𝑦 ⟩
The idea behind the attack is (just like before) to break pseudorandomness without fully inverting the unitary 𝑃 . In this case, we make use of Rosenthal’s one-query state synthesis algorithm [Ros24]: for any family of states |𝜓𝑦 ⟩ indexed by 𝑦, there is a classical oracle 𝑓 (·, ·) relative to which |𝜑𝑦 ⟩ can be synthesized by querying 𝑓 (·, 𝑦) (possibly along with some auxiliary junk state). This means that a single query to the function 𝑓 * (·, 𝑥) = 𝑓 (·, 𝑔2 (𝑥)) allows synthesizing |𝜑𝑔2 (𝑥) ⟩. Applying this algorithm (in superposition) for |𝜓𝑦 ⟩ = |𝑦⟩ ⊗ |𝜑𝑦 ⟩ gives us our attack, mapping 𝑃 𝐻 ⊗𝑛 |𝑘⟩ to 1 𝑁 1/4
∑︁
(−1)⟨𝑘,𝑦⟩ · |𝜑𝑦 ⟩ ⊗ |𝑦⟩ ⊗ |𝜑𝑦 ⟩ ⊗ |junk𝑦 ⟩ ,
𝑦∈{0,1}𝑛/2
which we can recognize by applying a SWAP test to the first and third registers. In our opinion, this suggests that understanding one-query pseudorandomness properties of states of the form |𝜓𝑅,𝑘 ⟩ (for structured randomness 𝑅) is extremely subtle!
2.3
From decision to search
With serious obstacles and negative results for generalizing [LMW24] outside of the setting of “fully random” states |𝜓𝑘 ⟩, we introduce the oracle state search game as a new method for proving unitary synthesis lower bounds. As stated in the introduction, in the oracle state search game: • The challenger generates and sends |𝜓𝑅,𝑘 ⟩ to the adversary for a random 𝑘 ← [𝐾]. • The adversary outputs a string 𝑘 ′ ∈ [𝐾] and wins if 𝑘 = 𝑘 ′ . For example, if we have |𝜓𝑘 ⟩ = 𝑈 |𝑘⟩ for some unitary 𝑈 , then synthesizing 𝑈 † is at least as hard as winning this game. To demonstrate our methodology, we now give a simple proof of Theorem 1.12: that this game ∑︀ is hard for one-query adversaries when |𝜓𝑅,𝑘 ⟩ = √1𝑁 𝑥 𝑅(𝑘, 𝑥) |𝑥⟩ for i.i.d. binary phases 𝑅(𝑘, 𝑥). Proof of Theorem 1.12. Without loss of generality, one-query adversaries for the oracle state search game have the following form: • Apply an isometry 𝑉 : C𝑁 → C𝑀 . • Apply a phase unitary 𝐹 = 𝐹𝑅 depending on 𝑅. 9
• Perform a projective 𝐾-outcome measurement {Π𝑘 }𝑘∈[𝐾] . With this notation, the adversary’s success probability is given by Win(𝒜 | 𝑅) = max E 𝐹
𝑘←[𝐾]
⃒⃒2 ]︁ [︁⃒⃒ ⃒⃒ ⃒⃒ ⃒⃒Π𝑘 𝐹 𝑉 |𝜓𝑅,𝑘 ⟩ ⃒⃒ .
At first glance, this may appear more unwieldy than the adversary’s advantage in the distinguishing game. However, a simple observation helps us a great deal: because {Π𝑘 }𝑘 form a projective measurement, the states {Π𝑘 𝐹 𝑉 |𝜓𝑅,𝑘 ⟩} are always orthogonal, so ⃒⃒ 1 ∑︁ ⃒⃒2 ⃒⃒ ⃒⃒ Win(𝒜 | 𝑅) = max⃒⃒ √ Π𝑘 𝐹 𝑉 |𝜓𝑅,𝑘 ⟩ ⃒⃒ . 𝐹 𝐾 𝑘∈[𝐾]
Now, using the [LMW24] diagonal decomposition for the state family |𝜓𝑅,𝑘 ⟩ = 𝐷𝑅,𝑘 |wt𝑉 ⟩ , we can upper bound this probability by the spectral relaxation ⃒⃒ 1 ∑︁ ⃒⃒2 ⃒⃒ ⃒⃒ Win(𝒜 | 𝑅) = max⃒⃒ √ Π𝑘 𝐹 𝐷𝑅,𝑘 |wt𝑉 ⟩ ⃒⃒ 𝐹 𝐾 𝑘∈[𝐾] ⃒⃒ 1 ∑︁ ⃒⃒2 ⃒⃒ ⃒⃒ Π𝑘 𝐷𝑅,𝑘 ⃒⃒ . ≤ ⃒⃒ √ 𝐾 𝑘∈[𝐾]
Thus, we wish to upper bound the value ⃒⃒2 ]︁
[︁⃒⃒
E ⃒ ⃒ 𝑀𝑅 ⃒ ⃒ , 𝑅
∑︀ where 𝑀𝑅 = √1 𝑘 Π𝑘 𝐷𝑅,𝑘 is a mean zero random matrix. The big question is, should we 𝐾
expect this quantity to be small? To start with, we can calculate the matrix variance, an important proxy for how large we expect this quantity to be: ⃒⃒)︁ ⃒⃒
⃒⃒ ⃒⃒ ⃒⃒ ⃒⃒
(︁⃒⃒ ⃒⃒
Var(𝑀𝑅 ) = max ⃒⃒E 𝑀𝑅† 𝑀𝑅 ⃒⃒, ⃒⃒E 𝑀𝑅 𝑀𝑅† ⃒⃒ . 𝑅
𝑅
𝑅
Fortunately, the random matrix 𝑀𝑅 is quite well-behaved, and we can calculate E 𝑀𝑅† 𝑀𝑅 = 𝑅
= =
1 ∑︁ E[𝐷† Π𝑘 𝐷𝑅,𝑘 ] 𝐾 𝑘 𝑅 𝑅,𝑘 1 ∑︁ E[𝐷† Π𝑘 𝐷𝑅,0 ] 𝐾 𝑘 𝑅 𝑅,0
1 1 † E[𝐷𝑅,0 · I, · I · 𝐷𝑅,0 ] = 𝐾𝑅 𝐾
as 𝑘 Π𝑘 = I and the rescaling terms have been defined so that they square to 1 on average. Similarly, ∑︀
E 𝑀𝑅 𝑀𝑅† = 𝑅
1 ∑︁ † E[Π𝑘′ 𝐷𝑅,𝑘′ 𝐷𝑅,𝑘 Π𝑘 ] 𝑅 𝐾 𝑘,𝑘′ 10
= = =
1 ∑︁ † E[Π𝑘 𝐷𝑅,𝑘 𝐷𝑅,𝑘 Π𝑘 ] 𝐾 𝑘 𝑅 1 ∑︁ † E[Π𝑘 𝐷𝑅,0 𝐷𝑅,0 Π𝑘 ] 𝐾 𝑘 𝑅 1 ∑︁ 1 Π𝑘 = · I, 𝐾 𝑘 𝐾
† where we additionally make use of the fact that E[𝐷𝑅,𝑘′ 𝐷𝑅,𝑘 ] = 0 for 𝑘 ̸= 𝑘 ′ . Thus, the vari𝑅
⃒⃒2
ance parameter predicts the quantity ⃒⃒𝑀𝑅 ⃒⃒ to be roughly bounded by 𝐾1 in expectation (up to poly(log dim 𝑀𝑅 ) factors). This is exactly what we are looking for! To complete the proof in the case of i.i.d. binary phase states, we simply observe that since the entries of 𝐷𝑅,𝑘 are linear combinations of the 𝑅(𝑘, 𝑥), the entire matrix 𝑀𝑅 is a “matrix Rademacher series,” or a Rademacher combination of fixed matrices, which is well-known to exhibit concentration governed by the matrix variance parameter [Tro15]. This proves an 𝑂( log𝐾𝑀 ) win probability upper bound for adversaries acting on 𝑀 qubits. ⃒⃒
2.4
Search game hardness beyond the random case
While the analysis from the previous section was done with i.i.d. binary phase states in mind, it turns out that two very promising parts of the analysis hold under mild assumptions on the distribution of coefficients 𝑅. That is: • The entries of the matrix 𝑀𝑅 always have a linear dependence on the coefficients 𝑅(𝑘, 𝑥). • The matrix variance Var(𝑀𝑅 ) ≤ 𝐾1 , provided that (1) in expectation over 𝑅, for every 𝑘, 𝑅
E |𝜓𝑅,𝑘 ⟩⟨𝜓𝑅,𝑘 | is maximally mixed over C𝑁 , and (2) for every 𝑘 ̸= 𝑘 ′ and every pair (𝑥, 𝑥′ ), 𝑅
E[𝑅(𝑘, 𝑥)𝑅(𝑘 ′ , 𝑥′ )] = 0. 𝑅
Note that condition (1) is only about the marginal mixed state E |𝜓𝑅,𝑘 ⟩⟨𝜓𝑅,𝑘 |, and does not require 𝑅
any level of independence between different 𝑅(𝑘, ·). In fact, we can relax this condition further, so that E |𝜓𝑅,𝑘 ⟩⟨𝜓𝑅,𝑘 | is only required to be maximally mixed over some subspace independent of 𝑘. 𝑅
the matrix variance statistic is a useful heuristic but does not guarantee that ⃒⃒Of ⃒course, ⃒2 E ⃒⃒𝑀𝑅 ⃒⃒ is small (let alone on the order of 1/𝐾). Nevertheless, we are able to argue concen𝑅
tration for the two most prominent (much lower randomness complexity) distributions of unitaries one can ask about. Permutations. As before, we consider the family of states 1 ∑︁ −1 (−1)⟨𝑘,𝜋 (𝑥)⟩ |𝑥⟩ |𝜓𝑅,𝑘 ⟩ = 𝑃 𝐻 ⊗𝑛 |𝑘⟩ = √ 𝑁 𝑥 −1
corresponding to the function 𝑅(𝑘, 𝑥) = (−1)⟨𝑘,𝜋 (𝑥)⟩ for a random permutation 𝜋. Evidently, these values are highly correlated across 𝑘. Nevertheless, using the linearity of 𝑀𝑅 , we can write 𝑀𝑅 =
∑︁
𝑅(𝑘, 𝑥) · 𝐵𝑘,𝑥
𝑘,𝑥
11
for some fixed, reasonably explicit and well-behaved matrices 𝐵𝑘,𝑥 . And while our randomness has a lot of “cross-𝑘” dependency, the functions 𝑅(·, 𝑥) are still mean zero3 and extremely close to independent! This conveniently the matrix variance (︁⃒⃒ ∑︀ means that )︁ parameter we calculated earlier is ⃒⃒ ⃒⃒ ∑︀ † † ⃒⃒⃒⃒ ⃒ ⃒ ⃒ ⃒ ⃒ ⃒ roughly bounded by max ≈ 𝐾1 , so our heuristic is still good. 𝑘,𝑥 𝐵𝑘,𝑥 𝐵𝑘,𝑥 , 𝑘,𝑥 𝐵𝑘,𝑥 𝐵𝑘,𝑥 We are ultimately able to analyze 𝑀𝑅 by writing it as a “combinatorial matrix sum” [MJC+ 14] 𝑀𝑅 =
∑︁
𝐴𝑥,𝜋−1 (𝑥) ,
𝑥
for a 2𝑛 × 2𝑛 family of matrices
(−1)⟨𝑘,𝑦⟩ 𝐵𝑘,𝑥
𝐴𝑥,𝑦 =
∑︁ 𝑘
satisfying two important properties: • For a random choice of 𝑦, the matrix 𝐴𝑥,𝑦 is zero in expectation. • The individual matrices 𝐴𝑥,𝑦 are “small” in the expected sense: they have spectral norm at √ most 1/ 𝐾, roughly speaking because the 𝐵𝑘,𝑥 are mutually orthogonal. It turns out that this information, plus a very similar calculation to the matrix variance bound from earlier, is enough to guarantee concentration [MJC+ 14], so this proves Theorem 1.9! Alternating phases.
To rule out 1-query unitary synthesis of 𝐹2 𝐻𝐹1 , we consider the states |𝜓𝑅,𝑘 ⟩ = 𝐹2 𝐻𝐹1 𝐻 |𝑘⟩ 1 ∑︁ = 𝐹2 𝐻 · √ (−1)𝑓1 (𝑦)+⟨𝑦,𝑘⟩ |𝑦⟩ 𝑁 𝑦 ∑︁ 1 = (−1)𝑓2 (𝑥)+𝑓1 (𝑦)+⟨𝑦,𝑘⟩+⟨𝑦,𝑥⟩ |𝑥⟩ , 𝑁 𝑥,𝑦
so our coefficients have the form ∑︁ 1 𝑅(𝑘, 𝑥) = √ (−1)𝑓2 (𝑥) (−1)𝑓1 (𝑦)+⟨𝑦,𝑘+𝑥⟩ := (−1)𝑓2 (𝑥) · 𝛼𝑘+𝑥 , 𝑁 𝑦 where the coefficients 𝛼𝑘+𝑥 depend on 𝑓1 but not 𝑓2 . Thus, again writing 𝑀𝑅 =
∑︁
𝑅(𝑘, 𝑥) · 𝐵𝑘,𝑥 ,
𝑘,𝑥
we observe that although the 𝑅(𝑘, 𝑥) are not all independent, this is a Rademacher matrix sum for every fixed 𝑓1 . This implies that ⃒⃒ ⃒⃒
⃒⃒2 ⃒⃒
⃒⃒ ⃒⃒
⃒⃒ ⃒⃒
⃒⃒ ⃒⃒
⃒⃒ ⃒⃒
⃒⃒ ⃒⃒
⃒⃒ ⃒⃒
E𝑓1 ,𝑓2 ⃒⃒𝑀𝑅 ⃒⃒ ≲ E𝑓1 ⃒⃒Var(𝑀𝑅 )⃒⃒ ≲ E𝑓1 ⃒⃒E𝑓2 𝑀𝑅† 𝑀𝑅 ⃒⃒ + E𝑓1 ⃒⃒E𝑓2 𝑀𝑅 𝑀𝑅† ⃒⃒, 𝑓2
so we have reduced the problem to another matrix concentration problem. Finally, while it may ̃︁𝑓 = E𝑓 𝑀𝑅 𝑀 † may be challenging because of a appear that arguing the concentration of 𝑀 1 2 𝑅 quadratic dependence on 𝑓1 , it turns out that there is a simple rectangular square root 𝑀𝑓1 that ̃︁𝑓 . This allows us to bound ||𝑀 ̃︁𝑓 || = ||𝑀𝑓 ||2 via depends linearly on 𝑓1 and satisfies 𝑀𝑓†1 𝑀𝑓1 = 𝑀 1 1 1 a second matrix concentration inequality. We refer the reader to Section 8 for more details. 3
This requires excluding 𝑘 = 0𝑛 from the set of keys.
12
3
Preliminaries
We use 𝑁 = 2𝑛 for the dimension of a main 𝑛-qubit register and 𝑀 = 2𝑚 for the dimension of a potentially larger workspace. For a positive integer 𝐾, we write [𝐾] := {0, 1, . . . , 𝐾 − 1}.
3.1
The unitary synthesis problem
We recall the oracle-circuit formulation from [LMW24]. Definition 3.1 (Approximating a unitary, [LMW24]). Let 𝑈 be an 𝑛-qubit unitary, and let Φ𝑈 be the associated quantum channel. Let Φapprox be a quantum channel with 𝑛-qubit input and output registers. We say that Φapprox 𝜀-approximates 𝑈 if 𝐷◇ (Φapprox , Φ𝑈 ) ≤ 𝜀. Definition 3.2 (Channel implemented by an oracle circuit, [LMW24]). Given a 𝑡-query oracle circuit 𝒜(·) with an 𝑛-qubit input register, an 𝑚-qubit workspace register, intermediate unitaries 𝑈1 , . . . , 𝑈𝑡+1 on 𝑚 qubits, and a Boolean function 𝑓 : {0, 1}𝑚 → {±1}, the induced 𝑛-qubit channel Φ𝒜𝑓 acts as follows. 1. On input |𝜓⟩, prepare 𝑈𝑡+1 · 𝑂𝑓 · 𝑈𝑡 · · · 𝑂𝑓 · 𝑈2 · 𝑂𝑓 · 𝑈1 ( |𝜓⟩ |0𝑚−𝑛 ⟩). 2. Output the first 𝑛 qubits and discard the remaining 𝑚 − 𝑛 workspace qubits. More generally, if 𝑊 is an 𝑚-qubit unitary, we write Φ𝒜𝑊 for the channel obtained by replacing each occurrence of 𝑂𝑓 above by 𝑊 . Definition 3.3 ((𝒞1 , 𝒞2 )-unitary synthesis). Let 𝒞1 be a class of 𝑛-qubit unitaries and let 𝒞2 be a class of 𝑚-qubit unitaries. A 𝑡-query oracle circuit 𝒜(·) is an (𝜀, 𝑡)-approximate (𝒞1 , 𝒞2 )-synthesis algorithm if, for every 𝑈 ∈ 𝒞1 , there exists 𝑊𝑈 ∈ 𝒞2 such that 𝐷◇ (Φ𝒜𝑊𝑈 , Φ𝑈 ) ≤ 𝜀. The standard variant of unitary synthesis concerns the case where 𝒞2 consists of binary phase unitaries (which implement Boolean functions). Definition 3.4 (Unitary synthesis for a class 𝒞). Let ℱ{±1} denote the class of binary phase oracles, i.e., unitaries of the form 𝑂𝑓 . We say that 𝒜(·) is an (𝜀, 𝑡)-approximate synthesis algorithm for 𝒞 if it is an (𝜀, 𝑡)-approximate (𝒞, ℱ{±1} )-synthesis algorithm. A slight modification of the standard variant considers 𝒞2 to be the class of all (not necessarily binary) phase unitaries. Since phase unitaries can be implemented to arbitrary precision given two queries to a binary phase oracle, it follows that 𝑡-query algorithms in this model can be simulated by 2𝑡-query algorithms in the standard model. We observe that (𝒞1 , 𝒞2 )-relative unitary synthesis obeys a simple composition theorem. Proposition 3.5 (Composition of relative unitary synthesis). Let 𝒜(·) be an (𝜀1 , 𝑡1 )-approximate (𝒞1 , 𝒞2 )-synthesis algorithm, and let ℬ (·) be an (𝜀2 , 𝑡2 )-approximate (𝒞2 , 𝒞3 )-synthesis algorithm. Then there exists an (𝜀1 + 𝑡1 𝜀2 , 𝑡1 𝑡2 )-approximate (𝒞1 , 𝒞3 )-synthesis algorithm. 13
Proof. Fix 𝑈 ∈ 𝒞1 . Let 𝑊𝑈 ∈ 𝒞2 witness the approximation guarantee for 𝒜(·) , so that 𝐷◇ (Φ𝒜𝑊𝑈 , Φ𝑈 ) ≤ 𝜀1 . Let 𝑍𝑈 ∈ 𝒞3 witness the approximation guarantee for ℬ (·) applied to 𝑊𝑈 , so that 𝐷◇ (Φℬ𝑍𝑈 , Φ𝑊𝑈 ) ≤ 𝜀2 . Construct a new oracle circuit 𝒞 (·) by replacing each of the 𝑡1 query gates to 𝑊 inside 𝒜(·) by a fresh copy of ℬ (·) . Then 𝒞 (·) makes 𝑡1 𝑡2 queries to its oracle. For 𝑗 ∈ {0, 1, . . . , 𝑡1 }, let Γ𝑗 denote the channel obtained from 𝒜𝑊𝑈 by replacing the first 𝑗 query gates to 𝑊𝑈 by ℬ 𝑍𝑈 , while leaving the remaining 𝑡1 − 𝑗 query gates ideal. Thus Γ0 = Φ𝒜𝑊𝑈 and Γ𝑡1 = Φ𝒞 𝑍𝑈 . For each 𝑗 ∈ [𝑡1 ], the channels Γ𝑗−1 and Γ𝑗 differ only in a single query slot, so by monotonicity of diamond distance under pre- and post-composition with channels, 𝐷◇ (Γ𝑗−1 , Γ𝑗 ) ≤ 𝐷◇ (Φℬ𝑍𝑈 , Φ𝑊𝑈 ) ≤ 𝜀2 . By the triangle inequality, 𝐷◇ (Φ𝒞 𝑍𝑈 , Φ𝒜𝑊𝑈 ) ≤
𝑡1 ∑︁
𝐷◇ (Γ𝑗−1 , Γ𝑗 ) ≤ 𝑡1 𝜀2 .
𝑗=1
Combining this with the outer approximation error gives 𝐷◇ (Φ𝒞 𝑍𝑈 , Φ𝑈 ) ≤ 𝐷◇ (Φ𝒞 𝑍𝑈 , Φ𝒜𝑊𝑈 ) + 𝐷◇ (Φ𝒜𝑊𝑈 , Φ𝑈 ) ≤ 𝑡1 𝜀2 + 𝜀1 . Since 𝑈 ∈ 𝒞1 was arbitrary, the claim follows. We will also use a different but related notion of closeness between the implemented channel and the target unitary channel, based on worst-case fidelity on worst-case inputs, possibly entangled with an auxiliary register. We call this notion auxiliary-input correctness. Definition 3.6 (Auxiliary-input correctness of a synthesis algorithm). Let 𝒜(·) be a universal oracle circuit with induced channel Φ𝒜(·) on the 𝑛-qubit input register. We say that 𝒜(·) has correctness 𝜂 for synthesizing a family {𝑈𝑛 }𝑛 of 𝑛-qubit unitary if, for every 𝑈 in the family, there exists an oracle 𝑓𝑈 such that for every pure state |Ψ⟩𝑋,Aux on the input register 𝑋 together with an arbitrary auxiliary register Aux, 𝐹 ((Φ𝑈 ⊗ IdAux )( |Ψ⟩⟨Ψ|), (Φ𝒜𝑓𝑈 ⊗ IdAux )( |Ψ⟩⟨Ψ|)) ≥ 𝜂. This fidelity-based notion of correctness is equivalent to the diamond-norm approximate formulation in Definition 3.1, up to constant factor parameter loss, due to the following standard fact from quantum information theory [Wat18, Theorem 3.33]. Proposition 3.7 (Diamond distance versus aux-input correctness). Let 𝑈 be an 𝑛-qubit unitary, and let Φ be an 𝑛-qubit channel. Then, 1. If 𝐷◇ (Φ, Φ𝑈 ) ≤ 𝜀, then Φ has aux-input correctness at least 1 − 𝜀 for 𝑈 .
14
2. If Φ has aux-input correctness at least 𝜂 for 𝑈 , then 𝐷◇ (Φ, Φ𝑈 ) ≤
√︀
1 − 𝜂.
This means that aux-input correctness obeys a composition theorem due to Proposition 3.5. However, we observe that at least for the case 𝑡1 = 𝑡2 = 1, there is a tighter composition theorem without passing through Proposition 3.7. Proposition 3.8 (Composition of aux-input correctness). Let 𝒜(·) and ℬ (·) be one-query oracle circuits, and let 𝒞1 , 𝒞2 , 𝒞3 be classes of unitaries. Assume that the following hold: 1. For every 𝑈 ∈ 𝒞1 , there exists 𝑊𝑈 ∈ 𝒞2 such that for every pure state |Ψ⟩𝑋,Aux , 𝐹 ((Φ𝑈 ⊗ IdAux )( |Ψ⟩⟨Ψ|), (Φ𝒜𝑊𝑈 ⊗ IdAux )( |Ψ⟩⟨Ψ|)) ≥ 𝜂1 . 2. For every 𝑊 ∈ 𝒞2 , there exists 𝑍𝑊 ∈ 𝒞3 such that for every pure state |Φ⟩𝑌,Aux , 𝐹 ((Φ𝑊 ⊗ IdAux )( |Φ⟩⟨Φ|), (Φℬ𝑍𝑊 ⊗ IdAux )( |Φ⟩⟨Φ|)) ≥ 𝜂2 . Then there exists a one-query oracle circuit 𝒟(·) such that for every 𝑈 ∈ 𝒞1 , there exists 𝑍𝑈 ∈ 𝒞3 for which, for every pure state |Ψ⟩𝑋,Aux , 𝐹 ((Φ𝑈 ⊗ IdAux )( |Ψ⟩⟨Ψ|), (Φ𝒟𝑍𝑈 ⊗ IdAux )( |Ψ⟩⟨Ψ|)) ≥ 𝜂⋆ , where 𝜂⋆ := cos
2
(︂
𝜋 √ √ min , arccos 𝜂1 + arccos 𝜂2 2 {︂
}︂)︂
.
Proof. Let 𝒟(·) be obtained by replacing the unique oracle call inside 𝒜(·) by ℬ (·) . Fix 𝑈 ∈ 𝒞1 , and choose 𝑊𝑈 ∈ 𝒞2 and 𝑍𝑈 ∈ 𝒞3 as in the hypotheses. Fix any pure state |Ψ⟩𝑋,Aux , and define 𝜌 := (Φ𝒟𝑍𝑈 ⊗ IdAux )( |Ψ⟩⟨Ψ|),
𝜎 := (Φ𝒜𝑊𝑈 ⊗ IdAux )( |Ψ⟩⟨Ψ|),
𝜏 := (Φ𝑈 ⊗ IdAux )( |Ψ⟩⟨Ψ|).
By the first hypothesis, 𝐹 (𝜎, 𝜏 ) ≥ 𝜂1 . It remains to lower bound 𝐹 (𝜌, 𝜎). Let |Ω⟩𝑄,Aux be the pure state of the queried register of 𝒜, together with all remaining workspace registers and the auxiliary register Aux, immediately before the unique query gate of 𝒜𝑊𝑈 on input |Ψ⟩. Replacing that ideal query 𝑊𝑈 by the one-query implementation ℬ 𝑍𝑈 acts on the queried register while leaving Aux untouched, so the second hypothesis gives fidelity at least 𝜂2 between the corresponding post-query states. Applying the common postquery channel of 𝒜 to both branches and using monotonicity of fidelity under channels, we obtain 𝐹 (𝜌, 𝜎) ≥ 𝜂2 . √︀ Now define the Bures angle 𝐴(𝛼, 𝛽) := arccos 𝐹 (𝛼, 𝛽). By the triangle inequality for the Bures angle (see, e.g., [Wat18, Section 9.2]), √ √ 𝐴(𝜌, 𝜏 ) ≤ 𝐴(𝜌, 𝜎) + 𝐴(𝜎, 𝜏 ) ≤ arccos 𝜂2 + arccos 𝜂1 . Therefore, 𝐹 (𝜌, 𝜏 ) ≥ cos
2
(︂
𝜋 √ √ min , arccos 𝜂1 + arccos 𝜂2 2 {︂
Since |Ψ⟩𝑋,Aux was arbitrary, the claim follows. 15
}︂)︂
= 𝜂⋆ .
3.2
One-query normal form
The lower bounds in this paper all concern one-query algorithms, so we describe a normal form that will be used throughout, following [LMW24]. Definition 3.9 (One-query unitary synthesis algorithm). A one-query unitary synthesis algorithm on 𝑛-qubit inputs is specified by • an oracle 𝑂𝑓 , • an isometry 𝑉 : C𝑁 → C𝑀 , representing the computation before the oracle query, and • a unitary 𝑈 on C𝑀 , representing the computation after the oracle query. On input |𝜓⟩ ∈ C𝑁 , the corresponding quantum channel prepares 𝑈 𝑂𝑓 𝑉 |𝜓⟩ and then outputs the designated 𝑛-qubit subsystem. Fixing the computational basis on the 𝑀 -dimensional workspace, every isometry 𝑉 : C𝑁 → C𝑀 can be written as ∑︁ |𝑖⟩⟨𝑣𝑖 | , 𝑉 = 𝑖∈[𝑀 ]
where the vectors |𝑣𝑖 ⟩ ∈ C𝑁 satisfy
∑︁
|𝑣𝑖 ⟩⟨𝑣𝑖 | = I𝑁 .
𝑖∈[𝑀 ]
3.3
The weight vector decomposition relative to an input distribution
We next define the diagonal (weight vector) decomposition of an isometry 𝑉 with respect to a distribution on input states. This generalizes the diagonal decomposition of [LMW24] to an arbitrary input distribution ([LMW24] considered only maximally mixed inputs). In our setting, the relevant weight vector is attached not just to the isometry 𝑉 , but to 𝑉 together with the input distribution. Lemma 3.10 (Weight vector decomposition). Let 𝑉 : C𝑁 → C𝑀 be an isometry, and write 𝑉 =
∑︁
|𝑖⟩⟨𝑣𝑖 | .
𝑖∈[𝑀 ]
Let 𝜇 be a distribution on pure states in C𝑁 , and define [︁
]︁
𝑝𝑖 := E𝜓∼𝜇 |⟨𝑣𝑖 |𝜓⟩|2 = ⟨𝑣𝑖 | · E𝜓 |𝜓⟩⟨𝜓| · |𝑣𝑖 ⟩ , [︀
]︀
|wt𝑉,𝜇 ⟩ :=
∑︁ √
𝑝𝑖 |𝑖⟩ .
𝑖∈[𝑀 ]
For each pure state |𝜓⟩, define the diagonal matrix (𝜇)
𝐷𝑉,𝜓 :=
⟨𝑣𝑖 |𝜓⟩ |𝑖⟩⟨𝑖| , √ 𝑝𝑖 𝑖∈[𝑀 ]: 𝑝 >0 ∑︁
𝑖
with diagonal entry 0 when 𝑝𝑖 = 0. Then |wt𝑉,𝜇 ⟩ is a unit vector, and for 𝜇-almost every |𝜓⟩ we have (𝜇) 𝑉 |𝜓⟩ = 𝐷𝑉,𝜓 |wt𝑉,𝜇 ⟩ . 16
Proof. Since 𝑉 is an isometry, ⎛
|⟨𝑣𝑖 |𝜓⟩|2 = ⟨𝜓| ⎝
∑︁ 𝑖∈[𝑀 ]
⎞
|𝑣𝑖 ⟩⟨𝑣𝑖 |⎠ |𝜓⟩ = ⟨𝜓|𝜓⟩ = 1
∑︁
𝑖∈[𝑀 ]
for every unit vector |𝜓⟩. Averaging over 𝜓 ∼ 𝜇 gives 𝑖 𝑝𝑖 = 1, so |wt𝑉,𝜇 ⟩ has unit norm. For the decomposition itself, if 𝑝𝑖 = 0 then the nonnegative random variable |⟨𝑣𝑖 |𝜓⟩|2 has expectation 0, and hence vanishes with probability 1. Therefore, for 𝜇-almost every |𝜓⟩, ∑︀
∑︁ ⟨𝑣𝑖 |𝜓⟩
(𝜇)
𝐷𝑉,𝜓 |wt𝑉,𝜇 ⟩ =
√
𝑖∈[𝑀 ]
3.4
𝑝𝑖
⎛
∑︁ √
|𝑖⟩⟨𝑖| ⎝
⎞
𝑝𝑗 |𝑗⟩⎠ =
∑︁
⟨𝑣𝑖 |𝜓⟩ |𝑖⟩ = 𝑉 |𝜓⟩ .
𝑖∈[𝑀 ]
𝑗∈[𝑀 ]
Useful concentration inequalities
In this section, we state two matrix concentration inequalities that are used in the proofs of Theorems 5.1 and 5.2, respectively. Theorem 3.11 (Matrix Rademacher series, [Tro15, Theorem 4.1.1 and Equation (4.1.7)]). Let {𝜀𝑘 }𝑘 be independent Rademacher random variables and let {𝐵𝑘 }𝑘 be fixed complex matrices of dimension 𝑑1 × 𝑑2 . Define 𝑍 :=
∑︁
𝜀𝑘 𝐵 𝑘 ,
𝑘
⃦ ⃦ ⃦}︃ {︃⃦ ⃦∑︁ ⃦ ⃦∑︁ ⃦ ⃦ ⃦ *⃦ ⃦ * 𝑣(𝑍) := max ⃦ 𝐵𝑘 𝐵𝑘 ⃦ , ⃦ 𝐵𝑘 𝐵𝑘 ⃦ . ⃦ ⃦ ⃦ ⃦ 𝑘
Then for all 𝑡 ≥ 0,
𝑘
(︃
)︃
𝑡2 Pr[‖𝑍‖ ≥ 𝑡] ≤ (𝑑1 + 𝑑2 ) exp − , 2𝑣(𝑍) and moreover 𝑣(𝑍) ≤ E‖𝑍‖2 ≤ 2 𝑣(𝑍) 1 + log(𝑑1 + 𝑑2 ) . (︀
)︀
Theorem 3.12 (Bernstein inequality for a combinatorial matrix sum, [MJC+ 14, Corollary 10.3]). Let (𝐴𝑗𝑘 )𝑛𝑗,𝑘=1 be Hermitian 𝑑 × 𝑑 matrices such that 𝑛 ∑︁
𝐴𝑗𝑘 = 0
and
‖𝐴𝑗𝑘 ‖ ≤ 𝑟
for all (𝑗, 𝑘).
𝑗,𝑘=1
Let 𝜋 be a uniformly random permutation of {1, . . . , 𝑛} and define 𝑋 :=
𝑛 ∑︁
𝐴𝑗,𝜋(𝑗) .
𝑗=1
Then for every 𝑡 ≥ 0, (︃
)︃
𝑡2 √ Pr 𝜆max (𝑋) ≥ 𝑡 ≤ 𝑑 · exp − , 12𝜎 2 + 4 2 𝑟𝑡 [︀
where
]︀
⃦ ⃦ ⃦ ⃦ ⃦ 𝑛 ⃦ ⃦ 𝑛 ⃦ ∑︁ ∑︁ ⃦ ⃦ ⃦ ⃦ 1⃦ 1⃦ † 2 2 ⃦ 𝜎 := ⃦ 𝐴𝑗𝑘 ⃦ = ⃦ 𝐴𝑗𝑘 𝐴𝑗𝑘 ⃦ ⃦. 𝑛 ⃦𝑗,𝑘=1 𝑛 ⃦𝑗,𝑘=1 ⃦ ⃦
17
4
The Oracle State Search and Choi State Games
In this section, we define two new cryptographic games that will enable us to prove unitary synthesis lower bounds. First, we describe and study the oracle state search game. Definition 4.1 (Oracle state search game). Fix a random variable R and, for every 𝑅 in its support, define a family of normalized states {︀
|𝜓𝑅,𝑘 ⟩ : 𝑘 ∈ [𝐾] ⊆ C𝑁 . }︀
Without loss of generality, we may describe |𝜓𝑅,𝑘 ⟩ in the computational basis with the following normalization: 1 ∑︁ |𝜓𝑅,𝑘 ⟩ = √ 𝑅(𝑘, 𝑥) |𝑥⟩ 𝑁 𝑥∈[𝑁 ] for some random variables {R(𝑘, 𝑥) ∈ C}𝑘∈[𝐾],𝑥∈[𝑁 ] . In the oracle state search game, the challenger samples 𝑅 together with a uniformly random key 𝑘 ∈ [𝐾], gives the adversary one copy of |𝜓𝑅,𝑘 ⟩, and the adversary must output 𝑘 after making one oracle query. The oracle can depend on the variable 𝑅 but not on 𝑘. Definition 4.2 (One-query search adversary). A one-query adversary for the search game is specified by • a pre-query isometry 𝑉 : C𝑁 → C𝑀 , and • a projective measurement {Π𝑘 }𝑘∈[𝐾] on the 𝑀 -dimensional post-query space. For a fixed oracle 𝑂𝑓 , the adversary applies 𝑉 , makes one query to 𝑂𝑓 , and then measures with {Π𝑘 }𝑘∈[𝐾] . It is shown in [LMW24] (Corollary 3.34) that this normal form is without loss of generality, where log(𝑀 ) ≤ 𝑛 + ℓ + log 𝐾 for ℓ equal to the length of the adversary’s oracle query. Definition 4.3 (Adversary’s winning probability). For a fixed state family defined by 𝑅, the adversary’s winning probability is 1 ∑︁ Win(𝒜 | 𝑅) := max ⟨𝜓𝑅,𝑘 | 𝑉 † 𝑂𝑓† Π𝑘 𝑂𝑓 𝑉 |𝜓𝑅,𝑘 ⟩ . 𝑓 𝐾 𝑘∈[𝐾] There are two related notions of hardness of the oracle state search game. Definition 4.4 ((𝑀, 𝜀)-hardness in expectation). We say that the one-query oracle state search game is (𝑀, 𝜀)-hard in expectation over a random variable 𝑅 if for all 𝑡-query adversaries acting on a Hilbert space of dimension 𝑀 , [︁
]︁
E𝑅 Win(𝒜 | 𝑅) ≤ 𝜀. Definition 4.5 ((𝑀, 𝜀, 𝛿)-hardness). We say that the one-query oracle state search game is (𝑀, 𝜀, 𝛿)hard over a random variable 𝑅 if for all 𝑡-query adversaries acting on a Hilbert space of dimension 𝑀, [︁ ]︁ Pr𝑅 Win(𝒜 | 𝑅) > 𝜀 ≤ 𝛿. Of particular interest to us is the case where the states { |𝜓𝑅,𝑘 ⟩} are orthogonal, meaning that |𝜓𝑅,𝑘 ⟩ = 𝑈𝑅 |𝑘⟩ for some unitary 𝑈𝑅 depending on 𝑅. In this case, we observe in Appendix B that the Haar-random distribution on 𝑈𝑅 is “the hardest instance” of the oracle search game: if any distribution on 𝑈𝑅 is (𝑀, 𝜀)-hard (respectively, (𝑀, 𝜀, 𝛿)-hard), then so is the Haar distribution. 18
4.1
Relationship to Unitary Synthesis
In this subsection, we assume that for every 𝑅, the states |𝜓𝑅,𝑘 ⟩ 𝑘∈[𝐾] are mutually orthogonal. Similar implications hold in relaxed settings where the states are only approximately orthogonal, but the orthogonal case is all that we will need in this paper. We first formally state the fact that hardness of the oracle state search game implies the hardness of unitary synthesis. {︀
}︀
Lemma 4.6 (Search hardness implies synthesis hardness). For any given 𝑅, let 𝑈𝑅 be any unitary satisfying 𝑈𝑅 |𝜓𝑅,𝑘 ⟩ = |𝑘⟩ for all 𝑘 ∈ [𝐾]. If there exists a 𝑡-query oracle circuit 𝒜(·) that synthesizes the family {𝑈𝑅 }𝑅 with aux-input correctness 𝜂, then there exists a 𝑡-query search adversary whose winning probability in the oracle state search game is at least 𝜂 for every 𝑅. In particular, if every 𝑡-query search adversary has expected winning probability at most 𝛿, then no 𝑡-query oracle circuit can synthesize the family {𝑈𝑅 }𝑅 with aux-input correctness greater than 𝛿. Proof. Fix a choice of 𝑅. Let 𝒜(·) be a 𝑡-query synthesis algorithm for 𝑈𝑅 , and let 𝑓𝑅 be an oracle witnessing aux-input correctness 𝜂 for this unitary. Write the corresponding circuit using the normal form from Definition 3.2: it makes queries to oracle 𝑂𝑓𝑅 , interleaved with fixed unitaries (𝑈1 , ..., 𝑈𝑡+1 ). Partition the computational basis of the designated 𝑛-qubit output register into 𝐾 disjoint sets 𝑆𝑘 so that 𝑘 ∈ 𝑆𝑘 for every 𝑘 ∈ [𝐾]; for instance, one may take 𝑆𝑘 = {𝑘} for 𝑘 ̸= 0 and 𝑆0 = {0} ∪ ([𝑁 ] ∖ [𝐾]). Define projectors ⎞
⎛ † ⎝ Π𝑘 := 𝑈𝑡+1
∑︁
|𝑗⟩⟨𝑗| ⊗ I⎠ 𝑈𝑡+1
for 𝑘 ∈ [𝐾].
𝑗∈𝑆𝑘
Then {Π𝑘 }𝑘∈[𝐾] is a projective measurement on the full workspace, and hence defines a 𝑡-query search adversary: run 𝒜𝑓𝑅 , except that just after the 𝑡-th query, apply measurement {Π𝑘 }𝑘∈[𝐾] (instead of post-query unitary 𝑈𝑡+1 ). Now fix any key 𝑘 ∈ [𝐾] and feed the search adversary the challenge state |𝜓𝑅,𝑘 ⟩. By correctness, the reduced output state has fidelity at least 𝜂 with the pure state |𝑘⟩. Since fidelity against a pure state equals the corresponding overlap, the probability that the output register lands in the set 𝑆𝑘 is at least 𝜂. Therefore measuring the full workspace with {Π𝑘 }𝑘∈[𝐾] outputs 𝑘 with probability at least 𝜂. Averaging over the uniformly random key gives winning probability at least 𝜂 for this fixed 𝑅. Moreover, we observe in Section 4.3, the hardness of the oracle state search game also implies non-trivial forms of quantum cryptography.
4.2
The Oracle Choi State Game
In this section, we introduce what we consider to be the weakest natural formulation of average-case hardness of unitary synthesis, which we call the oracle Choi state game.
19
Definition 4.7 (Oracle Choi state game). Fix a random variable R and a family of unitary {𝑈𝑅 }𝑅∈R defined by R. In the oracle Choi state game, the challenger samples 𝑅 and prepares the following Choi state of unitary 𝑈𝑅 on register 𝐻 and 𝐴: ∑︁ 1 |Ψ𝑅 ⟩ = √ |𝑘⟩𝐻 ⊗ 𝑈𝑅 |𝑘⟩𝐴 . 𝑁 𝑘∈{0,1}𝑛
Then it sends register 𝐴 to the adversary, keeping register 𝐻 hidden. The adversary will perform some computation on register 𝐴, by making queries to an oracle that might depend arbitrarily on 𝑅. After that, the challenger will apply a projective measurement { |ΨEPR ⟩⟨ΨEPR | , 𝐼 − |ΨEPR ⟩⟨ΨEPR |} ∑︀ on register 𝐻 and 𝐴, for |ΨEPR ⟩ := √1𝑁 𝑘∈{0,1}𝑛 |𝑘⟩𝐻 ⊗ |𝑘⟩𝐴 . The adversary wins the game if and only if the measurement outcome is accepting. Similarly to the case of the oracle state search game, we also describe a canonical form for one-query adversaries in the Choi state game. Definition 4.8 (One-query Choi adversary). A one-query adversary for the oracle Choi state game is specified by • a pre-query isometry 𝑉 : C𝑁 → C𝑀 , and • a post-query unitary 𝑈 : C𝑀 → C𝑀 on the 𝑀 -dimensional post-query space. For a fixed oracle 𝑂𝑓 , the adversary applies 𝑉 (which maps register 𝐴 to a larger register 𝐴𝐴′ ), makes one query to 𝑂𝑓 , and then applies 𝑈 . It is shown in [LMW24] (Corollary 3.34) that this normal form is without loss of generality, where log(𝑀 ) ≤ 𝑛 + ℓ + 1 for ℓ as the length of the adversary’s oracle query. Definition 4.9 (Adversary’s winning probability). For a fixed unitary 𝑈𝑅 defined by 𝑅, the adversary’s winning probability in the oracle Choi state game is ⃦ ⎞⃦2 ⎛ ⃦ ⃦ ∑︁ ⃦ ⃦ 1 ⎝ ⃦ ⎠ √ Π Win(𝒜 | 𝑅) := max ⃦ |𝑘⟩ ⊗ 𝑈 · 𝑂 · 𝑉 · 𝑈 |𝑘⟩ 𝑅 EPR 𝑓 ⃦ ⃦ 𝑓 ⃦ 𝑁 𝑘∈{0,1}𝑛 ⃦
where ΠEPR := |ΨEPR ⟩⟨ΨEPR | ⊗ 𝐼𝐴′ . Relationship to Unitary Synthesis. We observe that if the oracle Choi state game is hard for some class of adversaries, then worst-case unitary synthesis is hard for the same class of adversaries. Lemma 4.10 (Choi state game hardness implies synthesis hardness). If there exists an oracle circuit 𝒜(·) that synthesizes the family {𝑈𝑅† }𝑅 with aux-input correctness 𝜂 within 𝑡 queries, then there exists a 𝑡-query Choi adversary whose winning probability in the Choi state game is at least 𝜂 for every 𝑅. In particular, if every 𝑡-query Choi adversary has expected winning probability at most 𝛿, then no 𝑡-query oracle circuit can synthesize the family {𝑈𝑅† }𝑅 with aux-input correctness greater than 𝛿.
20
Proof. Fix a choice of 𝑅. Let 𝒜(·) be a 𝑡-query synthesis algorithm for 𝑈𝑅† , and let 𝑓𝑅 be an oracle witnessing aux-input correctness 𝜂 for this unitary. Write the corresponding circuit using the normal form from Definition 3.2: it makes queries to oracle 𝑂𝑓𝑅 , interleaved with fixed unitaries (𝑈1 , ..., 𝑈𝑡+1 ). This (𝑈1 , ..., 𝑈𝑡+1 ) and choice of 𝑓𝑅 actually define a 𝑡-query Choi adversary. By the aux-input correctness, the output state (together with the hidden state as the auxiliary state) has fidelity at least 𝜂 with the pure state |ΨEPR ⟩. That is, the 𝑡-query Choi adversary will win with probability at least 𝜂. In fact, the oracle Choi state game has a natural interpretation as measuring the Haar-average input correctness of a unitary-synthesis procedure. For fixed 𝑅 and oracle 𝑓 , let ℰ𝑅,𝑓 denote the channel implemented by the adversary 𝒜𝑓 on register 𝐴, after tracing out any workspace or ancilla. Since the adversary attempts to undo 𝑈𝑅 on register 𝐴 in the Choi state game, here we consider synthesizing 𝑈𝑅† . Its Haar-average correctness is naturally defined as (︁
)︁
𝜂𝑅,𝑓 := E|𝜓⟩←Haar ⟨𝜓| ℰ𝑅,𝑓 𝑈𝑅 |𝜓⟩⟨𝜓| 𝑈𝑅† |𝜓⟩ . Define Λ𝑅,𝑓 (𝜌) := ℰ𝑅,𝑓 (𝑈𝑅 𝜌𝑈𝑅† ), ΦEPR := |ΨEPR ⟩⟨ΨEPR |, we have ⟨𝜓| Λ𝑅,𝑓 ( |𝜓⟩⟨𝜓|) |𝜓⟩ = 𝑁 · Tr
[︁(︁
)︁
]︁
( |𝜓⟩⟨𝜓|)T ⊗ |𝜓⟩⟨𝜓| (I ⊗ Λ𝑅,𝑓 )(ΦEPR ) .
·ΦEPR Using the Haar second-moment identity E|𝜓⟩←Haar [( |𝜓⟩⟨𝜓|)T ⊗ |𝜓⟩⟨𝜓|] = 𝐼+𝑁 𝑁 (𝑁 +1) , we obtain
𝜂𝑅,𝑓 =
1 + 𝑁 · Tr [ΦEPR (I ⊗ Λ𝑅,𝑓 )(ΦEPR )] 𝑁 +1
where we used Tr((I ⊗ Λ𝑅,𝑓 )(ΦEPR )) = 1. The trace term above is exactly the winning probability in the oracle Choi state game with oracle 𝑓 . Therefore, maximizing over 𝑓 gives Win(𝒜 | 𝑅) =
(𝑁 + 1) max𝑓 𝜂𝑅,𝑓 − 1 . 𝑁
Thus, the Choi-game winning probability is an affine rescaling of the best Haar-average correctness for adversary 𝒜 to synthesize 𝑈𝑅† . Relationship to the Oracle State Search Game. In this part, we will show that the search hardness implies the Choi state game hardness. Note that every unitary 𝑈𝑅 naturally defines state family as {𝑈𝑅 𝑊 |𝑘⟩}𝑘∈{0,1}𝑛 for some fixed unitary 𝑊 : C𝑁 → C𝑁 . In fact, the oracle Choi state game can be viewed as a coherent search game on state family ∑︀ {𝑈𝑅 |𝑘⟩}𝑘 , trying to coherently map 𝑈𝑅 |𝑘⟩ back to |𝑘⟩ on register 𝐴, as mapping 𝑘 |𝑘⟩𝐻 ⊗𝑈𝑅 |𝑘⟩𝐴 ∑︀ back to 𝑘 |𝑘⟩𝐻 ⊗ |𝑘⟩𝐴 in the oracle Choi state game. Lemma 4.11 (Search hardness implies Choi state game hardness). If there exists a 𝑡-query Choi adversary 𝒜(·) that wins the oracle Choi state game on unitary family {𝑈𝑅 }𝑅 with winning probability 𝜂, then for every fixed unitary 𝑊 : C𝑁 → C𝑁 , for state family { |𝜓𝑅,𝑘 ⟩ := 𝑈𝑅 𝑊 |𝑘⟩}, there exists a 𝑡-query search adversary whose expected winning probability in the oracle state search game is at least 𝜂. 21
That is, if for some fixed unitary 𝑊0 : C𝑁 → C𝑁 with correspondingly defined state family { |𝜓𝑅,𝑘 ⟩ : 𝑈𝑅 𝑊0 |𝑘⟩}, every 𝑡-query search adversary has expected winning probability at most 𝛿, then no 𝑡-query Choi adversary can win the oracle Choi state game on unitary family {𝑈𝑅 }𝑅 with expected winning probability greater than 𝛿. Proof. Fix a family of {𝑈𝑅 }𝑅 . Let 𝒜(·) be a 𝑡-query Choi adversary for {𝑈𝑅 }𝑅 , and let 𝑓𝑅 be an oracle witnessing correctness 𝜂𝑅 for this unitary with 𝜂 = E𝑅 𝜂𝑅 . Write the corresponding circuit using the normal form from Definition 3.2: it makes queries to oracle 𝑂𝑓𝑅 , interleaved with fixed unitaries (𝑈1 , ..., 𝑈𝑡+1 ). For fixed unitary 𝑊 : C𝑁 → C𝑁 and state family { |𝜓𝑅,𝑘 ⟩ := 𝑈𝑅 𝑊 |𝑘⟩}, define projectors (︁
)︁
† Π𝑘 := 𝑈𝑡+1 · 𝑊 |𝑘⟩⟨𝑘| 𝑊 † ⊗ I𝐴′ · 𝑈𝑡+1
for 𝑘 ∈ {0, 1}𝑛
Then {Π𝑘 }𝑘∈{0,1}𝑛 is a projective measurement on the full workspace, and hence defines a 𝑡-query search adversary: run 𝒜𝑓𝑅 , except that just after the 𝑡-th query, apply measurement {Π𝑘 }𝑘∈[𝐾] (instead of post-query unitary 𝑈𝑡+1 ). For a random 𝑘 ← {0, 1}𝑛 , the search adversary winning probability can be written as (define 𝑓𝑅 := 𝑂𝑓𝑅 · 𝑈𝑡 · · · 𝑂𝑓𝑅 · 𝑈1 , as the part of the algorithm just after 𝑡 queries): 𝑈1→𝑡 ⃦2 ⃦
⃦ ⃦
𝑓𝑅 E𝑘∈{0,1}𝑛 ⃦Π𝑘 · 𝑈1→𝑡 · ( |𝜓𝑅,𝑘 ⟩ ⊗ |0𝑚−𝑛 ⟩)⃦
⃦2 ⃦ ⃦ ⃦ ∑︁ ⃦ ⃦ 1 𝑓𝑅 𝑚−𝑛 ⃦ √ · (𝑈 𝑊 |𝑘⟩ ⊗ |0 ⟩) |𝑘⟩ ⊗ Π · 𝑈 =⃦ 𝑅 𝑘 1→𝑡 ⃦ ⃦ ⃦ ⃦ 𝑁 𝑘∈{0,1}𝑛 ⃦(︃ ⃦2 )︃ ⃦ ∑︁ ⃦ 1 ∑︁ ⃦ 𝑓𝑅 † 𝑚−𝑛 ⃦ =⃦ |𝑘⟩⟨𝑘| ⊗ 𝑊 |𝑘⟩⟨𝑘| 𝑊 ⊗ I𝐴′ √ ⟩)⃦ |𝑘⟩ ⊗ 𝑈𝑡+1 · 𝑈1→𝑡 · (𝑈𝑅 𝑊 |𝑘⟩ ⊗ |0 ⃦ ⃦ 𝑁 𝑘 𝑘 ⃦ ⃦2 ⃦(︁ ⃦ )︁ 1 ∑︁ ⃦ 𝑓𝑅 † 𝑚−𝑛 ⃦ ≥ ⃦ (I ⊗ 𝑊 ) |ΨEPR ⟩⟨ΨEPR | (I ⊗ 𝑊 ) ⊗ I𝐴′ · √ ⟩)⃦ |𝑘⟩ ⊗ 𝑈𝑡+1 · 𝑈1→𝑡 · (𝑈𝑅 𝑊 |𝑘⟩ ⊗ |0 ⃦ ⃦ 𝑁 𝑘 ⃦ ⃦2 ⃦ ⃦ 1 ∑︁ ⃦ ⃦ 𝑓𝑅 = ⃦⟨ΨEPR | (𝑊 * ⊗ I) · √ |𝑘⟩ ⊗ 𝑈𝑡+1 · 𝑈1→𝑡 · (𝑈𝑅 𝑊 |𝑘⟩ ⊗ |0𝑚−𝑛 ⟩)⃦ ⃦ ⃦ 𝑁 𝑘 ⃦ ⃦2 ⃦ ⃦ 1 ∑︁ ⃦ 𝑚−𝑛 ⃦ = ⃦⟨ΨEPR | · √ |𝑘⟩ ⊗ 𝑈𝑡+1 · 𝑂𝑓𝑅 · 𝑈𝑡 · · · 𝑂𝑓𝑅 · 𝑈1 · (𝑈𝑅 |𝑘⟩ ⊗ |0 ⟩)⃦ . ⃦ ⃦ 𝑁 𝑘
By the winning definition of the oracle Choi state game, for fixed 𝑅 this is at least 𝜂𝑅 . This means that for fixed 𝑅, the 𝑡-query search adversary can win with probability at least 𝜂𝑅 . Averaging over 𝑅, this will give expected winning probability in the oracle state search game at least 𝜂.
4.3
Relationship to Quantum Cryptography
We conclude this section by explaining how hardness of the oracle state search game and the Choi state game gives rise to quantum-cryptographic primitives. In particular, their hardness will imply the security of a quantum bit commitment scheme.
22
From the Choi game. The oracle Choi state game can also be viewed as the task of breaking the binding security of the following commitment scheme (relative to R): 1 ∑︁ |Ψ0 ⟩ := |ΨEPR ⟩ = √ |𝑘⟩𝐻 ⊗ |𝑘⟩𝐴 , 𝑁 𝑘 1 ∑︁ |𝑘⟩𝐻 ⊗ 𝑈𝑅 |𝑘⟩𝐴 . |Ψ1 ⟩ := |Ψ𝑅 ⟩ = √ 𝑁 𝑘 To commit to bit 𝑏, the sender prepares |Ψ𝑏 ⟩ (note that one does not need to synthesize 𝑈𝑅 to prepare |Ψ1 ⟩; synthesizing a state can be easier [Ros24]). Then it sends register 𝐻 to the receiver. To open the commitment, the sender announces 𝑏 and sends register 𝐴. This commitment scheme is perfectly hiding. For binding security (see [Yan22, BCQ23, GJMZ23] for discussion), an adversarial sender that starts from an honestly generated commitment |Ψ1 ⟩, acts only on register 𝐴 and successfully opens it as a commitment to 0 as |Ψ0 ⟩, is exactly an adversary for the oracle Choi state game. Therefore, hardness of the oracle Choi state game implies the security of the above perfectly-hiding computationally-binding quantum bit commitment scheme. From the search game. By Lemma 4.11, hardness of the oracle state search game implies hardness of the corresponding oracle Choi state game. Therefore, hardness of the oracle state search game also implies quantum bit commitment through the construction similar as above: 1 ∑︁ |Ψ0 ⟩ := |ΨEPR ⟩ = √ |𝑘⟩𝐻 ⊗ |𝑘⟩𝐴 , 𝑁 𝑘 1 ∑︁ |𝑘⟩𝐻 ⊗ |𝜓𝑅,𝑘 ⟩𝐴 . |Ψ1 ⟩ := √ 𝑁 𝑘
5
Main Theorems
In this section, we formally state (or re-state) the results that were outlined in the introduction. Theorem 5.1 (Permutation family search bound). Let 𝑃 be the in-place permutation unitary associated with a uniformly random permutation 𝜋 on {0, 1}𝑛 , and consider the search game for the state family {𝑃 𝐻 |𝑘⟩}𝑘∈[𝐾]∖{0} . Then every one-query adversary with workspace dimension 𝑀 satisfies (︃ )︃ [︀ ]︀ log2 𝑀 log2 𝐾 E𝜋 Win(𝒜 | 𝜋) = 𝑂 . 𝐾 Theorem 5.2 (𝐹2 𝐻𝐹1 𝐻 search bound). Let 𝑓1 , 𝑓2 : {0, 1}𝑛 → {0, 1} be uniformly random Boolean ∑︀ functions, and let 𝐹𝑗 = 𝑥 (−1)𝑓𝑗 (𝑥) |𝑥⟩⟨𝑥| for 𝑗 ∈ {1, 2}. For the search game on the family {𝐹2 𝐻𝐹1 𝐻 |𝑘⟩}𝑘∈[𝐾] , every one-query adversary with workspace dimension 𝑀 satisfies E𝑓1 ,𝑓2 Win(𝒜 | 𝑓1 , 𝑓2 ) = 𝑂 [︀
]︀
(︂
log 𝑀 · log(𝑀 𝑁 ) . 𝐾 )︂
Corollary 5.3 (𝐹𝑡 𝐻𝐹𝑡−1 𝐻 · · · 𝐹2 𝐻𝐹1 search bound). Let 𝑓1 , . . . , 𝑓𝑡 : {0, 1}𝑛 → {0, 1} be uniformly ∑︀ random Boolean functions, and let 𝐹𝑗 = 𝑥 (−1)𝑓𝑗 (𝑥) |𝑥⟩⟨𝑥| for 𝑗 ∈ {1, . . . , 𝑡}. For the search 23
game on the family {𝐹𝑡 𝐻𝐹𝑡−1 𝐻 · · · 𝐹2 𝐻𝐹1 𝐻 |𝑘⟩}𝑘∈[𝐾] , every one-query adversary with workspace dimension 𝑀 satisfies log 𝑀 · log(𝑀 𝑁 ) E𝑓1 ,...,𝑓𝑡 Win(𝒜 | 𝑓1 , . . . , 𝑓𝑡 ) = 𝑂 . 𝐾 [︀
]︀
(︂
)︂
Theorem 5.4 (One-query distinguishing attack for a structured subset of 𝑃 𝐻 |𝑘⟩). There exists a one-query adversary 𝒜 such that for every in-place permutation unitary 𝑃 there is a classical oracle 𝑓𝜋 for which 𝒜𝑓𝜋 distinguishes the ensemble {𝑃 𝐻 |𝑘⟩}𝑘∈[2𝑛/2 ] from Haar-random input with constant advantage. Theorem 5.5 (Constant-correctness synthesis for phase unitaries). For phase unitaries of the ∑︀ form 𝐷(𝐹 ) = 𝑥 𝛼(𝑥) · |𝑥⟩⟨𝑥|, there is a one-query synthesis algorithm with constant correctness (Definition 3.6). In the special case of 𝛼(𝑥) ∈ {1, 𝑖, −1, −𝑖}, the achieved correctness is at least 1/2; for the general case, the achieved correctness is at least 1/4. Corollary 5.6. Any family of unitaries with a (3/4+𝜀) correct 1-query unitary synthesis algorithm relative to the class of complex phase unitaries also has an Ω(𝜀2 )-correct 1-query unitary synthesis algorithm relative to binary phase unitaries (or Boolean functions). Theorem 5.7 (Quantum-advice lower bound for 𝐹 𝐻 |𝑘⟩). Let 𝑓 : {0, 1}𝑛 → {0, 1} be uniformly ∑︀ random and let 𝐹 = 𝑥 (−1)𝑓 (𝑥) |𝑥⟩⟨𝑥|. Suppose a (zero-query) non-uniform algorithm uses 𝑆 qubits of advice depending on 𝑓 and outputs 𝑘 from one copy of 𝐹 𝐻 |𝑘⟩ with success probability 𝜀. Then 𝜀𝑡 ≤ 2𝑆
(︂
8𝑡 𝑁
)︂𝑡
for every integer 𝑡 ≥ 1.
In particular, setting 𝑡 = 𝑆 gives 𝜀 ≤ 16𝑆/𝑁 .
6
A Generic Search Reduction
In this section, we generically reduce the problem of upper bounding E[Win(𝒜 | 𝑅)] to the calcula𝑅
tion of the expected (squared) spectral norm of a random matrix. We require only mild assumptions on the distribution over 𝑅: • For the first step, we require only that E𝑅 |𝜓𝑅,𝑘 ⟩⟨𝜓𝑅,𝑘 | is independent of 𝑘. • For the second step, we require that E𝑅 |𝜓𝑅,𝑘 ⟩⟨𝜓𝑅,𝑘 | is maximally mixed over a linear subspace of C𝑁 .
6.1
Generic spectral relaxation under identical marginals
We now utilize the weight-vector decomposition from Section 3.3 to analyze the search game from Section 4. Lemma 6.1 (Generic spectral relaxation). Assume that for each 𝑘 ∈ [𝐾], the mixed state E𝑅 |𝜓𝑅,𝑘 ⟩⟨𝜓𝑅,𝑘 | is independent of 𝑘. Let 𝒜 = (𝑉, {Π𝑘 }𝑘∈[𝐾] ) be a one-query adversary for the search game, and let (R,𝑘)
𝐷𝑉,𝑅,𝑘 := 𝐷𝑉,𝜓𝑅,𝑘 24
be the diagonal matrix from Lemma 3.10, formed using the distribution on |𝜓R,𝑘 ⟩ for a random choice of R. Define 1 ∑︁ 𝑀𝑅 := √ Π𝑘 𝐷𝑉,𝑅,𝑘 . 𝐾 𝑘∈[𝐾] Then, for every 𝑅, Win(𝒜 | 𝑅) ≤ ‖𝑀𝑅 ‖2 . Consequently, E Win(𝒜 | 𝑅) ≤ E‖𝑀𝑅 ‖2 . [︀
]︀
𝑅
𝑅
Proof. Fix 𝑅. By Lemma 3.10, 𝑉 |𝜓𝑅,𝑘 ⟩ = 𝐷𝑉,𝑅,𝑘 |wt𝑉,R,𝑘 ⟩
for each 𝑘 ∈ [𝐾].
By our assumption that ER |𝜓R,𝑘 ⟩⟨𝜓R,𝑘 | is independent of 𝑘, we see that |wt𝑉,R,𝑘 ⟩ = |wt𝑉 ⟩ is independent of 𝑘. Hence Win(𝒜 | 𝑅) = max 𝑓
1 ∑︁ † 𝑂𝑓† Π𝑘 𝑂𝑓 𝐷𝑉,𝑅,𝑘 |wt𝑉 ⟩ ⟨wt𝑉 | 𝐷𝑉,𝑅,𝑘 𝐾 𝑘∈[𝐾] ⎛
1 = max ⟨wt𝑉 | 𝑂𝑓† ⎝ 𝑓
⎞ ∑︁
𝐾 𝑘∈[𝐾]
† 𝐷𝑉,𝑅,𝑘 Π𝑘 𝐷𝑉,𝑅,𝑘 ⎠ 𝑂𝑓 |wt𝑉 ⟩
⃦ ⃦ ⃦ ⃦ ⃦ 1 ∑︁ ⃦ † ⃦ ≤⃦ 𝐷𝑉,𝑅,𝑘 Π𝑘 𝐷𝑉,𝑅,𝑘 ⃦ ⃦ ⃦ 𝐾 𝑘∈[𝐾] ⃦ ⃦⎛ ⎞⎛ ⎞⃦ ⃦ ⃦ ∑︁ ∑︁ ⃦ ⃦ 1 1 † ⃦ ⎝ ⎠ ⎝ ⎠ √ =⃦ √ 𝐷𝑉,𝑅,𝑘 Π𝑘 Π𝑘 𝐷𝑉,𝑅,𝑘 ⃦ ⃦ 𝐾 𝑘∈[𝐾] 𝐾 𝑘∈[𝐾] ⃦ ⃦ ⃦ ⃦ ⃦ ⃦ = ⃦𝑀𝑅† 𝑀𝑅 ⃦ = ‖𝑀𝑅 ‖2 .
Averaging over 𝑅 gives the final inequality.
6.2
Description of 𝑀𝑅 for subspace-uniform state families
Our applications will rely on Lemma 6.1 in a more concrete setting: the challenge state distribution is, in expectation, maximally mixed on a fixed subspace. In this case, there is a simple description of the random matrix 𝑀𝑅 . Lemma 6.2. Assume the hypotheses of Lemma 6.1. In addition, suppose there is a subspace 𝑆 ⊆ C𝑁 of dimension 𝐿 with projector Π𝑆 such that for every 𝑘 ∈ [𝐾], E |𝜓𝑅,𝑘 ⟩⟨𝜓𝑅,𝑘 | = [︀
]︀
𝑅
Let |𝑣̃︀𝑖 ⟩ := Π𝑆 |𝑣𝑖 ⟩ and 𝑝𝑖 :=
1 Π𝑆 𝐿
‖ |𝑣̃︀𝑖 ⟩‖2 . 𝐿 25
Then 𝑀𝑅 =
∑︁
𝑅(𝑘, 𝑥) 𝐵𝑘,𝑥 ,
𝑘∈[𝐾], 𝑥∈[𝑁 ]
where 𝐵𝑘,𝑥 := √
∑︁ 1 ⟨𝑣̃︀𝑖 |𝑥⟩ √ Π𝑘 |𝑖⟩⟨𝑖| , 𝑁 𝐾 𝑖∈[𝑀 ]: 𝑝𝑖 >0 𝑝𝑖
and these matrices satisfy † 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⪯
𝐿 I, 𝑁𝐾
(1)
† 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⪯
𝐿 I. 𝑁𝐾
(2)
𝐵𝑘†1 ,𝑥 𝐵𝑘2 ,𝑦 = 0 for 𝑘1 ̸= 𝑘2
(3)
∑︁ 𝑘,𝑥
∑︁ 𝑘,𝑥
Proof. Fix 𝑘 ∈ [𝐾]. By assumption, E |𝜓𝑅,𝑘 ⟩⟨𝜓𝑅,𝑘 | = [︀
]︀
𝑅
1 Π𝑆 . 𝐿
Hence
‖Π𝑆 |𝑣𝑖 ⟩‖2 ‖ |𝑣̃︀𝑖 ⟩‖2 1 Π𝑆 |𝑣𝑖 ⟩ = = = 𝑝𝑖 . 𝑅 𝐿 𝐿 𝐿 Moreover, because every challenge state lies in 𝑆, we have E |⟨𝑣𝑖 |𝜓𝑅,𝑘 ⟩|2 = ⟨𝑣𝑖 | [︀
]︀
)︂
(︂
⟨𝑣𝑖 |𝜓𝑅,𝑘 ⟩ = ⟨𝑣̃︀𝑖 |𝜓𝑅,𝑘 ⟩
for all 𝑅, 𝑘.
Therefore 𝐷𝑉,𝑅,𝑘 =
⟨𝑣̃︀𝑖 |𝜓𝑅,𝑘 ⟩ |𝑖⟩⟨𝑖| √ 𝑝𝑖 𝑖∈[𝑀 ]: 𝑝 >0 ∑︁
𝑖
∑︁ ∑︁ 1 ⟨𝑣̃︀𝑖 |𝑥⟩ 𝑅(𝑘, 𝑥) √ |𝑖⟩⟨𝑖| . =√ 𝑝𝑖 𝑁 𝑖∈[𝑀 ]: 𝑝𝑖 >0 𝑥∈[𝑁 ]
Substituting this into the definition of 𝑀𝑅 yields 1 ∑︁ 𝑀𝑅 = √ Π𝑘 𝐷𝑉,𝑅,𝑘 𝐾 𝑘∈[𝐾] ⎛
⎞
∑︁ 1 ⟨𝑣̃︀𝑖 |𝑥⟩ = 𝑅(𝑘, 𝑥) ⎝ √ √ Π𝑘 |𝑖⟩⟨𝑖|⎠ 𝑝𝑖 𝑁 𝐾 𝑘∈[𝐾], 𝑥∈[𝑁 ] 𝑖∈[𝑀 ]: 𝑝𝑖 >0 ∑︁
=
∑︁
𝑅(𝑘, 𝑥)𝐵𝑘,𝑥 .
𝑘,𝑥
It remains to prove (1) and (2). For the first bound, ⎛
∑︁ 𝑘,𝑥
† 𝐵𝑘,𝑥 𝐵𝑘,𝑥 =
1 Π𝑘 ⎝ 𝑁 𝐾 𝑘,𝑥 𝑖∈[𝑀 ]: 𝑝 >0 ∑︁
∑︁
|⟨𝑣̃︀𝑖 |𝑥⟩|2 𝑝𝑖
𝑖
26
⎞
|𝑖⟩⟨𝑖|⎠ Π𝑘
⎞
⎛
∑︁ 1 ∑︁ ‖ |𝑣̃︀𝑖 ⟩‖2 = |𝑖⟩⟨𝑖|⎠ Π𝑘 Π𝑘 ⎝ 𝑁 𝐾 𝑘∈[𝐾] 𝑝 𝑖 𝑖∈[𝑀 ]: 𝑝 >0 𝑖
⎛
⎞
∑︁ 1 ∑︁ 𝐿 𝐿 ∑︁ = Π𝑘 ⎝ Π𝑘 = · I. 𝐿 |𝑖⟩⟨𝑖|⎠ Π𝑘 ⪯ 𝑁 𝐾 𝑘∈[𝐾] 𝑁 𝐾 𝑘∈[𝐾] 𝑁𝐾 𝑖∈[𝑀 ]: 𝑝 >0 𝑖
For the second bound, ⎛
⎞⎛
⎞
∑︁ ∑︁ ⟨𝑥|𝑣̃︀𝑖1 ⟩ 1 ∑︁ ⎝ ⟨𝑣̃︀𝑖2 |𝑥⟩ † |𝑖1 ⟩⟨𝑖1 | Π𝑘 ⎠ ⎝ Π𝑘 |𝑖2 ⟩⟨𝑖2 |⎠ 𝐵𝑘,𝑥 𝐵𝑘,𝑥 = √ √ 𝑁 𝐾 𝑘,𝑥 𝑖 ∈[𝑀 ]: 𝑝 >0 𝑝𝑖1 𝑝 𝑖 2 𝑘,𝑥 𝑖 ∈[𝑀 ]: 𝑝 >0
∑︁
1
2
𝑖1
𝑖2
2
⪯
1 |⟨𝑣̃︀𝑖 |𝑥⟩| |𝑖⟩⟨𝑖| 𝑁 𝐾 𝑘,𝑥 𝑖∈[𝑀 ]: 𝑝 >0 𝑝𝑖 ∑︁
∑︁
𝑖
=
∑︁ 1 ‖ |𝑣̃︀𝑖 ⟩‖2 𝐿 I. |𝑖⟩⟨𝑖| ⪯ 𝑁 𝐾 𝑖∈[𝑀 ]: 𝑝 >0 𝑝𝑖 𝑁𝐾 𝑖
For the third identity, note that 𝐵𝑘,𝑥 = Π𝑘 𝐵𝑘,𝑥 for all 𝑘, 𝑥 and that Π𝑘1 Π𝑘2 = 0 for 𝑘1 ̸= 𝑘2 . Theorems 5.1 and 5.2 (as well as Theorems A.1 and A.4) prove upper bounds on the search game win probability by invoking Lemmas 6.1 and 6.2, and then upper bounding E[‖𝑀𝑅 ‖2 ]. 𝑅
7
One-query lower bound for permutation unitaries
In this section, we analyze the permutation state family {𝑃 𝐻 |𝑘⟩}𝑘 , for the permutation unitary 𝑃 associated with a uniformly random permutation 𝜋, 𝑃 : |𝑥⟩ ↦→ |𝜋(𝑥)⟩. We will first give a one-query algorithm for a distinguishing game for this state family in Section 7.1. This motivates our focus on the oracle state search game, with the formulation in Section 7.2. We then prove the one-query lower bound by analyzing the oracle state search game. The analysis proceeds by first writing the relevant random matrix as a combinatorial matrix sum over permutations in Section 7.3, computing variance parameters for this sum in Section 7.4, and applying the matrix Bernstein inequality for combinatorial matrix sums [MJC+ 14] in Section 7.5. By invoking the appropriate matrix tail inequalities, we also prove a classical advice lower bound for non-uniform one-query algorithms in Section 7.6.
7.1
A one-query distinguishing attack
We consider the task of distinguishing a single copy of a phase state generated by an in-place permutation (applied to a fixed subspace of phase states in C𝑁 ) from a Haar random state. This distinguishing game is played as follows. 1. The challenger samples a permutation 𝜋 over {0, 1}𝑛 together with a random bit 𝑏 ∈ {0, 1}. 2. The challenger generates and sends to the adversary one copy of a state |𝜓⟩: • If 𝑏 = 0, the challenger samples a uniformly random key 𝑘 ∈ [𝐾] ⊂ [𝑁 ], and gives the adversary one copy of |𝜓⟩ = 𝑃 𝐻 |𝑘⟩ (unitary 𝑃 is defined by 𝜋, 𝑃 : |𝑥⟩ ↦→ |𝜋(𝑥)⟩). 27
• If 𝑏 = 1, the challenger samples a uniformly random 𝑥 ∈ [𝑁 ] and gives the adversary one copy of |𝜓⟩ = |𝑥⟩. 3. The adversary is asked to output 𝑏 after making one oracle query, where the oracle can depend only on 𝜋. This is similar to the oracle state distinguishing game in [LMW24, Definition 3.8], where the adversary wishes to distinguish a single copy of a random binary phase state { |𝜓𝑅𝑘 ⟩}𝑘 from Haar random. While our eventual goal is to show that synthesizing in-place permutations is infeasible, we first prove that for states generated by in-place permutation unitaries, winning the one-query distinguishing game can be easy! This indicates that analyzing oracle state distinguishing games may be insufficient for a one-query permutation synthesis lower bound. Theorem 7.1 (Theorem 5.4 restated). There exists a one-query adversary 𝒜 such that, for every in-place permutation unitary 𝑃 : |𝑥⟩ ↦→ |𝜋(𝑥)⟩ on {0, 1}𝑛 , there is a classical oracle 𝑓𝜋 : {0, 1}ℓ(𝑛) → {0, 1} for some polynomially bounded ℓ(𝑛) for which 𝒜𝑓𝜋 distinguishes the ensemble {𝑃 𝐻 |𝑘⟩}𝑘∈[2𝑛/2 ] from Haar-random input with constant advantage. Proof. Let
𝒦small := {0𝑛/2 𝑧 : 𝑧 ∈ {0, 1}𝑛/2 } ⊆ {0, 1}𝑛 ,
so that |𝒦small | = 2𝑛/2 . Define
𝑔𝜋 (𝑥) := 𝜋 −1 (𝑥)[𝑛/2+1,𝑛] ,
namely the last 𝑛/2 bits of 𝜋 −1 (𝑥). For every 𝑦 ∈ {0, 1}𝑛/2 , define the state |𝜑𝜋,𝑦 ⟩ := 2−𝑛/4
∑︁
|𝑥⟩ .
𝑥: 𝑔𝜋 (𝑥)=𝑦
By the one-query state-synthesis algorithm of Rosenthal [Ros24, Theorem 4.1], there is a polynomialsize quantum circuit 𝐶𝑛 and, for each pair (𝜋, 𝑦), a classical oracle 𝑓𝜋,𝑦 such that the reduced state 𝑓 on the first 𝑛 qubits of 𝐶𝑛𝜋,𝑦 |0poly(𝑛) ⟩ is within trace distance 2−𝑛 of |𝜑𝜋,𝑦 ⟩. We now combine all of these oracles into a single oracle 𝑓𝜋 (𝑥, 𝑢, 𝑧) := (−1)𝑔𝜋 (𝑥)·𝑢 𝑓𝜋,𝑔𝜋 (𝑥) (𝑧). On input |𝜓⟩ =
𝑥 𝛼𝑥 |𝑥⟩, the adversary proceeds as follows.
∑︀
1. Append ancilla |+⟩⊗𝑛/2 |0poly(𝑛) ⟩, producing three registers: ∑︁
⊗𝑛/2
𝛼𝑥 |𝑥⟩1 ⊗ |+⟩2
⊗ |0poly(𝑛) ⟩3 .
𝑥
2. Run 𝐶𝑛 on the third register, answering its oracle query using 𝑓𝜋 on the joint state. On basis states |𝑥, 𝑢, ·⟩, this applies the phase (−1)𝑔𝜋 (𝑥)·𝑢 together with the oracle 𝑓𝜋,𝑔𝜋 (𝑥) needed by 𝐶𝑛 . 3. Apply 𝐻 ⊗𝑛/2 to the second register and measure it in the computational basis, obtaining some 𝑦 ∈ {0, 1}𝑛/2 . 28
4. Perform a swap test between the first register and the first 𝑛 qubits of the third register. Output “structured” if and only if the swap test accepts. Suppose first that the input is 𝑃 𝐻 |𝑘⟩ for some 𝑘 ∈ 𝒦small . Because the first 𝑛/2 bits of 𝑘 vanish, 1 ∑︁ 1 ∑︁ −1 𝑃 𝐻 |𝑘⟩ = √ (−1)𝑘·𝜋 (𝑥) |𝑥⟩ = √ (−1)𝑘·𝑔𝜋 (𝑥) |𝑥⟩ . 𝑁 𝑥 𝑁 𝑥 After step 2, the joint state is proportional to ∑︁
(−1)𝑘·𝑔𝜋 (𝑥) |𝑥⟩ ⊗
𝑥
∑︁
𝑓
(−1)𝑔𝜋 (𝑥)·𝑢 |𝑢⟩ ⊗ 𝐶𝑛𝜋,𝑔𝜋 (𝑥) |0poly(𝑛) ⟩ .
𝑢
Applying 𝐻 ⊗𝑛/2 to the second register maps this to a superposition proportional to (−1)𝑘·𝑦 |𝜑𝜋,𝑦 ⟩ ⊗ |𝑦⟩ ⊗ 𝐶𝑛𝑓𝜋,𝑦 |0poly(𝑛) ⟩ .
∑︁ 𝑦∈{0,1}𝑛/2
Conditioned on measuring 𝑦, the first register is exactly |𝜑𝜋,𝑦 ⟩, while the first 𝑛 qubits of the third register 𝜌𝜋,𝑦 are within trace distance 2−𝑛 of |𝜑𝜋,𝑦 ⟩. Therefore the swap test accepts with probability at least 1 1 1 + ⟨𝜑𝜋,𝑦 | 𝜌𝜋,𝑦 |𝜑𝜋,𝑦 ⟩ ≥ 1 − · 2−𝑛 . 2 2 2 Now suppose the input is a uniformly random computational basis state |𝑥⟩. After step 3, the first two registers are |𝑥⟩ |𝑔𝜋 (𝑥)⟩, and the first 𝑛 qubits of the third register are still within trace distance 2−𝑛 of |𝜑𝜋,𝑔𝜋 (𝑥) ⟩. The overlap between |𝑥⟩ and |𝜑𝜋,𝑔𝜋 (𝑥) ⟩ is exactly 2−𝑛/4 , so the swap test accepts with probability at most 1 1 1 1 + ⟨𝑥| 𝜌𝑥,𝑔𝜋 (𝑥) |𝑥⟩ ≤ + · 2−𝑛/2 . 2 2 2 2 This gives constant distinguishing advantage.
7.2
Search formulation
We now turn to the search problem. Fix a key set 𝒦 ⊆ {0, 1}𝑛 of size 𝐾 containing 0, and identify the search key space with 𝒦 ∖ {0}. Given one copy of 𝑃 𝐻 |𝑘⟩ for uniformly random 𝑘 ∈ 𝒦 ∖ {0}, the goal is to output 𝑘 using one oracle query. For a uniformly random permutation 𝜋, define 𝑅𝜋 (𝑘, 𝑥) := (−1)𝑘·𝜋
−1 (𝑥)
1 ∑︁ 𝑃 𝐻 |𝑘⟩ = √ 𝑅𝜋 (𝑘, 𝑥) |𝑥⟩ . 𝑁 𝑥
so that
In order to invoke Lemmas 6.1 and 6.2, we take advantage of one additional property of this family. Let Π⊥ := I − |+𝑁 ⟩⟨+𝑁 | , where |+𝑁 ⟩ = 𝑁 −1/2 𝑥 |𝑥⟩. For every nonzero key 𝑘, the state 𝑃 𝐻 |𝑘⟩ is orthogonal to |+𝑁 ⟩, and its marginal over random 𝜋 is the maximally mixed state on |+𝑁 ⟩⊥ : ∑︀
E𝜋 𝑃 𝐻 |𝑘⟩⟨𝑘| 𝐻𝑃 −1 = [︀
]︀
29
1 Π⊥ . 𝑁 −1
Indeed, permutation symmetry forces this density matrix to commute with every permutation matrix, hence to have the form 𝑎 |+𝑁 ⟩⟨+𝑁 | + 𝑏Π⊥ ; since every 𝑃 𝐻 |𝑘⟩ with 𝑘 ̸= 0 lies in |+𝑁 ⟩⊥ , we have 𝑎 = 0, and the trace-one condition gives 𝑏 = 1/(𝑁 − 1). ∑︀ Write 𝑉 = 𝑖 |𝑖⟩⟨𝑣𝑖 | as usual, and define ‖ |𝑣̃︀𝑖 ⟩‖2 𝑝𝑖 := . 𝑁 −1
|𝑣̃︀𝑖 ⟩ := Π⊥ |𝑣𝑖 ⟩ ,
Because the challenge states lie in |+𝑁 ⟩⊥ , only the projected vectors 𝑣̃︀𝑖 matter in the overlap computation. Therefore, by Lemmas 6.1 and 6.2 with 𝑆 = |+𝑁 ⟩⊥ and 𝐿 = 𝑁 − 1, it is enough to bound ∑︁ E𝜋 ‖𝑀𝜋 ‖2 , 𝑀𝜋 := 𝑅𝜋 (𝑘, 𝑥)𝐵𝑘,𝑥 . 𝑘,𝑥
Here 𝐵𝑘,𝑥 = √ which satisfies ∑︁
† 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⪯
𝑘,𝑥
and
∑︁ 1 ⟨𝑣̃︀𝑖 |𝑥⟩ √ Π𝑘 |𝑖⟩⟨𝑖| , 𝑁 𝐾 𝑖∈[𝑀 ]: 𝑝𝑖 >0 𝑝𝑖
𝑁 −1 · I, 𝑁𝐾
∑︁
† 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⪯
𝑘,𝑥
𝑁 −1 · I, 𝑁𝐾
𝐵𝑘†1 ,𝑥 𝐵𝑘2 ,𝑦 = 0 for 𝑘1 ̸= 𝑘2 .
Because 𝜋 and 𝜋 −1 are identically distributed, we will freely replace 𝜋 −1 by 𝜋 in the calculations below.
7.3
Rewriting 𝑀𝜋 as a combinatorial matrix sum
Step 1: write in terms of deterministic matrices. From the definition of 𝑅𝜋 , 𝑀𝜋 =
∑︁
(−1)𝑘·𝜋(𝑥) 𝐵𝑘,𝑥 .
𝑘,𝑥
For 𝑥, 𝑦 ∈ [𝑁 ], define
𝐴𝑥,𝑦 :=
(−1)𝑘·𝑦 𝐵𝑘,𝑥 .
(4)
∑︁ 𝑘
Then
𝑀𝜋 =
∑︁
𝐴𝑥,𝜋(𝑥) .
𝑥
Thus the random permutation now appears only through the combinatorial matrix sum
𝑥 𝐴𝑥,𝜋(𝑥) .
∑︀
Step 2: pass to a Hermitian dilation. The matrices 𝐴𝑥,𝑦 need not be Hermitian, so we replace them with their Hermitian dilations 0 𝐵𝑘,𝑥 , † 𝐵𝑘,𝑥 0 )︃
(︃ ̂︀𝑘,𝑥 := 𝐵
Then
(︃
𝐴̂︀𝑥,𝑦 :=
⃦ ⃦2 ⃦∑︁ ⃦ ⃦ ⃦ E𝜋 ‖𝑀𝜋 ‖ = E𝜋 ⃦ 𝐴̂︀𝑥,𝜋(𝑥) ⃦ . ⃦ 𝑥 ⃦ 2
30
)︃
0 𝐴𝑥,𝑦 . † 𝐴𝑥,𝑦 0
(5)
7.4
Parameter estimates for the combinatorial matrix sum
We now verify the hypotheses of Theorem 3.12 for the family {𝐴̂︀𝑥,𝑦 }𝑥,𝑦 . Zero total sum. Using (4), ∑︁
𝐴𝑥,𝑦 =
𝑥,𝑦
(−1)𝑘·𝑦 𝐵𝑘,𝑥 =
∑︁ ∑︁
∑︁
𝑥,𝑦
𝑘,𝑥
𝑘
𝐵𝑘,𝑥
(︃ ∑︁
)︃
(−1)𝑘·𝑦
=𝑁
𝑦
∑︁
𝐵0,𝑥 .
𝑥
As 0 is not in the key space, we set Π0 = 0 by convention, so 𝐵0,𝑥 = 0 for every 𝑥, and therefore ∑︀ 𝑥,𝑦 𝐴𝑥,𝑦 = 0. The same holds for the Hermitian dilations. ⃦ ⃦
⃦ ⃦
Uniform norm bound. Since ⃦𝐴̂︀𝑥,𝑦 ⃦ = ‖𝐴𝑥,𝑦 ‖, it suffices to bound ‖𝐴𝑥,𝑦 ‖. We compute ⎛
𝐴†𝑥,𝑦 𝐴𝑥,𝑦 = ⎝ =
⎞
⎞⎛
(−1)𝑘1 ·𝑦 𝐵𝑘†1 ,𝑥 ⎠ ⎝
(−1)𝑘2 ·𝑦 𝐵𝑘2 ,𝑥 ⎠
∑︁
∑︁
𝑘1
𝑘2
∑︁
(−1)(𝑘1 +𝑘2 )·𝑦 𝐵𝑘†1 ,𝑥 𝐵𝑘2 ,𝑥 =
𝑘1 ,𝑘2
∑︁
† 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⪯
𝑘
1 · I. 𝐾
Thus, we obtain that √︁ ⃦ ⃦ 1 ⃦ ̂︀ ⃦ † ⃦𝐴𝑥,𝑦 ⃦ = ‖𝐴𝑥,𝑦 ‖ = 𝜆max (𝐴𝑥,𝑦 𝐴𝑥,𝑦 ) ≤ √ ,
(6)
𝐾
√ so the role of 𝑟 in Theorem 3.12 is played by 1/ 𝐾. Variance bound.
The matrix variance parameter is ⃦
⃦
∑︁
𝐴𝑥,𝑦 𝐴†𝑥,𝑦 =
⃦ 1 ⃦ 1 ⃦∑︁ ̂︀2 ⃦ max 𝜎2 = 𝐴𝑥,𝑦 ⃦ = ⃦ ⃦ ⃦ 𝑁 𝑥,𝑦 𝑁
⃦ ⃦ ⃦}︃ {︃⃦ ⃦∑︁ ⃦ ⃦∑︁ ⃦ ⃦ ⃦ ⃦ ⃦ 𝐴𝑥,𝑦 𝐴†𝑥,𝑦 ⃦ , ⃦ 𝐴†𝑥,𝑦 𝐴𝑥,𝑦 ⃦ . ⃦ ⃦ 𝑥,𝑦 ⃦ ⃦ 𝑥,𝑦 ⃦
For the first term, 𝑥,𝑦
∑︁ ∑︁
(−1)(𝑘1 +𝑘2 )·𝑦 𝐵𝑘1 ,𝑥 𝐵𝑘†2 ,𝑥
𝑥,𝑦 𝑘1 ,𝑘2
=𝑁
∑︁
† 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⪯
𝑘,𝑥
𝑁 −1 · I, 𝐾
using (1) with 𝐿 = 𝑁 − 1. The second term is identical and equals 𝑁 (2). Therefore 𝑁 −1 1 𝜎2 = ≤ . 𝑁𝐾 𝐾
31
† 𝑁 −1 𝑘,𝑥 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⪯ 𝐾 · I by
∑︀
(7)
7.5
Upper bounding the search game winning probability
Apply Theorem 3.12 to the Hermitian matrix 𝑋 :=
∑︁
𝐴̂︀𝑥,𝜋(𝑥) .
𝑥
Using (6) and (7), we obtain the (︃
𝑡2 √ √ Pr 𝜆max (𝑋) ≥ 𝑡 ≤ 2𝑀 · exp − 12/𝐾 + 4 2 𝑡/ 𝐾 [︀
Choose 𝑡 := 𝐶
)︃
]︀
log 𝑀 log 𝐾 √ 𝐾
Then
.
for a sufficiently large universal constant 𝐶.
[︃
Pr 𝜆max (𝑋) ≥ 𝐶 2
2 log
2
𝑀 log2 𝐾 1 ≤ . 𝐾 𝐾 ]︃
Combining this with (5), E𝜋 ‖𝑀𝜋 ‖2 = E‖𝑋‖2 = E 𝜆max (𝑋)2 [︀
[︁
]︁
]︀ [︁
]︁
≤ Pr 𝜆max (𝑋)2 ≥ 𝑡2 · 1 + Pr 𝜆max (𝑋)2 ≤ 𝑡2 · 𝑡2 log2 𝑀 log2 𝐾 =𝑂 𝐾 (︃
)︃
.
By Lemma 6.1, this is also an upper bound on the average search success probability, and thus proves Theorem 5.1.
7.6
One-query lower bound with classical advice
The same tail bound also derives the classical-advice lower bound. For a fixed advice string, the spectral reduction from Lemma 6.1 suggests that constant winning probability requires ‖𝑀𝜋 ‖2 = Ω(1). By setting 𝑡 = 𝑐 for some constant 𝑐 = Ω(1), this occurs with probability bounded by (︁ √ )︁ 𝑐2 √ √ Pr 𝜆max (𝑋) ≥ 𝑐 ≤ 2𝑀 · exp − = 2𝑀 · exp −Ω( 𝐾) , 12/𝐾 + 4 2 𝑐/ 𝐾 √ which is exponentially small if log 𝑀 ≪ 𝐾. A union bound over all 2𝑆 advice strings then yields the lower bound √ 𝑆 + log(𝑀 ) = Ω( 𝐾) (︃
[︀
)︃
]︀
in order to achieve constant win probability.
32
8
One-query lower bound for 𝐹2 𝐻𝐹1
In this section, we analyze the state family {𝐹2 𝐻𝐹1 𝐻 |𝑘⟩}𝑘 through the oracle state search game. We start with the formulation of the search game in Section 8.1. The proof of lower bound also makes use of the spectral relaxation from Lemma 6.1. However, unlike the permutation case, the random matrix 𝑀𝑅 is no longer a combinatorial sum. Instead, we exploit the two independent sources of randomness (from 𝑓1 and 𝑓2 ) in two steps. First, we condition on 𝑓1 and use the randomness of 𝑓2 to invoke a matrix Rademacher series concentration inequality in Section 8.2. Then, we analyze the matrix variance terms from Section 8.2, in expectation over 𝑓1 , by a second matrix-concentration argument in Sections 8.3 and 8.4. We conclude our winning probability upper bound in Section 8.5. Finally, we present a classical advice lower bound for non-uniform one-query algorithms in Section 8.6. We also extend our lower bound to the 𝑡-case state family {𝐹𝑡 𝐻𝐹𝑡−1 𝐻 · · · 𝐹2 𝐻𝐹1 𝐻 |𝑘⟩}𝑘 for 𝑡 ≥ 3, as in Section 8.7.
8.1
Search formulation
Let 𝑓1 , 𝑓2 : {0, 1}𝑛 → {0, 1} be uniformly random Boolean functions, and define the phase unitaries 𝐹𝑗 :=
(−1)𝑓𝑗 (𝑥) |𝑥⟩⟨𝑥|
∑︁
(𝑗 ∈ {1, 2}).
𝑥∈{0,1}𝑛
The search problem is: given one copy of 𝐹2 𝐻𝐹1 𝐻 |𝑘⟩ for uniformly random 𝑘 ∈ [𝐾], recover 𝑘 using one oracle query. Write the challenge state as 1 ∑︁ 𝐹2 𝐻𝐹1 𝐻 |𝑘⟩ = √ 𝑅(𝑘, 𝑥) |𝑥⟩ , 𝑁 𝑥∈[𝑁 ] where
⎞
⎛
1 (−1)𝑓1 (𝑦)+𝑦·(𝑘+𝑥) ⎠ . 𝑅(𝑘, 𝑥) := (−1)𝑓2 (𝑥) · ⎝ √ 𝑁 𝑦∈[𝑁 ] ∑︁
(8)
Here and throughout this section, 𝑘 + 𝑥 denotes addition in F𝑛2 . Define 1 ∑︁ 𝛼𝑢 := √ (−1)𝑓1 (𝑦)+𝑦·𝑢 𝑁 𝑦∈[𝑁 ] so that
(𝑢 ∈ {0, 1}𝑛 ),
(9)
𝑅(𝑘, 𝑥) = (−1)𝑓2 (𝑥) 𝛼𝑘+𝑥 .
We observe that the marginal distribution of the challenge state |𝜓𝑅,𝑘 ⟩ over random (𝑓1 , 𝑓2 ) is independent of 𝑘: replacing 𝑓1 by (𝑘)
𝑓1 (𝑦) := 𝑓1 (𝑦) ⊕ (𝑦 · 𝑘) (𝑘)
transforms the 𝑘-th family into the 0-th, and (𝑓1 , 𝑓2 ) has the same distribution as (𝑓1 , 𝑓2 ). Moreover, [︀ ]︀ 1 ·I for every 𝑘, E𝑓1 ,𝑓2 𝐹2 𝐻𝐹1 𝐻 |𝑘⟩⟨𝑘| 𝐻𝐹1 𝐻𝐹2 = 𝑁 33
because averaging over 𝑓2 kills all off-diagonal entries while each diagonal entry is 1/𝑁 . Therefore, Lemmas 6.1 and 6.2 apply with 𝑆 = C𝑁 and 𝐿 = 𝑁 . This means that E𝑓1 ,𝑓2 [Win(𝒜 | 𝑓1 , 𝑓2 )] ≤ E𝑓1 ,𝑓2 ‖𝑀𝑅 ‖2 ,
𝑀𝑅 :=
∑︁
𝑅(𝑘, 𝑥)𝐵𝑘,𝑥 ,
𝑘,𝑥
where ∑︁
† 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⪯
𝑘,𝑥
1 · I, 𝐾
∑︁
† 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⪯
𝑘,𝑥
1 I, 𝐾
and 𝐵𝑘†1 ,𝑥 𝐵𝑘2 ,𝑦 = 0 for all 𝑘1 ̸= 𝑘2 .
8.2
Conditioning on 𝑓1 : a matrix Rademacher series
For each fixed 𝑓1 and each 𝑥 ∈ [𝑁 ], define 𝑍𝑥 :=
∑︁
𝛼𝑘+𝑥 𝐵𝑘,𝑥 .
𝑘
Then
𝑀𝑅 =
∑︁
(−1)𝑓2 (𝑥) 𝑍𝑥 .
(10)
𝑥
Conditioned on 𝑓1 , the signs {(−1)𝑓2 (𝑥) }𝑥 are independent Rademacher variables. Therefore, Theorem 3.11 implies E𝑓2 ‖𝑀𝑅 ‖2 ≤ 𝑂(log 𝑀 ) · Var(𝑀𝑅 ) ⃦ ⃦
(︁⃦ ⃦
⃦)︁ ⃦
⃦ ⃦
≤ 𝑂(log 𝑀 ) · ⃦E𝑓2 [𝑀𝑅 𝑀𝑅† ]⃦ + ⃦E𝑓2 [𝑀𝑅† 𝑀𝑅 ]⃦ .
(11)
Averaging over 𝑓1 gives ⎛
⎞ ⃦ ⃦ ⃦ ⃦ ⎜ ⃦ ⃦⎟ ⃦ † ⃦ † ⎟ E𝑓1 ,𝑓2 ‖𝑀𝑅 ‖2 = 𝑂(log 𝑀 ) · ⎜ ⎝E𝑓1 ⃦E𝑓2 [𝑀𝑅 𝑀𝑅 ]⃦ + E𝑓1 ⃦E𝑓2 [𝑀𝑅 𝑀𝑅 ]⃦⎠ . ⏟ ⏞ ⏞ ⏟ Section 8.3
(12)
Section 8.4
In the next section, we bound these two terms separately.
8.3
Bounding E𝑓1 ‖E𝑓2 [𝑀𝑅 𝑀𝑅† ]‖
In terms of equation (10), the 𝑓2 -average kills all cross terms in 𝑥, so ⃦ ⃦ ⃦ ⃦ ⃦∑︁ ⃦ ⃦ ⃦ † ⃦ †⃦ E𝑓1 ⃦E𝑓2 [𝑀𝑅 𝑀𝑅 ]⃦ = E𝑓1 ⃦ 𝑍𝑥 𝑍𝑥 ⃦ . ⃦ 𝑥 ⃦
(13)
It is convenient to package these matrices into a single rectangular matrix. Define 𝑁𝑓1 :=
∑︁
𝑍𝑥 ⊗ ⟨𝑥| .
𝑥
Then ∑︁
𝑍𝑥 𝑍𝑥† = 𝑁𝑓1 𝑁𝑓†1 ,
⃦ ⃦ ⃦∑︁ ⃦ ⃦ †⃦ E𝑓1 ⃦ 𝑍𝑥 𝑍𝑥 ⃦ = E𝑓1 ‖𝑁𝑓1 ‖2 . ⃦ 𝑥 ⃦
so
𝑥
34
(14)
Next we rewrite 𝑁𝑓1 as a second matrix Rademacher series. Expanding (9), 𝑁𝑓1 =
∑︁
𝑍𝑥 ⊗ ⟨𝑥| =
𝑥
∑︁
𝛼𝑘+𝑥 𝐵𝑘,𝑥 ⊗ ⟨𝑥|
𝑘,𝑥
1 ∑︁ (−1)𝑓1 (𝑦)+𝑦·(𝑘+𝑥) 𝐵𝑘,𝑥 ⊗ ⟨𝑥| =√ 𝑁 𝑘,𝑥,𝑦 =
∑︁
(−1)𝑓1 (𝑦) 𝑄𝑦 ,
(15)
𝑦
where
1 ∑︁ 𝑄𝑦 := √ (−1)𝑦·(𝑘+𝑥) 𝐵𝑘,𝑥 ⊗ ⟨𝑥| . 𝑁 𝑘,𝑥
The signs {(−1)𝑓1 (𝑦) }𝑦 are again independent Rademacher variables, so a second application of Theorem 3.11 yields E𝑓1 ‖𝑁𝑓1 ‖2 ≤ 𝑂(log(𝑀 𝑁 )) · Var(𝑁𝑓1 ) ⃦ ⃦
(︁⃦ ⃦
⃦ ⃦
⃦)︁ ⃦
≤ 𝑂(log(𝑀 𝑁 )) · ⃦E𝑓1 [𝑁𝑓1 𝑁𝑓†1 ]⃦ + ⃦E𝑓1 [𝑁𝑓†1 𝑁𝑓1 ]⃦ . First variance term. Averaging (15) over 𝑓1 removes the cross terms in 𝑦, so ⃦ ⃦ ⃦ ⃦ ⃦∑︁ ⃦ ⃦ ⃦ ⃦ † ⃦ 𝑄𝑦 𝑄†𝑦 ⃦ ⃦E𝑓1 [𝑁𝑓1 𝑁𝑓1 ]⃦ = ⃦ ⃦ 𝑦 ⃦ ⃦ ⃦ ⃦∑︁ ∑︁ ∑︁ ⃦ ⃦ ⃦ 1 ⃦ † 𝑦·(𝑘1 +𝑥1 )+𝑦·(𝑘2 +𝑥2 ) ⃦ = (−1) 𝐵 𝐵 ⟨𝑥 |𝑥 ⟩ 𝑘1 ,𝑥1 𝑘2 ,𝑥2 1 2 ⃦ ⃦ 𝑁 ⃦ 𝑦 𝑘 ,𝑥 𝑘 ,𝑥 ⃦ 1 1 2 2 ⃦ ⃦ ⃦ ⃦∑︁ ∑︁ ∑︁ 1 ⃦ † ⃦ 𝑦·(𝑘1 +𝑘2 ) ⃦ ⃦ = (−1) 𝐵 𝐵 𝑘1 ,𝑥 𝑘2 ,𝑥 ⃦ 𝑁⃦ ⃦ ⃦ 𝑦 𝑥 𝑘1 ,𝑘2 ⃦ ⃦ ⃦∑︁ ⃦ ⃦ 1 † ⃦ ⃦ =⃦ 𝐵 𝐵 . 𝑘,𝑥 𝑘,𝑥 ⃦ ≤ ⃦ 𝐾 ⃦ 𝑘,𝑥 ⃦
Second variance term. Similarly, ⃦ ⃦ ⃦ ⃦ ⃦∑︁ ⃦ ⃦ ⃦ ⃦ ⃦ † 𝑄†𝑦 𝑄𝑦 ⃦ ⃦E𝑓1 [𝑁𝑓1 𝑁𝑓1 ]⃦ = ⃦ ⃦ 𝑦 ⃦ ⃦ ⃦ ⃦∑︁ ∑︁ ∑︁ ⃦ ⃦ 1 ⃦ 𝑦·(𝑘1 +𝑥1 )+𝑦·(𝑘2 +𝑥2 ) † ⃦ ⃦ (−1) 𝐵 𝐵 ⊗ |𝑥 ⟩ ⟨𝑥 | = 1 2 ⃦ ⃦ 𝑘1 ,𝑥1 𝑘2 ,𝑥2 𝑁 ⃦ 𝑦 𝑘 ,𝑥 𝑘 ,𝑥 ⃦ 1 1 2 2 ⃦ ⃦ ⃦∑︁ ⃦ ⃦ ⃦ † ⃦ =⃦ 𝐵 𝐵 ⊗ |𝑥⟩ ⟨𝑥| ⃦ ⃦ 𝑘,𝑥 𝑘,𝑥 ⃦ 𝑘,𝑥 ⃦ ⃦ ⃦ ⃦ ⃦ ⃦ ⃦∑︁ ⃦ ⃦ ∑︁ ⃦ ⃦ 1 ⃦ ⃦ † † ⃦ . = max ⃦ 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⃦ ≤ ⃦ 𝐵 𝐵 𝑘,𝑥 ⃦ ≤ ⃦ 𝑘,𝑥 𝑥 ⃦ ⃦ ⃦ 𝐾 ⃦ 𝑘
𝑘,𝑥
35
(16)
Combining these estimates with (13), (14), and (16), we obtain )︂ (︂ ⃦ ⃦ log(𝑀 𝑁 ) ⃦ † ⃦ . E𝑓1 ⃦E𝑓2 [𝑀𝑅 𝑀𝑅 ]⃦ = 𝑂
(17)
𝐾
8.4
Bounding E𝑓1 ‖E𝑓2 [𝑀𝑅† 𝑀𝑅 ]‖
Again using (10), averaging over 𝑓2 removes the cross terms in 𝑥 and gives ⃦ ⃦ ⃦ ⃦ ⃦ ⃦∑︁ ⃦ ⃦ ⃦ ⃦ † † E𝑓1 ⃦E𝑓2 [𝑀𝑅 𝑀𝑅 ]⃦ = E𝑓1 ⃦ 𝑍𝑥 𝑍𝑥 ⃦ ⃦ ⃦ ⃦ ⃦ 𝑥 ⃦ ⃦∑︁ ∑︁ ⃦ ⃦ † * ⃦ 𝛼 𝛼 𝐵 𝐵 = E𝑓1 ⃦ 𝑘1 +𝑥 𝑘2 +𝑥 𝑘1 ,𝑥 𝑘2 ,𝑥 ⃦ ⃦ ⃦ ⃦ 𝑥 𝑘1 ,𝑘2 ⃦ ⃦ ⃦ ⃦∑︁ ∑︁ ⃦ ⃦ † |𝛼𝑘+𝑥 |2 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⃦ , = E𝑓1 ⃦ ⃦ ⃦ 𝑥
𝑘
where the (𝑘1 , 𝑘2 ) cross terms vanish by (3). Next, we note that ∑︁ ∑︁ 𝑥
† |𝛼𝑘+𝑥 |2 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⪯ max 𝑛 |𝛼𝑢 |2 · 𝑢∈{0,1}
𝑘
∑︁
† 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⪯ max 𝑛 |𝛼𝑢 |2 · 𝑢∈{0,1}
𝑘,𝑥
1 · I. 𝐾
Therefore,
[︁ ]︁ 1 · E𝑓1 max |𝛼𝑢 |2 . (18) 𝑢 𝐾 𝑛 For each fixed √ 𝑢 ∈ {0, 1} , the quantity 𝛼𝑢 is a sum of independent mean-zero random signs of magnitude 1/ 𝑁 , so Hoeffding’s inequality gives ⃦ ⃦
⃦ ⃦
E𝑓1 ⃦E𝑓2 [𝑀𝑅† 𝑀𝑅 ]⃦ ≤
Pr |𝛼𝑢 | ≥ [︀
𝑓1
4 log 𝑁 ≤
√︀
]︀
2 . 𝑁2
A union bound over all 𝑢 ∈ {0, 1}𝑛 yields [︁
]︁
Pr max |𝛼𝑢 |2 ≥ 4 log 𝑁 ≤ 𝑓1
Since |𝛼𝑢 | ≤
√
𝑢
2 . 𝑁
𝑁 , we obtain the expectation bound [︁
]︁
E𝑓1 max |𝛼𝑢 |2 = 𝑂(log 𝑁 ). 𝑢
Combining (18) and (19),
(︂ )︂ ⃦ ⃦ log 𝑁 ⃦ ⃦ † E𝑓1 ⃦E𝑓2 [𝑀𝑅 𝑀𝑅 ]⃦ = 𝑂 .
𝐾
36
(19)
8.5
Final bound on the search success probability
Plugging (17) and the bound from Section 8.4 into (12) gives E𝑓1 ,𝑓2 [Win(𝒜 | 𝑓1 , 𝑓2 )] ≤ E𝑓1 ,𝑓2 ‖𝑀𝑅 ‖2 log(𝑀 𝑁 ) 𝐾 (︂ )︂ log 𝑀 · log(𝑀 𝑁 ) =𝑂 . 𝐾 (︂ (︂
= 𝑂(log 𝑀 ) · 𝑂
)︂
+𝑂
(︂
log 𝑁 𝐾
)︂)︂
This proves the claimed one-query search bound for the family 𝐹2 𝐻𝐹1 𝐻 |𝑘⟩ in Theorem 5.2.
8.6
One-query lower bound with classical advice
The tail bound in Theorem 3.11 also implies a classical-advice lower bound. For a fixed advice string, the spectral reduction from Lemma 6.1 suggests that constant winning probability would require ‖𝑀𝑅 ‖2 = Ω(1). For fixed 𝑓1 , by setting 𝑡 = 𝑐 for some constant 𝑐 = Ω(1), Theorem 3.11 implies (︃ )︃ 𝑐2 Pr[‖𝑀𝑅 ‖ ≥ 𝑐] ≤ 2𝑀 · exp − . 𝑓2 2 · Var(𝑀𝑅 ) Therefore, for parameter 𝑐′ to be defined later, Pr [‖𝑀𝑅 ‖ ≥ 𝑐] ≤ Pr Var(𝑀𝑅 ) ≥ 𝑐′ + Pr Var(𝑀𝑅 ) < 𝑐′ ∧ ‖𝑀𝑅 ‖ ≥ 𝑐 ]︀
[︀
𝑓1 ,𝑓2
𝑓1
[︀
]︀
𝑓1 ,𝑓2
(︃
𝑐2 ≤ Pr Var(𝑀𝑅 ) ≥ 𝑐 + 2𝑀 · exp − 𝑓1 2 · 𝑐′
)︃
′ ]︀
[︀
.
From the definition of Var(𝑀𝑅 ) and (14), (18), ⃦ ⃦
⃦ ⃦
⃦ ⃦
⃦ ⃦
Var(𝑀𝑅 ) ≤ ⃦E𝑓2 [𝑀𝑅 𝑀𝑅† ]⃦ + ⃦E𝑓2 [𝑀𝑅† 𝑀𝑅 ]⃦ ≤ ‖𝑁𝑓1 ‖2 +
1 max |𝛼𝑢 |2 . 𝐾 𝑢
Therefore, by applying tail bound in Theorem 3.11 for 𝑁𝑓1 , the bound of Var(𝑁𝑓1 ) ≤ 2/𝐾 in Section 8.3, together with a tail bound for (19), ⎡
√︃ ⎤
′ ]︀
Pr Var(𝑀𝑅 ) ≥ 𝑐 ≤ Pr⎣‖𝑁𝑓1 ‖ ≥ [︀
𝑓1
𝑓1
𝑐′ ⎦ 𝑐′ 𝐾 + Pr max |𝛼𝑢 |2 ≥ 𝑢 2 2
]︂
)︃
𝑐′ 𝐾 2
[︂
(︃
𝑐′ ≤ 2𝑀 𝑁 · exp − 4 · Var(𝑁𝑓1 ) (︂
≤ 2𝑀 𝑁 · exp −
𝑐′ 𝐾 2
(︂
+ 𝑁 · exp −
)︂
.
√ Therefore, by setting 𝑐′ = 1/ 𝐾, we can bound the probability for 𝑐 = Ω(1) by (︃
𝑐2 Pr [‖𝑀𝑅 ‖ ≥ 𝑐] ≤ Pr Var(𝑀𝑅 ) ≥ 𝑐 + 2𝑀 · exp − 𝑓1 ,𝑓2 𝑓1 2 · 𝑐′ ′ ]︀
[︀
37
)︃
)︂
(︃
)︃
𝑐′ 𝐾 𝑐2 ≤ 2𝑀 𝑁 · exp − + 2𝑀 · exp − 2 2 · 𝑐′ )︁ (︁ )︁ (︁ √ √ = 2𝑀 𝑁 · exp − 𝐾/2 + 2𝑀 · exp −𝑐2 𝐾/2 , (︂
)︂
√ which is exponentially small if log 𝑀 𝑁 ≪ 𝐾. A union bound over all 2𝑆 advice strings then yields the lower bound √ 𝑆 + log(𝑀 𝑁 ) = Ω( 𝐾) in order to achieve constant win probability.
8.7
One-query lower bound for 𝐹𝑡 𝐻𝐹𝑡−1 𝐻 · · · 𝐹2 𝐻𝐹1
In this subsection, we extend our one-query lower bound to the oracle state search game with state family {𝐹𝑡 𝐻𝐹𝑡−1 𝐻 · · · 𝐹2 𝐻𝐹1 𝐻 |𝑘⟩}𝑘 . Corollary 8.1 (Corollary 5.3 restated). Let 𝑓1 , . . . , 𝑓𝑡 : {0, 1}𝑛 → {0, 1} be uniformly random ∑︀ Boolean functions, and let 𝐹𝑗 = 𝑥 (−1)𝑓𝑗 (𝑥) |𝑥⟩⟨𝑥| for 𝑗 ∈ {1, . . . , 𝑡}. For the search game on the family {𝐹𝑡 𝐻𝐹𝑡−1 𝐻 · · · 𝐹2 𝐻𝐹1 𝐻 |𝑘⟩}𝑘∈[𝐾] , every one-query adversary with workspace dimension 𝑀 satisfies (︂ )︂ [︀ ]︀ log 𝑀 · log(𝑀 𝑁 ) E𝑓1 ,...,𝑓𝑡 Win(𝒜 | 𝑓1 , . . . , 𝑓𝑡 ) = 𝑂 . 𝐾 Proof. We prove the lower bound for the search game on {𝐹𝑡 𝐻𝐹𝑡−1 𝐻 · · · 𝐹2 𝐻𝐹1 𝐻 |𝑘⟩}𝑘 by reducing it to the 𝑡 = 2 case. In fact, our reduction shows that the one-query oracle state search game on {𝐹𝑡 𝐻𝐹𝑡−1 𝐻 · · · 𝐹2 𝐻𝐹1 𝐻 |𝑘⟩}𝑘 is at least as (𝑀, 𝜀)-hard as the corresponding 𝑡 = 2 case. For simplicity, for any 𝐹1 , . . . , 𝐹𝑡 , we define a unitary 𝑈[3:𝑡] := 𝐹𝑡 𝐻𝐹𝑡−1 𝐻 · · · 𝐹3 𝐻 and states |𝜓2,𝑘 ⟩ := 𝐹2 𝐻𝐹1 𝐻 |𝑘⟩ ,
|𝜓𝑡,𝑘 ⟩ := 𝐹𝑡 𝐻𝐹𝑡−1 𝐻 · · · 𝐹1 𝐻 |𝑘⟩ = 𝑈[3:𝑡] |𝜓2,𝑘 ⟩ .
From the definition of the search game in Section 4, we can write the adversary’s winning probability on |𝜓𝑡,𝑘 ⟩, in expectation over 𝑓1 , . . . , 𝑓𝑡 , as [︂
]︂
E𝑓1 ,...,𝑓𝑡 [Win(𝒜 | 𝑓1 , . . . , 𝑓𝑡 )] = E𝑓1 ,...,𝑓𝑡 max E𝑘 ⟨𝜓𝑡,𝑘 | 𝑉 † 𝑂𝑓† Π𝑘 𝑂𝑓 𝑉 |𝜓𝑡,𝑘 ⟩ . 𝑓
The maximum winning probability for this 𝑡-case can thus be upper bounded by the 𝑡 = 2 bound: sup {E𝑓1 ,...,𝑓𝑡 [Win(𝒜 | 𝑓1 , . . . 𝑓𝑡 )]} 𝒜
= sup
𝑉,{Π𝑘 }
{︂
[︂
E𝑓3 ,...,𝑓𝑡 E𝑓1 ,𝑓2 max E𝑘 ⟨𝜓𝑡,𝑘 | 𝑉 𝑓
≤ E𝑓3 ,...,𝑓𝑡 sup
{︂
= E𝑓3 ,...,𝑓𝑡 sup
{︂
𝑂𝑓† Π𝑘 𝑂𝑓 𝑉 |𝜓𝑡,𝑘 ⟩
]︂}︂
E𝑓1 ,𝑓2 max E𝑘 ⟨𝜓𝑡,𝑘 | 𝑉 † 𝑂𝑓† Π𝑘 𝑂𝑓 𝑉 |𝜓𝑡,𝑘 ⟩
]︂}︂
𝑓
𝑉,{Π𝑘 }
𝑉,{Π𝑘 }
[︂
†
[︂
]︂}︂
† E𝑓1 ,𝑓2 max E𝑘 ⟨𝜓2,𝑘 | 𝑈[3:𝑡] 𝑉 † 𝑂𝑓† Π𝑘 𝑂𝑓 𝑉 𝑈[3:𝑡] |𝜓2,𝑘 ⟩ 𝑓
38
= E𝑓3 ,...,𝑓𝑡 sup
{︂
𝑉,{Π𝑘 }
[︂
E𝑓1 ,𝑓2 max E𝑘 ⟨𝜓2,𝑘 | 𝑉 † 𝑂𝑓† Π𝑘 𝑂𝑓 𝑉 |𝜓2,𝑘 ⟩
]︂}︂
𝑓
(20)
= sup {E𝑓1 ,𝑓2 [Win(𝒜 | 𝑓1 , 𝑓2 )]} . 𝒜
In particular, (20) holds because for every fixed 𝑓3 , . . . , 𝑓𝑡 and adversary 𝒜, the previous expression describes the effect of a modified adversary 𝒜′ that applies the isometry 𝑉 𝑈[3:𝑡] instead of 𝑉 . By Section 8.5 (or Theorem 5.2), log 𝑀 · log(𝑀 𝑁 ) , E𝑓1 ,...,𝑓𝑡 [Win(𝒜 | 𝑓1 , . . . 𝑓𝑡 )] = 𝑂 𝐾 )︂
(︂
and this proves the claimed one-query search bound for the family 𝐹𝑡 𝐻𝐹𝑡−1 𝐻 · · · 𝐹1 𝐻 |𝑘⟩. For search game over {𝐹𝑡 𝐻𝐹𝑡−1 𝐻 · · · 𝐹2 𝐻𝐹1 𝐻 |𝑘⟩}𝑘 , this proof also shows a reduction from 𝑡 to 𝑡 − 1: if the search game for some fixed 𝑡0 is (𝑀, 𝜀)-hard, then it is also (𝑀, 𝜀)-hard for any 𝑡 ≥ 𝑡0 . This reduction also holds for adversaries that make any fixed number of queries (such as 𝑡0 − 1). A similar argument also holds for the (𝑀, 𝜀, 𝛿)-hardness. Therefore, since the one-query lower bound with classical advice for 𝑡 = 2 (see Section 8.6) is obtained by union bounding all classical advice over its (𝑀, 𝜀, 𝛿)-hardness, the same one-query lower bound with classical advice extends to all 𝑡 ≥ 2.
9
One-query synthesis for phase unitaries with constant correctness
In this section, we give a one-query algorithm for synthesizing (diagonal) phase unitaries with constant correctness (Theorem 5.5). By combining with our unitary synthesis composition theorem, the one-query algorithm also implies Corollary 5.6.
9.1
Phase unitary setup
Any phase unitary on 𝑛 qubits can be written as 𝐷(𝐹 ) =
∑︁
𝜔𝑞𝐹 (𝑥) |𝑥⟩⟨𝑥| ,
𝜔𝑞 := 𝑒2𝜋𝑖/𝑞 ,
𝑥∈{0,1}𝑛
for a sufficiently fine phase discretization 𝐹 : {0, 1}𝑛 → [𝑞]. The goal is to synthesize 𝐷(𝐹 ) using a single oracle query. Remark 9.1 (Oracle interface used in this section). The constructive algorithm below is most naturally written in the standard function-oracle model |𝑥⟩ |𝑦⟩ ↦−→ |𝑥⟩ |𝑦 ⊕ 𝐹 (𝑥)⟩ . For 𝑞 = 4, the second register consists of two qubits. This interface can be reduced to the boolean phase-oracle model within one query: define 𝑓 : {0, 1}𝑛+⌈log 𝑞⌉ → {0, 1} such that 𝑓 (𝑥, 𝑦) = 𝑦 · 𝐹 (𝑥). Then (I𝑛 ⊗ 𝐻 ⊗⌈log 𝑞⌉ ) · 𝑂𝑓 · (I𝑛 ⊗ 𝐻 ⊗⌈log 𝑞⌉ ) will implement the above interface. 39
9.2
The special case 𝑞 = 4
When 𝑞 = 4, the four target phases are {1, 𝑖, −1, −𝑖}. Write 𝐹 (𝑥) = 𝑏0 (𝑥)||𝑏1 (𝑥) ∈ {0, 1}2 , and define the ancilla states |−⟩ =
|0⟩ − |1⟩ √ , 2
|0⟩ + 𝑖 |1⟩ √ , 2
|+𝑖⟩ =
|−𝑖⟩ =
|0⟩ − 𝑖 |1⟩ √ . 2
The key identities are 𝑋 |−⟩ = − |−⟩ ,
𝑋 |+𝑖⟩ = 𝑖 |−𝑖⟩ ,
⟨+𝑖|−𝑖⟩ = 0.
Observe that if 𝐹 (𝑥) ∈ {0, 1}2 is identified as an integer, we have that 𝑖𝐹 (𝑥) = (−1)𝑏0 (𝑥) · 𝑖𝑏1 (𝑥) . Proposition 9.2. There is a one-query algorithm that synthesizes 𝐷(𝐹 ) for every 𝐹 : {0, 1}𝑛 → {0, 1, 2, 3} with correctness at least 1/2. Proof. Start from an arbitrary joint input state, with input register 𝑋 and auxiliary register Aux, |𝜓⟩𝑋,Aux =
∑︁
𝛼𝑥 |𝑥⟩𝑋 |𝜓𝑥 ⟩Aux .
𝑥
Append the ancilla state |−⟩ |+𝑖⟩. Then query the oracle so that on computational basis, the query acts by |𝑥⟩ |𝑦⟩ ↦−→ |𝑥⟩ |𝑦 ⊕ 𝐹 (𝑥)⟩ . Equivalently, if 𝐹 (𝑥) = 𝑏0 (𝑥)||𝑏1 (𝑥) then the ancilla undergoes 𝑋 𝑏0 (𝑥) ⊗ 𝑋 𝑏1 (𝑥) . Let 𝑆0 := {𝑥 : 𝐹 (𝑥) ∈ {0, 2}}, 𝑆1 := {𝑥 : 𝐹 (𝑥) ∈ {1, 3}}. Using the identities above, the post-query state is ∑︁
𝛼𝑥 𝑖𝐹 (𝑥) |𝑥⟩ |𝜓𝑥 ⟩ |−⟩ |+𝑖⟩ +
𝑥∈𝑆0
∑︁
𝛼𝑥 𝑖𝐹 (𝑥) |𝑥⟩ |𝜓𝑥 ⟩ |−⟩ |−𝑖⟩
𝑥∈𝑆1
=
∑︁
𝛼𝑥 𝐷(𝐹 ) |𝑥⟩ |𝜓𝑥 ⟩ |−⟩ |+𝑖⟩ +
𝑥∈𝑆0
∑︁
𝛼𝑥 𝐷(𝐹 ) |𝑥⟩ |𝜓𝑥 ⟩ |−⟩ |−𝑖⟩ .
𝑥∈𝑆1
Tracing out the ancilla destroys the coherence between the 𝑆0 and 𝑆1 parts but preserves each part exactly. Define ∑︁ 𝑝0 := |𝛼𝑥 |2 , 𝑝1 := 1 − 𝑝0 , 𝑥∈𝑆0
and normalized states 1 ∑︁ |𝜓 (0) ⟩ := √ 𝛼𝑥 |𝑥⟩ |𝜓𝑥 ⟩ , 𝑝0 𝑥∈𝑆
1 ∑︁ |𝜓 (1) ⟩ := √ 𝛼𝑥 |𝑥⟩ |𝜓𝑥 ⟩ . 𝑝1 𝑥∈𝑆
0
1
The reduced output state is then given by 𝜌 = 𝑝0 𝐷(𝐹 ) |𝜓 (0) ⟩⟨𝜓 (0) | 𝐷(𝐹 )† + 𝑝1 𝐷(𝐹 ) |𝜓 (1) ⟩⟨𝜓 (1) | 𝐷(𝐹 )† .
40
Therefore the fidelity with the ideal output 𝐷(𝐹 ) |𝜓⟩ is F 𝜌, 𝐷(𝐹 ) |𝜓⟩ = ⟨𝜓| 𝐷(𝐹 )† 𝜌𝐷(𝐹 ) |𝜓⟩ (︀
)︀
= 𝑝0 |⟨𝜓 | 𝜓 (0) ⟩|2 + 𝑝1 |⟨𝜓 | 𝜓 (1) ⟩|2 = 𝑝20 + 𝑝21 1 ≥ , 2 since 𝑝0 + 𝑝1 = 1 and the minimum of 𝑝20 + 𝑝21 occurs at 𝑝0 = 𝑝1 = 1/2.
9.3
General 𝑞 via rounding to the nearest quadrant
For general 𝑞, write
𝜔𝑞𝐹 (𝑥) = 𝑎(𝑥) + 𝑖𝑏(𝑥)
with 𝑎(𝑥), 𝑏(𝑥) ∈ R.
Define a rounded phase function 𝐺 : {0, 1}𝑛 → {0, 1, 2, 3} by choosing the nearest fourth root of unity: √ • if 𝑎(𝑥) ≥ 1/ 2, set 𝐺(𝑥) = 0; √ • if 𝑎(𝑥) ≤ −1/ 2, set 𝐺(𝑥) = 2; √ • if 𝑏(𝑥) ≥ 1/ 2, set 𝐺(𝑥) = 1; • otherwise set 𝐺(𝑥) = 3. 𝐹 (𝑥)
Equivalently, 𝑖𝐺(𝑥) is the fourth root of unity whose angle differs from 𝜔𝑞
by at most 𝜋/4.
Proposition 9.3. Applying the 𝑞 = 4 algorithm to the rounded phase function 𝐺 yields a one-query synthesis algorithm for 𝐷(𝐹 ) with correctness at least 1/4. Proof. Run the 𝑞 = 4 construction from Proposition 9.2 using 𝐺 in place of 𝐹 . As before, write 𝑆0 := {𝑥 : 𝐺(𝑥) ∈ {0, 2}},
𝑆1 := {𝑥 : 𝐺(𝑥) ∈ {1, 3}},
and decompose the input state as |𝜓⟩ =
∑︁
𝛼𝑥 |𝑥⟩ |𝜓𝑥 ⟩ =
√
𝑝0 |𝜓 (0) ⟩ +
√
𝑝1 |𝜓 (1) ⟩ ,
𝑥
where
𝑝0 :=
∑︁
|𝛼𝑥 |2 ,
𝑝1 :=
𝑥∈𝑆0
and
∑︁
|𝛼𝑥 |2 = 1 − 𝑝0 ,
𝑥∈𝑆1
1 ∑︁ |𝜓 (1) ⟩ := √ 𝛼𝑥 |𝑥⟩ |𝜓𝑥 ⟩ . 𝑝1 𝑥∈𝑆
1 ∑︁ |𝜓 (0) ⟩ := √ 𝛼𝑥 |𝑥⟩ |𝜓𝑥 ⟩ , 𝑝0 𝑥∈𝑆 0
1
The output state after tracing out the ancilla is 𝜌 = 𝑝0 𝐷(𝐺) |𝜓 (0) ⟩⟨𝜓 (0) | 𝐷(𝐺)† + 𝑝1 𝐷(𝐺) |𝜓 (1) ⟩⟨𝜓 (1) | 𝐷(𝐺)† . 41
To compare 𝐷(𝐺) with the target 𝐷(𝐹 ), define for each string 𝑥 𝛽𝑥 := 𝜔𝑞−𝐹 (𝑥) 𝑖𝐺(𝑥) . Then |𝛽𝑥 | = 1, and by construction of 𝐺(𝑥) the angle of 𝛽𝑥 is at most 𝜋/4 in absolute value. Equivalently, 1 Re(𝛽𝑥 ) ≥ √ for every 𝑥 ∈ {0, 1}𝑛 . 2 Also,
𝐷(𝐹 )† 𝐷(𝐺) =
∑︁
𝛽𝑥 |𝑥⟩⟨𝑥| .
𝑥
Therefore ⃒2 ⃒
⃒ ⃒
⃒2 ⃒
⃒ ⃒
F 𝜌, 𝐷(𝐹 ) |𝜓⟩ = 𝑝0 ⃒⟨𝜓| 𝐷(𝐹 )† 𝐷(𝐺) |𝜓 (0) ⟩⃒ + 𝑝1 ⃒⟨𝜓| 𝐷(𝐹 )† 𝐷(𝐺) |𝜓 (1) ⟩⃒ . (︀
)︀
We now bound the two overlap terms separately. For the 𝑆0 term, 1 ∑︁ ⟨𝜓| 𝐷(𝐹 )† 𝐷(𝐺) |𝜓 (0) ⟩ = √ |𝛼𝑥 |2 𝛽𝑥 . 𝑝0 𝑥∈𝑆 0
Indeed, all cross-terms vanish because 𝐷(𝐹 )† 𝐷(𝐺) is diagonal in the computational basis. Taking real parts and using |𝑧| ≥ Re(𝑧), we get ⃒ ⃒ (︁ )︁ ⃒ ⃒ ⃒⟨𝜓| 𝐷(𝐹 )† 𝐷(𝐺) |𝜓 (0) ⟩⃒ ≥ Re ⟨𝜓| 𝐷(𝐹 )† 𝐷(𝐺) |𝜓 (0) ⟩ 1 ∑︁
=√
𝑝0 𝑥∈𝑆
|𝛼𝑥 |2 Re(𝛽𝑥 )
0
1 ∑︁ |𝛼𝑥 |2 = ≥√ 2𝑝0 𝑥∈𝑆 0
√︂
𝑝0 . 2
Squaring and multiplying by 𝑝0 yields ⃒ ⃒
⃒2 ⃒
𝑝20 . 2
⃒ ⃒
⃒2 ⃒
𝑝21 . 2
𝑝0 ⃒⟨𝜓| 𝐷(𝐹 )† 𝐷(𝐺) |𝜓 (0) ⟩⃒ ≥ By the same argument, 𝑝1 ⃒⟨𝜓| 𝐷(𝐹 )† 𝐷(𝐺) |𝜓 (1) ⟩⃒ ≥ Substituting these two bounds gives F 𝜌, 𝐷(𝐹 ) |𝜓⟩ ≥ (︀
10
)︀
𝑝20 + 𝑝21 1 ≥ . 2 4
Quantum advice lower bound for 𝐹 𝐻 |𝑘⟩
In this section, we prove a quantum advice lower bound for the state search game with state family {𝐹 𝐻 |𝑘⟩}𝑘∈[𝐾] , where 𝐹 is a binary phase unitary. That is, instead of making a query to a classical 42
oracle, the adversary is only given quantum advice that may depend on the underlying state family (equivalently, on 𝐹 ) before receiving the input state |𝜓𝐹,𝑘 ⟩. Note that a binary phase unitary 𝐹 can be exactly synthesized with one query. Therefore, a quantum advice lower bound for zero-query synthesis gives a separation between one-query unitary synthesis and quantum programs (zero-query synthesis algorithms with quantum advice). By a similar reduction as in Lemma 4.6, the result of this section implies such a lower bound/separation. We remark that a more straightforward but quantitatively weaker separation holds by considering unitaries of the form |𝑥⟩ |𝑦⟩ ↦→ |𝑥⟩ |𝑦 ⊕ 𝑓 (𝑥)⟩ for a random (possibly long output) function 𝑓 . The separation is weaker because these unitaries are only as hard as computing a function on 𝑛 input bits, they will not have the same quantitative hardness as binary phase unitaries in the same dimension: either 𝑦 is short and there is a non-trivial approximation by guessing 𝑓 (𝑥) on input |𝑥⟩, or 𝑦 is long and 2𝑛 advice length is sublinear in the Hilbert space dimension. Unlike the permutation and 𝐹2 𝐻𝐹1 one-query lower bounds, we do not build on the matrix concentration-based approach of [LMW24] for this result. Instead, we make use of the alternating measurement hardness approach to advice lower bounds of [Liu23]. Organization. We start with the formulation of the search game in Section 10.1. Then, we prove the quantum advice lower bound in two steps. First, we reduce the one-instance search hardness to the hardness of an alternating measurement game in Section 10.2. Next, in Section 10.3, we upper bound the maximum winning probability of this alternating measurement game. We combine these results and conclude the quantum advice lower bound in Section 10.4. In Section 10.5, we show an algorithm that matches the lower bound (up to log 𝑁 factor).
10.1
Search formulation
Let 𝑓 : {0, 1}𝑛 → {0, 1} be uniformly random and let 𝐹 :=
∑︁
(−1)𝑓 (𝑥) |𝑥⟩⟨𝑥| .
𝑥∈{0,1}𝑛
The challenge state is 𝐹 𝐻 |𝑘⟩ for uniformly random 𝑘 ∈ [𝐾]. A non-uniform (zero-query) algorithm is allowed to use an 𝑆-qubit advice state |𝜑𝑓 ⟩ depending only on 𝑓 , and is asked to output 𝑘. Equivalently, we will work in the following normal form. The adversary has an 𝑆-qubit advice together with some ancilla initialized as |0𝑚 ⟩ on the adversary’s workspace register Z. The challenge state will be generated and sent to the adversary on input register X. The adversary will then apply a fixed projective measurement {Π𝑘 }𝑘∈[𝐾] to the input register X and the workspace Z. Writing |𝜓𝑓,𝑘 ⟩ := 𝐹 𝐻 |𝑘⟩ , its winning probability is
)︀⃦2
𝜀 := E𝑓,𝑘 ⃦Π𝑘 |𝜓𝑓,𝑘 ⟩X |𝜑𝑓 , 0𝑚 ⟩Z ⃦ . ⃦
(︀
The main result of this section is that an adversary’s maximum winning probability is upper bounded by 𝑆 𝜀=𝑂 𝐾 (︂
43
)︂
.
10.2
Reduction to alternating measurement game
Our first step is to reduce the one-instance winning probability to the winning probability of a 𝑡-round alternating measurement game. The alternating measurement game is first introduced in [Liu23] in order to obtain better security in the presence of quantum advice. Within our context of the search game, we define our alternating measurement game as the following. Definition 10.1 (Alternating measurement game). A random boolean function 𝑓 is sampled at the beginning. For a (non-uniform) quantum algorithm 𝒜 and any integer 𝑡, the alternating measurement game4 we consider here is defined as follows: • The challenger initializes its challenge register as |𝜓init ⟩ := √1𝐾 register C and input register X.
𝑘 |𝑘⟩C ⊗ 𝐻 |𝑘⟩X on challenge
∑︀
• The adversary initializes its state (or an advice) on adversary’s workspace register Z. Their algorithm is defined by a 𝐾-outcome measurement {Π𝑘 }𝑘∈[𝐾] on X, Z. • The challenger generates the first challenge by applying 𝐹 on register X, • They repeat the following procedure 𝑡 times, for 𝑖 = 1, 2, . . . , 𝑡: – If 𝑖 is odd, apply the measurement defined by projection ΠWin := to CXZ.
𝑘 |𝑘⟩⟨𝑘|C ⊗ (Π𝑘 )XZ
∑︀
– If 𝑖 is even, apply the measurement defined by projection Πinit,𝐹 := 𝐹 Πinit 𝐹 to CX, where Πinit = |𝜓init ⟩⟨𝜓init |. • The adversary wins the game if all measurement outcomes are 1. Lemma 10.2 (Reducing to alternating measurement hardness). If a non-uniform algorithm with 𝑆 qubits of advice wins the one-instance search game with probability 𝜀, then for every integer 𝑡 ≥ 1, there exists a 𝑡-round alternating measurement game, using the same 𝑆 qubits of advice, that wins with probability at least 𝜀𝑡 . Proof sketch. By the definition of these two projectors {ΠWin , Πinit,𝐹 }, we can rewrite our oneinstance winning probability )︀⃦2
𝜀 := E𝑓,𝑘 ⃦Π𝑘 |𝜓𝑓,𝑘 ⟩X |𝜑𝑓 , 0𝑚 ⟩Z ⃦ = E𝑓 ‖ΠWin 𝐹 |𝜓init ⟩CX |𝜑𝑓 , 0𝑚 ⟩Z ‖2 , ⃦
(︀
where the starting state 𝐹 |𝜓init ⟩ is in the image of Πinit,𝐹 . The lemma now follows by a standard rewinding argument [CMSZ22, Liu23]. By Jordan’s lemma, the two projectors decompose the space into orthogonal invariant subspaces of dimension at most two. On block with singular value 𝑝, if the initial state is on the corresponding singular vector in the image of Πinit,𝐹 , then its probability of surviving 𝑡 rounds is 𝑝𝑡 . Thus, for a general initial state with overall success probability 𝜀 = E[𝑝], the probability of surviving 𝑡 rounds is E[𝑝𝑡 ], which is at least (E[𝑝])𝑡 = 𝜀𝑡 by Jensen’s inequality. 4
Although we refer to it as a “game,” we remark that it is only a thought experiment, not a game that can physically be played between the challenger and adversary.
44
10.3
Upper-bounding the alternating measurement game
The second step is to upper bound the winning probability of a non-uniform 𝑡-round alternating measurement game with 𝑆-qubit quantum advice. The proof proceeds in two sub-steps: first reduce the non-uniform hardness to a uniform one by replacing the advice with the maximally mixed state; then prove uniform hardness of the 𝑡-round alternating measurement game by bounding the conditional winning probability at each round. To bound each conditional winning probability, we will rely on the randomness of 𝐹 and apply Zhandry’s compressed oracle technique [Zha19]. Here we prove an upper bound for the winning probability of a uniform 𝑡-round alternating measurement game. This will also upper bound the non-uniform case: for any adversary with 𝑆-qubit quantum advice with winning probability 𝜀𝑆 , a uniform algorithm can always sample an 𝑆-qubit maximally mixed state and run the non-uniform algorithm on the maximally mixed state, with winning probability at least 2−𝑆 · 𝜀𝑆 . Therefore, an upper bound for the winning probability of the uniform case will upper bound 2−𝑆 · 𝜀𝑆 , and thus give an upper bound for 𝜀𝑆 . Proposition 10.3 (Winning probability of (uniform) 𝑡-round alternating measurement game). For every uniform adversary in the alternating measurement game with 𝑡 measurement rounds, its maximum winning probability is upper bounded by (8𝑡/𝐾)𝑡 . We denote the measurement outcome in the 𝑖-th round as 𝑏𝑖 , and let 𝑏𝑖 = 1 if the state successfully projects onto ΠWin (if 𝑖 is odd), or Πinit,𝐹 (if 𝑖 is even). We also define the conditional probability for successfully projecting on the 𝑖-th round as 𝜀𝑖 , 𝜀𝑖 = Pr[𝑏𝑖 = 1 | 𝑏<𝑖 = 1] =
Pr[𝑏≤𝑖 = 1] . Pr[𝑏≤𝑖−1 = 1]
For alternating measurement game with 𝑡 rounds, we define 𝑏0 = 1 always, and the winning probability can be written as Pr[𝑏𝑡 = 1] =
𝑡 ∏︁
Pr[𝑏𝑖 = 1 | 𝑏<𝑖 = 1] =
𝑡 ∏︁
𝜀𝑖 .
𝑖=1
𝑖=1
The conditional probability is monotonically non-decreasing, as argued in [Liu23, Corollary 6.10]. Proposition 10.4 (Non-decreasing of 𝜀𝑖 ). {𝜀𝑖 }𝑖∈{1,...,𝑡} is monotonically non-decreasing, i.e., for every 𝑖 ∈ {2, . . . , 𝑡}, 𝜀𝑖−1 ≤ 𝜀𝑖 . Proof sketch. 𝜀𝑖 = Pr[𝑏𝑖 = 1 | 𝑏<𝑖 = 1] = Pr[𝑏≤𝑖 = 1]/ Pr[𝑏≤𝑖−1 = 1]. Similarly as in the proof for Lemma 10.2, by Jordan’s lemma, Pr[𝑏≤𝑖 = 1] can be expressed as E[𝑝𝑖 ]. By the Cauchy-Schwarz inequality, E[𝑝𝑖−1 ] · E[𝑝𝑖+1 ] ≥ E[𝑝𝑖 ]2 , and thus 𝜀𝑖+1 ≥ 𝜀𝑖 . With the non-decreasing property, it is sufficient to bound the conditional probability at only odd rounds. Lemma 10.5. For every uniform adversary in the alternating measurement game, 𝜀𝑡 ≤ 8𝑡/𝐾 for every 𝑡. Specifically, for every odd 𝑡, 𝜀𝑡 ≤ 4𝑡/𝐾. By the non-decreasing property of 𝜀𝑡 , for even 𝑡, we have 𝜀𝑡 ≤ 𝜀𝑡+1 ≤ 8𝑡/𝐾 with one more round of the alternating measurement game.
45
To bound this conditional winning probability, we will need to apply Zhandry’s compressed oracle framework [Zha19]. Since ΠWin is independent of 𝐹 , while Πinit,𝐹 = 𝐹 Πinit 𝐹 , we can view the conditional probability as making several queries to 𝐹 (or phase queries to the underlying boolean function 𝑓 ), while performing some intermediate measurements in between. Since we are analyzing probability over a random 𝑓 , we can purify the register for 𝑓 and view it in the Fourier basis as “database”. The algorithm starts with a pure uniform superposition of all possible 𝑓 , which corresponds to an initialized empty database; from the framework in [Zha19], any query to 𝑓 performing |𝑥⟩ |𝑓 ⟩ ↦→ (−1)𝑓 (𝑥) |𝑓 ⟩ will correspond to |𝑥⟩ |𝐷⟩ ↦→ |𝑥⟩ |𝐷 ⊕ {𝑥}⟩ in the database view, where 𝐷 ⊕ {𝑥} = 𝐷∖{𝑥} if 𝑥 ∈ 𝐷, and 𝐷 ⊕ {𝑥} = 𝐷 ∪ {𝑥} if 𝑥 ∈ / 𝐷. Within the compressed oracle framework, our alternating measurement game can be viewed with one more register D for the database. It is initialized as the empty set, and each “query to 𝐹 ” is replaced by a compressed oracle update on the database. The database register D is not touched by the projectors ΠWin , Πinit , although it is affected by (the purification of) 𝐹 Πinit 𝐹 . Proof of Lemma 10.5. We prove the lemma for odd 𝑡 (as even 𝑡 follows from Proposition 10.4). Define |Φ𝑡−1 ⟩ to be the normalized result state just after the (𝑡 − 1)-th round with outcome {𝑏𝑖 = 1}𝑖∈[𝑡−1] . For odd 𝑡, by definition, 𝜀𝑡 = ‖ΠWin |Φ𝑡−1 ⟩ ‖2 . Result state after (𝑡 − 1) rounds. We start by describing the state |Φ𝑡−1 ⟩. Since Πinit,𝐹 = 𝐹 Πinit 𝐹 , any result state after (𝑡 − 2) rounds in the alternating measurement game can be viewed as obtained by making (𝑡 − 3) queries to 𝐹 and performing many intermediate measurements that are independent of 𝐹 (for odd 𝑡). Within the compressed oracle framework, this gives an upper bound on the size of the database on register D. For the (𝑡−1)-th round (for odd 𝑡), we can view the projector Πinit,𝐹 = 𝐹 Πinit 𝐹 as the following: the algorithm first makes 1 query to 𝐹 , then it successfully measures on |𝜓init ⟩ on register CX, and then it makes another query to 𝐹 . Therefore, the result state after the first (𝑡 − 2) rounds along with the next query to 𝐹 has the form ∝
∑︁ 𝑘
|𝑘⟩C ⊗
∑︁
𝛼𝑘,𝑥,𝑧,𝐷 |𝑥⟩X |𝑧⟩Z |𝐷⟩D
𝑥,𝑧,𝐷
with database size |𝐷| ≤ 𝑡 − 2. Next, within the (𝑡 − 1)-th round, since the algorithm successfully measures on |𝜓init ⟩ on register CX, the result state on CX is a pure state |𝜓init ⟩ and thus is unentangled with Z and D, which has the form ∝
(︃ ∑︁
)︃
|𝑘⟩C ⊗ 𝐻 |𝑘⟩X
⎛ ⎞ ∑︁ ⊗ ⎝ 𝛽𝑧,𝐷 |𝑧⟩Z |𝐷⟩D ⎠ . 𝑧,𝐷
𝑘
Therefore, by making one query to 𝐹 , we will end up with |Φ𝑡−1 ⟩, the result state just after the (𝑡 − 1)-th round, |Φ𝑡−1 ⟩ = √
∑︁ 1 ∑︁ (−1)𝑘·𝑥 |𝑘, 𝑥⟩CX ⊗ 𝛽𝑧,𝐷 |𝑧⟩Z |𝐷 ⊕ {𝑥}⟩D . 𝐾𝑁 𝑘,𝑥 𝑧,𝐷
Now our goal is to give an upper bound for 𝜀𝑡 = ‖ΠWin |Φ𝑡−1 ⟩ ‖2 . In the below analysis we use |Φ⟩ := |Φ𝑡−1 ⟩, as we only analyze the result state after (𝑡 − 1)-th round. 46
We define 2 parts for |Φ⟩ as the following |Φ1 ⟩ , |Φ2 ⟩, |Φ⟩ = |Φ1 ⟩ + |Φ2 ⟩: |Φ1 ⟩ := √
∑︁ 1 (−1)𝑘·𝑥 · 𝛽𝑧,𝐷 · |𝑘, 𝑥, 𝑧⟩ |𝐷∖{𝑥}⟩ 𝐾𝑁 𝑘,𝑧,𝐷,𝑥∈𝐷
|Φ2 ⟩ := √
∑︁ 1 (−1)𝑘·𝑥 · 𝛽𝑧,𝐷 · |𝑘, 𝑥, 𝑧⟩ |𝐷 ∪ {𝑥}⟩ . 𝐾𝑁 𝑘,𝑧,𝐷,𝑥∈𝐷 /
Therefore, ‖ΠWin |Φ⟩ ‖2 = ‖ΠWin ( |Φ1 ⟩ + |Φ2 ⟩)‖2 ≤ 2 · (‖ΠWin |Φ1 ⟩ ‖2 + ‖ΠWin |Φ2 ⟩ ‖2 ), and now our goal is to bound ‖ΠWin |Φ1 ⟩ ‖2 and ‖ΠWin |Φ2 ⟩ ‖2 separately. For |Φ1 ⟩. Over all 𝑥 ∈ [𝑁 ], for any database 𝐷 with size |𝐷| ≤ 𝑡 − 2, only a small fraction of 𝑥 will lie in 𝐷. This intuition gives us the following upper bound: ⃦2 ⃦
⃦ ⃦
∑︁ ⃦ 1 ∑︁ ⃦ ⃦ (−1)𝑘·𝑥 · 𝛽𝑧,𝐷 · Π𝑘 |𝑥, 𝑧, 𝐷∖{𝑥}⟩⃦ ‖ΠWin |Φ1 ⟩ ‖2 = ⃦ ⃦ 𝐾𝑁 𝑘 ⃦𝑧,𝐷,𝑥∈𝐷 ⃦ ⃦2 ⃦ ⃦ ⃦ ∑︁ ∑︁ ⃦ ⃦ 1 𝑘·𝑥 ⃦ ⃦ (−1) · 𝛽 · |𝑥, 𝑧, 𝐷⟩ ≤ 𝑧,𝐷 ⃦ ⃦ 𝐾𝑁 𝑘 ⃦𝑧,𝐷,𝑥∈𝐷 ⃦ )︃ (︃ ∑︁ 1 ∑︁ ∑︁
=
≤
[𝑥 ∈ 𝐷]
|𝛽𝑧,𝐷 |2 ·
𝐾𝑁
𝑥∈𝐷
𝑘 𝑧,𝐷
𝑡−2 . 𝑁
For |Φ2 ⟩. Since Π𝑘 never acts on the database register D, we will have orthogonality for different database, and thus we can expand the term as ⃦ ⃦2 ⃦ ⃦ ∑︁ ∑︁ ⃦ ⃦ 1 𝑘·𝑥 𝛽𝑧,𝐷 ⃦ ⃦ √ ‖ΠWin |Φ2 ⟩ ‖2 = (−1) · · (Π |𝑥, 𝑧⟩) ⊗ |𝐷 ∪ {𝑥}⟩ 𝑘 ⃦ ⃦ 𝐾 𝑘 ⃦𝑧,𝐷,𝑥∈𝐷 𝑁 ⃦ / ⃦ ⃦2 ⃦ ∑︁ ⃦ ⃦ 1 ∑︁ ⃦ 𝑘·𝑥 𝛽𝑧,𝐷′ ∖{𝑥} ′ ⃦ ⃦ = (−1) · √ · (Π𝑘 |𝑥, 𝑧⟩) ⊗ |𝐷 ⟩⃦ ⃦ 𝐾 𝑘 ⃦𝑧,𝐷′ ,𝑥∈𝐷′ 𝑁 ⃦ ⃦ ⃦2 ⃦ ⃦ ∑︁ ⃦ 1 ∑︁ ∑︁ ⃦ 𝑘·𝑥 𝛽𝑧,𝐷′ ∖{𝑥} ⃦Π𝑘 · ⃦ √ = (−1) · · |𝑥, 𝑧⟩ ⃦ ⃦ 𝐾 𝑘 𝐷′ ⃦ 𝑁 ⃦ 𝑧,𝑥∈𝐷′ ∑︁ ∑︁ 1
=
𝐾
𝑝𝐷′ · ‖Π𝑘 |𝜑𝑘,𝐷′ ⟩ ‖2
𝑘
𝐷′
with the following definitions 𝑝𝐷′ :=
∑︁ |𝛽𝑧,𝐷′ ∖{𝑥} |2 𝑧,𝑥∈𝐷′
𝑁
,
|𝜑𝑘,𝐷′ ⟩ := √ 47
∑︁ 𝛽𝑧,𝐷′ ∖{𝑥} 1 (−1)𝑘·𝑥 · √ · |𝑥, 𝑧⟩ . ′ 𝑝𝐷 𝑧,𝑥∈𝐷′ 𝑁
Since ‖ |Φ2 ⟩ ‖ ≤ 1, 𝐷′ 𝑝𝐷′ = ‖ |Φ2 ⟩ ‖2 ≤ 1. Note that from the definition of |𝜑𝑘,𝐷′ ⟩, it is normalized, and if we define state |𝑣𝑥,𝐷′ ⟩ as ∑︀
|𝑣𝑥,𝐷′ ⟩ = √
1 ∑︁ 𝛽𝑧,𝐷′ ∖{𝑥} √ |𝑥, 𝑧⟩ , 𝑝𝐷′ 𝑧 𝑁
then for any 𝑘 ∈ {0, 1}𝑛 , |𝜑𝑘,𝐷′ ⟩ actually lies in a small subspace spanned by no more than |𝐷′ | states, ∑︁ |𝜑𝑘,𝐷′ ⟩ = (−1)𝑘·𝑥 |𝑣𝑥,𝐷′ ⟩ ∈ Span{ |𝑣𝑥,𝐷′ ⟩}𝑥∈𝐷′ . 𝑥∈𝐷′
We define Π𝐷′ as the projection on this subspace, and Tr(Π𝐷′ ) ≤ |𝐷′ | ≤ 𝑡 − 2 + 1 = 𝑡 − 1. This limitation of subspace spanned by {𝜑𝑘,𝐷′ }𝑘 for every 𝐷′ will help us upper bound ‖ΠWin |Φ2 ⟩ ‖2 : ‖ΠWin |Φ2 ⟩ ‖2 = = ≤ = ≤
1 ∑︁ ∑︁ 1 ∑︁ ∑︁ 𝑝𝐷′ · ‖Π𝑘 |𝜑𝑘,𝐷′ ⟩ ‖2 = 𝑝𝐷′ · ‖Π𝑘 Π′𝐷 |𝜑𝑘,𝐷′ ⟩ ‖2 𝐾 𝑘 𝐷′ 𝐾 𝑘 𝐷′ 1 ∑︁ ∑︁ 𝑝𝐷′ · Tr(Π𝐷′ Π𝑘 Π𝐷′ |𝜑𝑘,𝐷′ ⟩⟨𝜑𝑘,𝐷′ |) 𝐾 𝑘 𝐷′
1 ∑︁ ∑︁ 𝑝𝐷′ · Tr(Π𝐷′ Π𝑘 Π𝐷′ ) 𝐾 𝑘 𝐷′ 1 ∑︁ 𝑝𝐷′ · Tr(Π𝐷′ ) 𝐾 𝐷′
𝑡−1 . 𝐾
Concluding the proof. Since here the key space 𝐾 ≤ 𝑁 , we have ‖ΠWin |Φ⟩ ‖ ≤ 2 · (‖ΠWin |Φ1 ⟩ ‖ + ‖ΠWin |Φ2 ⟩ ‖ ) ≤ 2 · 2
2
2
(︂
𝑡−1 𝑡−2 + 𝐾 𝑁
)︂
<
4𝑡 . 𝐾
Proof of Proposition 10.3. With the upper bound of 𝜀𝑠 from Lemma 10.5 and non-decreasing property from Proposition 10.4, (︂ )︂𝑡 𝑡 ∏︁ 8𝑡 𝑡 . Pr[𝑏𝑡 = 1] = 𝜀𝑖 ≤ 𝜀𝑡 ≤ 𝐾 𝑖=1
10.4
Conclusion
Combining Lemma 10.2 and Proposition 10.3, we obtain the following theorem. Theorem 10.6. If a non-uniform algorithm with 𝑆 qubits of advice succeeds in recovering 𝑘 from one copy of 𝐹 𝐻 |𝑘⟩ with probability 𝜀, then for every integer 𝑡 ≥ 1, 𝜀 ≤2 𝑡
𝑆
(︂
8𝑡 𝐾
)︂𝑡
for every integer 𝑡 ≥ 1.
In particular, setting 𝑡 = 𝑆 gives
16𝑆 . 𝐾 Proof. By Lemma 10.2, the 𝑡-round alternating measurement can be won with probability at least 𝜀𝑡 . By Proposition 10.3, every such game has success probability at most 2𝑆 (8𝑡/𝐾)𝑡 . Combining the two inequalities proves the claim. 𝜀≤
48
10.5
Matching Algorithm
In this section, we give an algorithm with an 𝑆-qubit advice for the state search game on state family {𝐹 𝐻 |𝑘⟩}𝑘∈[𝐾] . This algorithm can reach winning probability Ω̃(𝑆/𝑁 ) for 𝑆 = 𝑜(𝑁/ log 𝑁 ), which matches our lower bound above (up to log 𝑁 factor, for the case when 𝐾 = Ω(𝑁 )). Algorithm. Suppose that the algorithm receives 𝑞 copies of |𝜓𝑓,0 ⟩ := 𝐹 𝐻 |0⟩ as its 𝑞 log 𝑁 -qubit advice. Denote the advice registers by 𝑋1 , . . . , 𝑋𝑞 and the challenge register by 𝑌 . 1. The algorithm coherently computes into an ancilla the smallest index 𝐼 := min{𝑖 ∈ [𝑞] : 𝑋𝑖 = 𝑌 }, setting 𝐼 = 𝑞 + 1 if no such index exists, and then measures 𝐼. 2. If 𝐼 = 𝑞 + 1, the algorithm aborts. If 𝐼 = 𝑖 ≤ 𝑞, it applies a bitwise CNOT from 𝑋𝑖 to 𝑌 , discards 𝑌 and all advice registers other than 𝑋1 , . . . , 𝑋𝑖 , and measures 𝑋𝑖 in the Hadamard basis to obtain its output. Analysis. For every 𝑖 ∈ [𝑞], Pr[𝐼 = 𝑖] = 𝑁1 (1 − 𝑁1 )𝑖−1 . Conditioned on 𝐼 = 𝑖, the equality of the computational-basis values in 𝑋𝑖 and 𝑌 cancels their two copies of the phase (−1)𝑓 (𝑥) . After the CNOT, the remaining state can be written as 1 ∑︁ (−1)𝑘·𝑥 |𝜃𝑥 ⟩⊗(𝑖−1) ⊗ |𝑥⟩ , |Γ𝑖,𝑘 ⟩ = √ 𝑁 𝑥 where |𝜃𝑥 ⟩ := √𝑁1−1
𝑓 (𝑧) |𝑧⟩. 𝑧̸=𝑥 (−1)
∑︀
𝑁 −2 Note that for distinct 𝑥, 𝑦, ⟨𝜃𝑦 |𝜃𝑥 ⟩ = 𝑁 −1 . Therefore, after tracing out the first 𝑖 − 1 registers, the state of 𝑋𝑖 is
𝜌𝑖,𝑘 = 𝛼𝑖 · 𝐻 |𝑘⟩⟨𝑘| 𝐻 + (1 − 𝛼𝑖 ) ·
I , 𝑁
𝛼𝑖 :=
(︂
𝑁 −2 𝑁 −1
)︂𝑖−1
.
The Hadamard-basis measurement thus outputs 𝑘 with probability at least 𝛼𝑖 . Consequently, for 𝑞 = 𝑜(𝑁 ), the overall winning probability is at least 𝑞 ∑︁
𝑞
1 ∑︁ 2 Pr[𝐼 = 𝑖] · 𝛼𝑖 = 1− 𝑁 𝑖=1 𝑁 𝑖=1 (︂
)︂𝑖−1
1 − (1 − 2/𝑁 )𝑞 𝑞 = =Ω 2 𝑁 (︂
)︂
.
Therefore, in terms of the total advice length 𝑆 = 𝑞 log 𝑁 , the algorithm uses 𝑆 advice qubits and achieves Ω (𝑞/𝑁 ) = Ω̃(𝑆/𝑁 ) winning probability in the search game.
References [Aar16]
Scott Aaronson. The complexity of quantum states and transformations: from quantum money to black holes. arXiv preprint arXiv:1607.05256, 2016.
49
[AK07]
Scott Aaronson and Greg Kuperberg. Quantum versus classical proofs and advice. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07), pages 115–128. IEEE, 2007.
[BCQ23]
Zvika Brakerski, Ran Canetti, and Luowen Qian. On the computational hardness needed for quantum cryptography. In Yael Tauman Kalai, editor, ITCS 2023, volume 251, pages 24:1–24:21. LIPIcs, January 2023.
[BEM+ 26] John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen. Unitary Complexity and the Uhlmann Transformation Problem. In Shubhangi Saraf, editor, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1–24:17, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [BKS16]
Afonso S Bandeira, Christopher Kennedy, and Amit Singer. Approximating the little grothendieck problem over the orthogonal and unitary groups. Mathematical programming, 160(1):433–475, 2016.
[CMSZ22] Alessandro Chiesa, Fermi Ma, Nicholas Spooner, and Mark Zhandry. Post-quantum succinct arguments: Breaking the quantum rewinding barrier. In 62nd FOCS, pages 49–58. IEEE Computer Society Press, February 2022. [GJMZ23] Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry. Commitments to quantum states. In Barna Saha and Rocco A. Servedio, editors, 55th ACM STOC, pages 1579– 1588. ACM Press, June 2023. [INN+ 22] Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. Quantum search-to-decision reductions and the state synthesis problem. In Proceedings of the 37th Computational Complexity Conference, pages 1–19, 2022. [JLS18]
Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 126–152. Springer, Cham, August 2018.
[Kre21]
William Kretschmer. Quantum pseudorandomness and classical complexity. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), pages 2–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021.
[Liu23]
Qipeng Liu. Non-uniformity and quantum advice in the quantum random oracle model. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part I, volume 14004 of LNCS, pages 117–143. Springer, Cham, April 2023.
[LMW24] Alex Lombardi, Fermi Ma, and John Wright. A one-query lower bound for unitary synthesis and breaking quantum cryptography. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th ACM STOC, pages 979–990. ACM Press, June 2024. [MJC+ 14] Lester Mackey, Michael I Jordan, Richard Y Chen, Brendan Farrell, and Joel A Tropp. Matrix concentration inequalities via the method of exchangeable pairs. The Annals of Probability, 42(3):906–945, 2014. 50
[MY22]
Tomoyuki Morimae and Takashi Yamakawa. Quantum commitments and signatures without one-way functions. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 269–295. Springer, Cham, August 2022.
[Ros21]
Gregory Rosenthal. Query and depth upper bounds for quantum unitaries via grover search. arXiv preprint arXiv:2111.07992, 2021.
[Ros24]
Gregory Rosenthal. Efficient quantum state synthesis with one query. In David P. Woodruff, editor, 35th SODA, pages 2508–2534. ACM-SIAM, January 2024.
[Tro12]
Joel A Tropp. A comparison principle for functions of a uniformly random subspace. Probability Theory and Related Fields, 153(3):759–769, 2012.
[Tro15]
Joel Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1–230, 2015.
[Wat18]
John Watrous. The Theory of Quantum Information. Cambridge University Press, USA, 1st edition, 2018.
[Yan22]
Jun Yan. General properties of quantum bit commitments (extended abstract). In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part IV, volume 13794 of LNCS, pages 628–657. Springer, Cham, December 2022.
[Yue22]
Henry Yuen. Lecture 6 from COMS E6998: Frontiers of quantum complexity and cryptography. Found at https://www.henryyuen.net/spring2022/ lec6-statesynthesis.pdf and https://www.henryyuen.net/spring2022/ lec6-unitarysynthesis.pdf, 2022.
[Zha19]
Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Advances in Cryptology – CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part II, page 239–268, Berlin, Heidelberg, 2019. Springer-Verlag.
A
Simple search game upper bounds
This section describes two additional applications of the spectral reduction from Lemma 6.1. The first results in a simpler alternative proof of some of the main results of [LMW24] about random binary phase states. The second proves a quantitatively similar statement bounding the maximum winning probability of the search game for Haar-random unitaries, which corresponds to a one-query lower bound for synthesizing Haar-random unitaries.
A.1
Random binary phase states
Let 𝑅 = (𝑅(𝑘, 𝑥))𝑘∈[𝐾], 𝑥∈[𝑁 ] be a family of independent Rademacher random variables, and define 1 ∑︁ |𝜓𝑅,𝑘 ⟩ := √ 𝑅(𝑘, 𝑥) |𝑥⟩ 𝑁 𝑥∈[𝑁 ]
for each 𝑘 ∈ [𝐾].
Thus the challenge states are independent random binary phase states. 51
Theorem A.1 (Search bound for binary phase states). For the oracle state search game associated with the family { |𝜓𝑅,𝑘 ⟩}𝑘∈[𝐾] above, every one-query adversary with workspace dimension 𝑀 satisfies (︀ )︀ [︀ ]︀ 2 1 + log(2𝑀 ) E𝑅 Win(𝒜 | 𝑅) ≤ . 𝐾 Proof. Fix a one-query adversary 𝒜 = (𝑉, {Π𝑘 }𝑘∈[𝐾] ). For each 𝑘 ∈ [𝐾], the random state |𝜓𝑅,𝑘 ⟩ has marginal [︀ ]︀ 1 E𝑅 |𝜓𝑅,𝑘 ⟩⟨𝜓𝑅,𝑘 | = · I. 𝑁 Lemmas 6.1 and 6.2 then tell us that E𝑅 Win(𝒜 | 𝑅) ≤ E𝑅 ‖𝑀𝑅 ‖2 , [︀
where
]︀
𝑀𝑅 =
∑︁
[︀
]︀
𝑅(𝑘, 𝑥) 𝐵𝑘,𝑥
𝑘∈[𝐾], 𝑥∈[𝑁 ]
and the matrices {𝐵𝑘,𝑥 }𝑘,𝑥 satisfy ∑︁
† = 𝐵𝑘,𝑥 𝐵𝑘,𝑥
𝑘,𝑥
1 · I, 𝐾
∑︁
† 𝐵𝑘,𝑥 ⪯ 𝐵𝑘,𝑥
𝑘,𝑥
1 · I. 𝐾
Since the coefficients {𝑅(𝑘, 𝑥)}𝑘,𝑥 are independent Rademacher random variables, we may apply Theorem 3.11 to the matrix Rademacher series 𝑀𝑅 . Its matrix variance parameter is ⃦⎫ ⎧⃦ ⃦ ⃦ ⃦⎬ ⃦ ⃦∑︁ ⎨⃦ ⃦ ⃦ ⃦∑︁ ⃦ 1 † † ⃦ ⃦ ⃦ 𝑣(𝑀𝑅 ) = max ⃦ 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⃦ , ⃦ 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⃦ ⃦⎭ = 𝐾 . ⎩⃦ ⃦ ⃦ ⃦ 𝑘,𝑥 𝑘,𝑥
Because 𝑀𝑅 is an 𝑀 × 𝑀 matrix, Theorem 3.11 gives E𝑅 ‖𝑀𝑅 ‖2 ≤ 2 1 + log(2𝑀 ) · (︀
)︀
1 , 𝐾
completing the proof. Theorem A.1 gives an alternative proof of the hardness of one-query unitary synthesis [LMW24].
A.2
Haar-random unitaries
Let 𝑈 = (𝑈𝑘,𝑥 )𝑘,𝑥∈[𝑁 ] be Haar-random in 𝑈 (𝑁 ), and define |𝜓𝑈,𝑘 ⟩ := 𝑈 |𝑘⟩ =
∑︁
𝑈𝑘,𝑥 |𝑥⟩
for each 𝑘 ∈ [𝑁 ].
𝑥∈[𝑁 ]
Thus { |𝜓𝑈,𝑘 ⟩}𝑘∈[𝑁 ] is a Haar-random orthonormal basis of C𝑁 . We wish to upper bound the probability of winning the state search game on input |𝜓𝑈,𝑘 ⟩ for uniform 𝑘 ∈ [𝐾] ⊂ [𝑁 ]. We will make use of the following inequality for matrix Gaussian series.
52
Lemma A.2 (Matrix Gaussian series, [Tro15, Theorem 4.1.1 and Equation (4.1.7)]). Let {𝛾𝑗 }𝑗 be independent standard complex Gaussian random variables, and let {𝐵𝑗 }𝑗 be fixed complex matrices of dimension 𝑑1 × 𝑑2 . Define 𝑍 :=
∑︁
⃦⎫ ⃦ ⃦ ⎧⃦ ⃦⎬ ⃦ ⃦ ⎨⃦ ∑︁ ⃦ ⃦ ⃦ ⃦∑︁ † †⃦ ⃦ ⃦ 𝐵 𝐵 , 𝐵 𝐵 𝑣(𝑍) := max ⃦ 𝑗⃦ . 𝑗 𝑗⃦ ⃦ 𝑗 ⃦ ⎩⃦ ⃦⎭ ⃦ ⃦ 𝑗 𝑗
𝛾𝑗 𝐵𝑗 ,
𝑗
Then E‖𝑍‖2 ≤ 2 𝑣(𝑍) 1 + log(𝑑1 + 𝑑2 ) . (︀
)︀
√ Proof. Write 𝛾𝑗 = (𝑔𝑗 + 𝑖ℎ𝑗 )/ 2, where {𝑔𝑗 }𝑗 and {ℎ𝑗 }𝑗 are independent families of real standard normal random variables. Then 𝑍=
∑︁ 𝐵𝑗 𝑖𝐵𝑗 𝑔𝑗 √ + ℎ𝑗 √ , 2 2 𝑗 𝑗
∑︁
√ √ so 𝑍 is a real Gaussian matrix series with coefficient family {𝐵𝑗 / 2, 𝑖𝐵𝑗 / 2}𝑗 . The corresponding variance parameter is exactly 𝑣(𝑍), because ∑︁ 𝐵𝑗 𝐵𝑗† 𝑗
2
+
∑︁ (𝑖𝐵𝑗 )(𝑖𝐵𝑗 )†
2
𝑗
=
∑︁
𝐵𝑗 𝐵𝑗†
𝑗
and similarly on the right. The claimed bound therefore follows from [Tro15, Theorem 4.1.1 and Equation (4.1.7)]. Next, by a reduction to the case of independent Gaussians — analogous to comparison-based arguments of Tropp [Tro12] for Haar-random real orthogonal matrices — we analyze random matrices with coefficients coming from Haar-random unitaries (rather than fully independent coefficients). Proposition A.3 (Haar-unitary matrix series). Let 1 ≤ 𝐾 ≤ 𝑁 , let 𝑈 ∈ 𝑈 (𝑁 ) be Haar-random, and let {𝐵𝑘,𝑥 }𝑘∈[𝐾], 𝑥∈[𝑁 ] be fixed complex matrices of dimension 𝑑1 × 𝑑2 . Define 𝑍𝑈,𝐾 :=
√
∑︁
𝑁 𝑈𝑘,𝑥 𝐵𝑘,𝑥 ,
𝑘∈[𝐾], 𝑥∈[𝑁 ]
⃦⎫ ⎧⃦ ⃦ ⃦ ⃦⎬ ⃦ ⃦ ⎨⃦ ∑︁ ∑︁ ⃦ ⃦ ⃦ ⃦ † † ⃦ ⃦ ⃦ 𝐵 𝐵 , 𝑣𝐾 := max ⃦ 𝐵 𝐵 𝑘,𝑥 ⃦ . 𝑘,𝑥 𝑘,𝑥 ⃦ ⃦ ⃦ 𝑘,𝑥 ⎩⃦ ⃦⎭ ⃦ ⃦𝑘∈[𝐾], 𝑥∈[𝑁 ] 𝑘∈[𝐾], 𝑥∈[𝑁 ]
Then E𝑈 ‖𝑍𝑈,𝐾 ‖2 ≤ 4 𝑣𝐾 1 + log(𝑑1 + 𝑑2 ) . (︀
)︀
Proof. Extend the family (𝐵𝑘,𝑥 )𝑘∈[𝐾], 𝑥∈[𝑁 ] to indices 𝑘 ∈ [𝑁 ] by setting 𝐵𝑘,𝑥 := 0 for 𝑘 ∈ [𝑁 ] ∖ [𝐾]. Then 𝑍𝑈,𝐾 =
∑︁ √
𝑁 𝑈𝑘,𝑥 𝐵𝑘,𝑥 ,
𝑘,𝑥∈[𝑁 ]
⎧⃦ ⃦ ⃦ ⃦⎫ ⃦ ⃦ ⃦⎬ ⎨⃦ ∑︁ ⃦ ∑︁ ⃦ ⃦ ⃦ † ⃦ ⃦ † ⃦ 𝑣𝐾 = max ⃦ 𝐵 𝐵 , 𝐵 𝐵 𝑘,𝑥 𝑘,𝑥 ⃦ ⃦ 𝑘,𝑥 ⃦ . ⃦ 𝑘,𝑥 ⎩⃦ ⃦ ⃦𝑘,𝑥∈[𝑁 ] ⃦⎭ 𝑘,𝑥∈[𝑁 ]
Thus, it suffices to prove the bound in the special case 𝐾 = 𝑁 . Let 𝐺 = (𝐺𝑘,𝑥 )𝑘,𝑥∈[𝑁 ] be a random matrix with independent complex Gaussian entries 𝐺𝑘,𝑥 ∼ 𝒩C (0, 1/𝑁 ). Since 𝐺 is invertible with probability 1, we write its polar decomposition 𝐺 = 𝑈 𝑃,
𝑈 ∈ 𝑈 (𝑁 ), 53
𝑃 = (𝐺† 𝐺)1/2 ⪰ 0.
Since 𝐺 is (left-) unitary invariant, it holds that 𝑈 is Haar-random and independent of 𝑃 . Moreover, since 𝐺 = 𝐺 · 𝑊 is invariant under right multiplication of an arbitrary fixed unitary 𝑊 , we have that 𝑃 = (𝐺† 𝐺)1/2 = 𝑊 † 𝑃 𝑊 is conjugation-invariant. Thus, E[𝑃 ] commutes with every unitary, and so E[𝑃 ] = 𝑎𝑁 · I, for
1 · E Tr(𝑃 ). 𝑁 Since 𝑈 and 𝑃 are independent, this lets us calculate the conditional expectation 𝑎𝑁 =
E[𝐺 | 𝑈 ] = 𝑈 · E[𝑃 ] = 𝑎𝑁 · 𝑈. Next, define the linear map
𝑇 (𝐺) :=
∑︁
𝐺𝑘,𝑥 𝐵𝑘,𝑥 .
𝑘,𝑥∈[𝑁 ]
The function
⃦2 ⃦√ ⃦ ⃦ 𝑓 (𝐺) := ⃦ 𝑁 𝑇 (𝐺)⃦
is convex and satisfies 𝑓 (𝜆 · 𝐴) = 𝜆2 𝑓 (𝐴) for every scalar 𝜆 ≥ 0. Jensen’s inequality therefore yields 𝑎2𝑁 · 𝑓 (𝑈 ) = 𝑓 (𝑎𝑁 𝑈 ) = 𝑓 E[𝐺 | 𝑈 ] ≤ E 𝑓 (𝐺) | 𝑈 . (︀
)︀
[︀
]︀
Taking expectations, this implies that ⃦ ⃦2 ⃦ ∑︁ √ ⃦ ⃦ ⃦ ⃦ 𝑎2𝑁 E𝑈 ‖𝑍𝑈,𝐾 ‖2 ≤ E⃦ 𝑁 𝐺 𝐵 𝑘,𝑥 𝑘,𝑥 ⃦ . ⃦ ⃦𝑘,𝑥∈[𝑁 ] ⃦
Because
√
𝑁 𝐺𝑘,𝑥 are independent standard complex Gaussian variables, Lemma A.2 gives ⃦ ⃦2 ⃦ ∑︁ √ ⃦ ⃦ ⃦ (︀ )︀ ⃦ E⃦ 𝑁 𝐺 𝐵 𝑘,𝑥 𝑘,𝑥 ⃦ ≤ 2 𝑣𝐾 1 + log(𝑑1 + 𝑑2 ) . ⃦ ⃦𝑘,𝑥∈[𝑁 ] ⃦
Thus, all√that remains is to lower bound 𝑎𝑁 . Fortunately, it is known (see, e.g., [BKS16]) that 𝑎𝑁 ≥ 1/ 2 for all 𝑁 , which allows us to conclude that E𝑈 ‖𝑍𝑈,𝐾 ‖2 ≤ 4 𝑣𝐾 1 + log(𝑑1 + 𝑑2 ) , (︀
)︀
as claimed. Theorem A.4 (Search bound for Haar-random unitaries). For the oracle state search game associated with the family { |𝜓𝑈,𝑘 ⟩ = 𝑈 |𝑘⟩}𝑘∈[𝐾] above, every one-query adversary with workspace dimension 𝑀 satisfies (︀ )︀ [︀ ]︀ 4 1 + log(2𝑀 ) E𝑈 Win(𝒜 | 𝑈 ) ≤ . 𝐾
54
Proof. Fix a one-query adversary 𝒜 = (𝑉, {Π𝑘 }𝑘∈[𝑁 ] ). For each 𝑘 ∈ [𝑁 ], the random state |𝜓𝑈,𝑘 ⟩ is Haar-random in C𝑁 , and therefore E𝑈 |𝜓𝑈,𝑘 ⟩⟨𝜓𝑈,𝑘 | = [︀
]︀
1 · I. 𝑁
By Lemmas 6.1 and 6.2, E𝑈 Win(𝒜 | 𝑈 ) ≤ E𝑈 ‖𝑀𝑈 ‖2 , [︀
𝑀𝑈 =
]︀
√ 𝑁 𝑈𝑘,𝑥 𝐵𝑘,𝑥 ,
∑︁ 𝑘∈[𝐾],𝑥∈[𝑁 ]
where the matrices {𝐵𝑘,𝑥 }𝑘,𝑥 satisfy ∑︁ 𝑘,𝑥
† 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⪯
1 · I, 𝐾
∑︁
† 𝐵𝑘,𝑥 𝐵𝑘,𝑥 ⪯
𝑘,𝑥
1 · I. 𝐾
Hence the variance parameter in Proposition A.3 is at most 1/𝐾. Applying that proposition with 𝑑1 = 𝑑2 = 𝑀 yields (︀ )︀ 4 1 + log(2𝑀 ) 2 E𝑈 ‖𝑀𝑈 ‖ ≤ , 𝐾 which completes the proof.
B
Unitary search game is hardest on Haar random unitaries
This section describes a reduction from (𝑡-query) oracle state search game hardness for Haar random unitaries to hardness for any distribution over unitaries, under two notions of hardness of the oracle state search game. Theorem B.1. Fix the number of oracle queries 𝑡 ∈ N. For unitary 𝑈𝑅 depending on random variable 𝑅, consider the oracle state search game on the state family { |𝜓𝑅,𝑘 ⟩ := 𝑈𝑅 |𝑘⟩}𝑘∈[𝐾] , where the adversary is given one copy of |𝜓𝑅,𝑘 ⟩ for a random 𝑘 ∈ [𝐾] and is asked to output 𝑘 after making 𝑡 oracle queries. Then the Haar-random unitary family is the hardest among all distribution {𝑈𝑅 }. More specifically, if any distribution on 𝑈𝑅 is (𝑀, 𝜀)-hard (respectively, (𝑀, 𝜀, 𝛿)-hard) in the 𝑡-query search game, then so is the Haar distribution. The proof idea is similar to the one in Corollary 8.1, which shows the one-query (𝑀, 𝜀)-hardness of the {𝐹𝑡 𝐻 · · · 𝐹1 𝐻 |𝑘⟩} search game based on the corresponding 𝑡 = 2 case. Here we first use the same idea to prove the (𝑀, 𝜀)-hardness of the Haar distribution in expectation in Appendix B.1, and then extend to the (𝑀, 𝜀, 𝛿)-hardness in Appendix B.2.
55
(𝑀, 𝜀)-hardness
B.1
Proof. For any 𝑡-query oracle circuit 𝒜(·) for an oracle state search game, it can be specified by a set of unitaries {𝑈𝑖 }𝑖∈[𝑡] between queries and final measurement projectors {Π𝑘 }𝑘∈[𝐾] , such that with oracle access to 𝑓 , 𝒜𝑓 will output 𝑘 with probability ‖Π𝑘 · 𝑂𝑓 · 𝑈𝑡 · · · · · 𝑂𝑓 · 𝑈2 · 𝑂𝑓 · 𝑈1 |𝜓⟩ |0𝑚−𝑛 ⟩ ‖2 . For notational convenience, we absorb the fixed ancilla initialization into the first operation, and define 𝑉1 to be the isometry 𝑈1 |0𝑚−𝑛 ⟩ mapping 𝑛 qubits to 𝑚 qubits. Thus, for a Haar random unitary 𝑈 ∈ 𝑈 (𝑁 ), define |𝜓𝑈,𝑘 ⟩ := 𝑈 |𝑘⟩, and we can write the adversary’s winning probability as ]︁
[︁
E𝑈 ∈𝑈 (𝑁 ) Win(𝒜 | 𝑈 ) = E𝑈 ∈𝑈 (𝑁 ) max E𝑘 ⟨𝜓𝑈,𝑘 | 𝑉1† 𝑂𝑓† · · · 𝑈𝑡 𝑂𝑓† Π𝑘 𝑂𝑓 𝑈𝑡 · · · 𝑂𝑓 𝑉1 |𝜓𝑈,𝑘 ⟩ . 𝑓
The maximum winning probability for Haar random unitary 𝑈 ∈ 𝑈 (𝑁 ) can then be upper bounded by the one for 𝑈𝑅 from any distribution of 𝑅: {︁
sup E𝑈 ∈𝑈 (𝑁 ) Win(𝒜 | 𝑈 )
}︁
𝒜
= =
sup
{︂
sup
{︂
{𝑈𝑡 },{Π𝑘 }
[︂
E𝑈 ∈𝑈 (𝑁 ),𝑈𝑅
{𝑈𝑡 },{Π𝑘 }
≤ E𝑈 ∈𝑈 (𝑁 ) = E𝑈 ∈𝑈 (𝑁 )
]︂}︂
E𝑈 ∈𝑈 (𝑁 ) max E𝑘 ⟨𝜓𝑈,𝑘 | 𝑉1† 𝑂𝑓† · · · 𝑈𝑡 𝑂𝑓† Π𝑘 𝑂𝑓 𝑈𝑡 · · · 𝑂𝑓 𝑉1 |𝜓𝑈,𝑘 ⟩ 𝑓
sup
{︂
sup
{︂
[︂
]︂}︂
[︂
]︂}︂
max E𝑘 ⟨𝜓𝑈 𝑈𝑅 ,𝑘 | 𝑉1† 𝑂𝑓† · · · 𝑈𝑡 𝑂𝑓† Π𝑘 𝑂𝑓 𝑈𝑡 · · · 𝑂𝑓 𝑉1 |𝜓𝑈 𝑈𝑅 ,𝑘 ⟩ 𝑓
E𝑅 max E𝑘 ⟨𝜓𝑅,𝑘 | 𝑈 † 𝑉1† 𝑂𝑓† · · · 𝑈𝑡 𝑂𝑓† Π𝑘 𝑂𝑓 𝑈𝑡 · · · 𝑂𝑓 𝑉1 𝑈 |𝜓𝑅,𝑘 ⟩ 𝑓
{𝑈𝑡 },{Π𝑘 }
[︂
]︂}︂
E𝑅 max E𝑘 ⟨𝜓𝑅,𝑘 | 𝑉1† 𝑂𝑓† · · · 𝑈𝑡 𝑂𝑓† Π𝑘 𝑂𝑓 𝑈𝑡 · · · 𝑂𝑓 𝑉1 |𝜓𝑅,𝑘 ⟩
(21)
𝑓
{𝑈𝑡 },{Π𝑘 }
= sup {E𝑅 Win(𝒜 | 𝑅)} , 𝒜
where the supremum is taken over all 𝒜 acting on 𝑚 total qubits post-isometry. Notably, (21) holds because for any fixed unitary 𝑈 and adversary strategy 𝒜 = ({𝑈𝑡 }, {Π𝑘 }) the success probability described in the previous expression is the { |𝜓𝑅,𝑘 ⟩} success probability of the adversary 𝒜′ = ({𝑈𝑡′ }, {Π𝑘 }), where 𝑉1′ = 𝑉1 · 𝑈 and the rest of the strategy is unchanged.
B.2
(𝑀, 𝜀, 𝛿)-hardness
Proof. The proof is almost identical to that of Appendix B.1. }︃
{︃
sup 𝒜
Pr [Win(𝒜 | 𝑈 ) > 𝜀]
𝑈 ∈𝑈 (𝑁 )
{︃
= =
Pr max E𝑘 ⟨𝜓𝑈,𝑘 | 𝑉1† 𝑂𝑓† · · · 𝑈𝑡 𝑂𝑓† Π𝑘 𝑂𝑓 𝑈𝑡 · · · 𝑂𝑓 𝑉1 |𝜓𝑈,𝑘 ⟩ > 𝜀 𝑓 𝑈 ∈𝑈 (𝑁 )
sup
{𝑈𝑡 },{Π𝑘 }
sup
{𝑈𝑡 },{Π𝑘 }
]︂}︃
[︂
{︂
[︂
]︂}︂
E𝑈 ∈𝑈 (𝑁 ) Pr max E𝑘 ⟨𝜓𝑈 𝑈𝑅 ,𝑘 | 𝑉1† 𝑂𝑓† · · · 𝑈𝑡 𝑂𝑓† Π𝑘 𝑂𝑓 𝑈𝑡 · · · 𝑂𝑓 𝑉1 |𝜓𝑈 𝑈𝑅 ,𝑘 ⟩ > 𝜀 𝑅
𝑓
56
≤ E𝑈 ∈𝑈 (𝑁 ) = E𝑈 ∈𝑈 (𝑁 )
sup
{︂
sup
{︂
{𝑈𝑡 },{Π𝑘 }
{𝑈𝑡 },{Π𝑘 }
[︂
]︂}︂
Pr max E𝑘 ⟨𝜓𝑅,𝑘 | 𝑈 † 𝑉1† 𝑂𝑓† · · · 𝑈𝑡 𝑂𝑓† Π𝑘 𝑂𝑓 𝑈𝑡 · · · 𝑂𝑓 𝑉1 𝑈 |𝜓𝑅,𝑘 ⟩ > 𝜀 𝑅
Pr
𝑓
[︂
𝑅
{︂
]︂}︂
max E𝑘 ⟨𝜓𝑅,𝑘 | 𝑉1† 𝑂𝑓† · · · 𝑈𝑡 𝑂𝑓† Π𝑘 𝑂𝑓 𝑈𝑡 · · · 𝑂𝑓 𝑉1 |𝜓𝑅,𝑘 ⟩ > 𝜀 𝑓 }︂
= sup Pr[Win(𝒜 | 𝑅)] > 𝜀 . 𝒜
C
𝑅
Hardness of the oracle Choi state game
This appendix presents proofs of one-query hardness of the oracle Choi state game. Two of the results (Theorem C.1 and Corollary C.3) rederive theorems that we proved using the oracle state search game in the body of the paper, while Theorem C.2 extends Theorem 5.2 to analogous classes of unitaries where the Hadamard unitary 𝐻 ⊗𝑛 has been replaced by a fairly general one-qubit unitary 𝑈0 .
C.1
Theorem statements
Theorem C.1 (Permutation family Choi bound, see Theorem 5.1). Let 𝑃 be the in-place permutation unitary associated with a uniformly random permutation 𝜋 on {0, 1}𝑛 , 𝑃 = 𝑃𝜋 : |𝑥⟩ ↦→ |𝜋(𝑥)⟩. For the oracle Choi state game for unitary family {𝑃𝜋 }𝜋 , every one-query adversary with workspace dimension 𝑀 satisfies (︃ )︃ [︀ ]︀ log2 𝑀 · log2 𝑁 E𝜋 Win(𝒜 | 𝜋) = 𝑂 . 𝑁 Theorem C.2 (𝐹2 𝑈0 𝐹1 Choi bound). Let 𝑓1 , 𝑓2 : {0, 1}𝑛 → {0, 1} be uniformly random Boolean ∑︀ functions, and let 𝐹𝑗 = 𝑥 (−1)𝑓𝑗 (𝑥) |𝑥⟩⟨𝑥| for 𝑗 ∈ {1, 2}. 𝑈0 : C𝑁 → C𝑁 is a fixed unitary that is independent of 𝐹1 , 𝐹2 . For the oracle Choi state game for unitary family {𝑈𝑓1 ,𝑓2 := 𝐹2 𝑈0 𝐹1 }𝑓1 ,𝑓2 , every one-query adversary with workspace dimension 𝑀 satisfies 𝑏2 · log 𝑀 · log(𝑀 𝑁 ) E𝑓1 ,𝑓2 Win(𝒜 | 𝑓1 , 𝑓2 ) = 𝑂 , 𝑁 (︃
[︀
for 𝑏 :=
√
)︃
]︀
𝑁 · max𝑘,𝑥∈[𝑁 ] | ⟨𝑥|𝑈0 |𝑘⟩ |.
Corollary C.3 (𝐹2 𝐻𝐹1 Choi bound, see Theorem 5.2). Let 𝑓1 , 𝑓2 : {0, 1}𝑛 → {0, 1} be uniformly ∑︀ random Boolean functions, and let 𝐹𝑗 = 𝑥 (−1)𝑓𝑗 (𝑥) |𝑥⟩⟨𝑥| for 𝑗 ∈ {1, 2}. For the oracle Choi state game for unitary family {𝐹2 𝐻𝐹1 }𝑓1 ,𝑓2 , every one-query adversary with workspace dimension 𝑀 satisfies (︂ )︂ [︀ ]︀ log 𝑀 · log(𝑀 𝑁 ) . E𝑓1 ,𝑓2 Win(𝒜 | 𝑓1 , 𝑓2 ) = 𝑂 𝑁
C.2
General setup
In this section, we generically reduce the problem of upper bounding E𝑅 [Win(𝒜 | 𝑅)] to the calculation of the expected (squared) spectral norm of a random matrix. This is similar to the search reduction as for the oracle state search game. While the search relaxation in Lemma 6.1 applies 𝑉 |𝜓𝑅,𝑘 ⟩ = 𝐷𝑉,𝑅,𝑘 |wt𝑉,R,𝑘 ⟩ from Lemma 3.10, viewing |wt𝑉,R,𝑘 ⟩ as an average over { |𝜓𝑅,𝑘 ⟩}𝑅 , here 57
in the Choi state game, the algorithm will always receive a maximally mixed state on its register 𝐴, so we will set |wt𝑉,R,𝑘 ⟩ = |wt𝑉 ⟩ independent of 𝑘, R. Lemma C.4 (Generic spectral relaxation). Let 𝒜 = (𝑉, 𝑈 ) be a one-query adversary for the oracle Choi state game, and let ∑︁ ⟨𝑣𝑖 |𝜓𝑅,𝑘 ⟩ |𝑖⟩⟨𝑖| , 𝐷𝑉,𝑅,𝑘 := √ 𝑝 𝑖 𝑖∈[𝑀 ]: 𝑝 >0 𝑖
be the diagonal matrix similar to the one from Lemma 3.10, while 𝑝𝑖 = 𝑁1 · ⟨𝑣𝑖 |𝑣𝑖 ⟩, defined from the distribution on a Haar random state. Define ∑︁ 1 ΠEPR ( |𝑘⟩ ⊗ 𝑈 𝐷𝑉,𝑅,𝑘 ) . 𝑀𝑅 := √ 𝑁 𝑘∈{0,1}𝑛
Then, for every 𝑅, Win(𝒜 | 𝑅) ≤ ‖𝑀𝑅 ‖2 . Consequently, E Win(𝒜 | 𝑅) ≤ E‖𝑀𝑅 ‖2 . [︀
]︀
𝑅
𝑅
Proof. Fix 𝑅. For 𝑝𝑖 = 𝑁1 · ⟨𝑣𝑖 |𝑣𝑖 ⟩ modified from Lemma 3.10, we see that |wt𝑉,R,𝑘 ⟩ = |wt𝑉 ⟩ is independent of 𝑘. Hence ⃦ (︃ )︃⃦2 ⃦ ⃦ ∑︁ 1 ⃦ ⃦ Win(𝒜 | 𝑅) = max ⃦ΠEPR √ |𝑘⟩ ⊗ 𝑈 · 𝑂𝑓 · 𝑉 |𝜓𝑅𝑘 ⟩ ⃦ ⃦ 𝑓 ⃦ 𝑁 𝑘 ⃦ )︃⃦2 (︃ ⃦ ⃦ ∑︁ 1 ⃦ ⃦ = max ⃦ΠEPR √ |𝑘⟩ ⊗ 𝑈 · 𝐷𝑉,𝑅,𝑘 · 𝑂𝑓 |wt𝑉 ⟩ ⃦ ⃦ 𝑓 ⃦ 𝑁 𝑘 ⃦ (︃ )︃⃦2 ⃦ ⃦ ∑︁ 1 ⃦ ⃦ ≤ ⃦ΠEPR √ |𝑘⟩ ⊗ 𝑈 · 𝐷𝑉,𝑅,𝑘 ⃦ = ‖𝑀𝑅 ‖2 . ⃦ ⃦ 𝑁 𝑘
Averaging over 𝑅 gives the final inequality.
C.3
Permutation lower bound in the oracle Choi state game
Choi formulation. Here we consider the oracle Choi state game with unitary family {𝑃 }𝜋∈𝑆𝑁 ∑︀ and the EPR state |ΨEPR ⟩ ∝ 𝑘∈{0,1}𝑛 |𝑘𝑘⟩. We apply the general spectral reduction in Lemma C.4. Now our goal is to upper bound E𝜋 ‖𝑀𝜋 ‖2 , where ∑︁ ⟨𝑣𝑖 |𝜋(𝑘)⟩ 1 ∑︁ 𝑀𝜋 = ΠEPR (𝐼 ⊗ 𝑈 ) √ |𝑘⟩ ⊗ |𝑖⟩⟨𝑖| √ 𝑝𝑖 𝑁 𝑘 𝑖 [︃
𝑀𝑅 as a combinatorial matrix sum.
(︃
)︃]︃
.
Define 𝐴̂︀𝑘,𝑥 and 𝐴𝑘,𝑥 as
∑︁ ⟨𝑣𝑖 |𝑥⟩ 1 𝐴𝑘,𝑥 = ΠEPR (𝐼 ⊗ 𝑈 ) √ |𝑘⟩ ⊗ √ |𝑖⟩⟨𝑖| 𝑝𝑖 𝑁 𝑖 [︃
(︃
58
)︃]︃
,
0 𝐴𝑘,𝑥 , † 𝐴𝑘,𝑥 0
(︃
𝐴̂︀𝑘,𝑥 =
)︃
and define 𝐵𝑘,𝑥 as the shifted Hermitian version ⎛
⎞
1 ∑︁ 𝐵𝑘,𝑥 = 𝐴̂︀𝑘,𝑥 − 2 ⎝ 𝐴̂︀𝑘,𝑥 ⎠ . 𝑁 𝑘,𝑥 ⃦2 ⃦2 ⃦∑︀ ⃦∑︀ ⃦ ⃦ ⃦ ⃦ ̂︀ ̂︀ 𝐴 𝐴 . Now our goal is to bound ⃦ ⃦ 𝑘 𝑘,𝜋(𝑘) ⃦ , by bound𝑘 𝑘,𝜋(𝑘) ⃦2 ⃦∑︀ ⃦ ⃦ ing its shifted version ⃦ 𝑘 𝐵𝑘,𝜋(𝑘) ⃦ . ⃦∑︀ ⃦
Now ‖𝑀𝜋 ‖2 = ⃦
⃦2 ⃦
𝑘 𝐴𝑘,𝜋(𝑘) ⃦ = ⃦
Parameter estimates for 𝐵𝑘,𝑥 . To apply Theorem 3.12 on parameter estimates.
𝑘 𝐵𝑘,𝜋(𝑘) , we have the following
∑︀
1. Sum to 0. As {𝐵𝑘,𝑥 } is the shifted version,
𝑘,𝑥 𝐵𝑘,𝑥 =
∑︀
𝑘,𝑥 (𝐴𝑘,𝑥 − 𝐴𝑘,𝑥 ) = 0.
∑︀
̂︀
̂︀
2. Bounded norm. The operator norm of 𝐵𝑘,𝑥 can be bounded by some basic properties of 𝐴𝑘,𝑥 . ⃦
‖𝐴𝑘,𝑥 ‖2 = ‖𝐴𝑘,𝑥 𝐴†𝑘,𝑥 ‖ =
∑︁ ⟨𝑣𝑖 |𝑥⟩ ⟨𝑥|𝑣𝑖 ⟩ 1 ⃦ ⃦ |𝑖⟩⟨𝑖| ⃦ΠEPR (𝐼 ⊗ 𝑈 ) |𝑘⟩⟨𝑘| ⊗ 𝑁⃦ 𝑝𝑖 𝑖 [︃
≤ ‖ΠEPR · ( |𝑘⟩⟨𝑘| ⊗ 𝐼) · ΠEPR ‖ =
(︃
)︃]︃
⃦ ⃦ ⃦ (𝐼 ⊗ 𝑈 † )ΠEPR ⃦ ⃦
1 , 𝑁
⃦ ⃦2 ⃦ [︃ ]︃⃦2 ⃦ ⃦ ⃦ ⃦ ∑︁ ⟨𝑣𝑖 |+⟩ ⃦∑︁ ⃦ ⃦ ⃦ 𝑥 ⃦ ⃦ = 𝑁 · Π (𝐼 ⊗ 𝑈 ) |+⟩ ⊗ |𝑖⟩⟨𝑖| 𝐴 ⃦ ⃦ √ 𝑘,𝑥 ⃦ 𝑘 ⃦ ⃦ ⃦ EPR 𝑝 𝑖 ⃦ 𝑘,𝑥 ⃦ 𝑖
≤ 𝑁 2 · ‖ΠEPR · ( |+⟩⟨+|𝑘 ⊗ 𝐼) · ΠEPR ‖ = 𝑁. With these, we can bound the operator norm of 𝐵𝑘,𝑥 as follows: ⃦ ⃦ ⃦ ⃦ ⃦ ⃦ ⃦ ⃦ ∑︁ ∑︁ ⃦ ⃦ ⃦ ⃦ 1 1 1 √ 2 ̂︀𝑘,𝑥 ⃦ = ‖𝐴𝑘,𝑥 ‖ + 1 ⃦ ⃦ ‖𝐵𝑘,𝑥 ‖ ≤ ‖𝐴̂︀𝑘,𝑥 ‖ + 2 ⃦ + 2 𝑁 ≤ √ . (22) 𝐴 𝐴 𝑘,𝑥 ⃦ ≤ √ ⃦ ⃦ ⃦ 2 𝑁 ⃦ 𝑘,𝑥 𝑁 𝑁 𝑁 𝑁 ⃦ ⃦ 𝑘,𝑥 ⃦
3. Bounded variance. The variance of 𝐵𝑘,𝑥 can be bounded by the following properties of 𝐴𝑘,𝑥 . ⃦ ⃦ ⃦∑︁ ⃦ ⃦ ⃦ 𝑁 † ⃦ 𝐴𝑘,𝑥 𝐴𝑘,𝑥 ⃦ ⃦ ⃦ = 𝑁 ‖ΠEPR · (𝐼 ⊗ 𝐼) · ΠEPR ‖ = 1, ⃦ 𝑘,𝑥 ⃦ ⃦ ⃦ ⃦ ⃦ ⃦∑︁ ⃦∑︁ ∑︁ ⃦ ⃦ ⃦ ⃦ ⃦ ⃦ 1 ⟨𝑥|𝑣 ⟩ ⟨𝑣 |𝑥⟩ 1 𝑖 𝑗 † † ⃦ ⃦ ⃦ 𝐴𝑘,𝑥 𝐴𝑘,𝑥 ⃦ = |𝑗⟩⟨𝑗| √ ⟨𝑘| (𝐼 ⊗ 𝑈 )ΠEPR (𝐼 ⊗ 𝑈 ) |𝑘⟩ √ |𝑖⟩⟨𝑖|⃦ = . ⃦ ⃦ ⃦ 𝑁 ⃦ 𝑘,𝑥 𝑖,𝑗 𝑝𝑗 𝑝𝑖 𝑁 ⃦ 𝑘,𝑥 ⃦ ⃦
59
With these, we can bound the variance of 𝐵𝑘,𝑥 as follows: ⃦ ⃦ ⃦ ⎛ ⎞2 ⃦ ⃦ ⃦ ⃦ ⃦∑︁ ⃦ ⃦ ∑︁ ∑︁ ⃦ ⃦ 1 1 1 ⃦ 2 ⃦ ̂︀2 − ̂︀𝑘,𝑥 ⎠ ⃦ ⃦ ⎝ = 𝐵 𝐴 𝜎2 = 𝐴 ⃦ ⃦ 𝑘,𝑥 𝑘,𝑥 ⃦ ⃦ 𝑁⃦ 𝑁⃦ 𝑁 2 𝑘,𝑥 ⃦ ⃦ 𝑘,𝑥 ⃦ 𝑘,𝑥 ⃦ ⃦ ⃦2 ⃦ ⃦ ⃦ ⃦ ⃦ ⃦ ∑︁ ∑︁ ⃦ ⃦ 1 ⃦ 1 ⃦ 2 ⃦ ̂︀ ̂︀ ⃦ ⃦ 𝐴𝑘,𝑥 ⃦ + 3 ⃦ 𝐴𝑘,𝑥 ⃦ ≤ ⃦ ⃦ 𝑁 ⃦ 𝑘,𝑥 ⃦ 𝑁 ⃦ 𝑘,𝑥 ⃦ ⃦⎫ ⃦ ⃦ ⃦2 ⎧⃦ ⃦ ⃦⎬ ⃦ ⃦∑︁ ⃦ ⃦∑︁ ⃦∑︁ ⎨ ⃦ ⃦ ⃦ ⃦ ⃦ ⃦ 1 ⃦ 1 † † ⃦ ⃦ ⃦ ⃦ + = 𝐴 𝐴 , 𝐴 𝐴 𝐴 · max ⃦ · 𝑘,𝑥 ⃦ 𝑘,𝑥 𝑘,𝑥 ⃦ ⃦ 𝑘,𝑥 ⃦ ⃦ ⃦ 𝑘,𝑥 ⎭ 𝑁3 ⃦ ⎩⃦ 𝑁 ⃦ ⃦ ⃦ ⃦ 𝑘,𝑥 𝑘,𝑥 𝑘,𝑥
≤
1 2 1 + 3 ·𝑁 ≤ . 𝑁 𝑁 𝑁
(23)
Upper bounding the Choi state game winning probability. Apply Theorem 3.12 to the Hermitian matrix ∑︁ 𝑋 := 𝐵𝑘,𝜋(𝑘) . 𝑘
Using (22) and (23), we obtain the (︃
𝑡2 √ √ Pr [𝜆max (𝑋) ≥ 𝑡] ≤ 2𝑀 · exp − 24/𝑁 + 8 2𝑡/ 𝑁 Choose 𝑡 := 𝐶 Then
log 𝑀 log 𝑁 √ 𝑁
)︃
.
for a sufficiently large universal constant 𝐶.
[︂
Pr 𝜆max (𝑋) ≥ 𝐶 ⃦∑︀ ⃦
Combining this with ‖𝑀𝜋 ‖2 = ⃦
1 log 𝑀 log 𝑁 √ ≤ . 𝑁 𝑁 ]︂
⃦2 ⃦
⃦2 ⃦ 𝑘,𝜋(𝑘) ⃦ ,
⃦∑︀ ⃦ 𝐴̂︀
𝑘 𝐴𝑘,𝜋(𝑘) ⃦ = ⃦
𝑘
⃦ ⎡⃦ ⎛⃦ ⎞⎤ ⃦ ⃦ ]︃ [︃⃦ ⃦∑︁ ⃦ √ ⃦ ⃦∑︁ ⃦ ⃦∑︁ ⃦ ⃦ ]︀ [︀ 𝑁 ⃦ ⃦ ⃦ ⃦ ⎠⎦ 𝐴̂︀𝑘,𝑥 ⃦ Pr ‖𝑀𝜋 ‖ ≥ 𝑡′ = Pr ⃦ 𝐴̂︀𝑘,𝜋(𝑘) ⃦ ≥ 𝑡′ ≤ Pr ⎣⃦ 𝐴̂︀𝑘,𝜋(𝑘) ⃦ ≥ 𝑡′ + 2 ⎝⃦ ⃦ ⃦− 𝑁 ⃦ ⃦ ⃦ ⃦ 𝑁 ⃦ 𝑘,𝑥 ⃦ 𝑘 𝑘 ⃦ ⎡⃦ ⎤ ⃦∑︁ ⃦ ∑︁ ⃦ ⃦ 1 1 ′ ⎦ ≤ Pr ⎣⃦ 𝐴̂︀𝑘,𝜋(𝑘) − 𝑁 · 2 𝐴̂︀𝑘,𝑥 ⃦ ⃦ ⃦≥𝑡 −√ 𝑁 𝑁 ⃦ 𝑘 ⃦ 𝑘,𝑥 [︂ ]︂
1 1 = Pr 𝜆max (𝑋) ≥ 𝑡′ − √ ≤ 𝑁 𝑁 √ √ by letting 𝑡′ = 𝐶 · log 𝑀 log 𝑁/ 𝑁 + 1/ 𝑁 . From this tail bound, we can conclude that,
(24)
E𝜋 ‖𝑀𝜋 ‖2 ≤ Pr ‖𝑀𝜋 ‖ ≥ 𝑡′ · 1 + Pr ‖𝑀𝜋 ‖ < 𝑡′ · (𝑡′ )2 [︀
1 ≤ + 1 · 𝐶′ · 𝑁
]︀
(︃
[︀
]︀
log2 𝑀 · log2 𝑁 1 + 𝑁 𝑁
60
)︃
(︃
=𝑂
log2 𝑀 · log2 𝑁 𝑁
)︃
.
By Lemma C.4, this is also an upper bound on the average Choi state game winning probability, and thus proves Theorem C.1. Extending to game with classical advice. The same tail bound also derives the classicaladvice lower bound. For a fixed advice string, the spectral reduction from Lemma C.4 suggests that constant winning probability requires ‖𝑀𝜋 ‖2 = Ω(1). By setting 𝑡′ − √1𝑁 = 𝑐 for some 𝑐 = Ω(1) as in (24), this occurs with probability bounded by (︁ √ )︁ 𝑐2 √ √ Pr 𝜆max (𝑋) ≥ 𝑐 ≤ 2𝑀 · exp − = 2𝑀 · exp −Ω( 𝑁 ) , 24/𝑁 + 8 2 𝑐/ 𝑁 √ which is exponentially small if log 𝑀 ≪ 𝑁 . A union bound over all 2𝑆 advice strings then yields the lower bound √ 𝑆 + log(𝑀 ) = Ω( 𝑁 ) (︃
[︀
)︃
]︀
in order to achieve constant win probability.
C.4
𝐹2 𝑈0 𝐹1 lower bound in the oracle Choi state game
Choi formulation. Here we consider the oracle Choi state game with unitary family {𝐹2 𝑈0 𝐹1 }𝑓1 ,𝑓2 :{0,1}𝑛 →{0,1} . We apply the general spectral reduction in Lemma C.4. Now our goal is to upper bound E𝑓1 ,𝑓2 ‖𝑀𝑓1 ,𝑓2 ‖2 , where ⃦2 ⃦ ⃦ ⃦ 1 ∑︁ ⃦ ⃦ |𝑘⟩ ⊗ 𝐷𝑓1 ,𝑓2 ,𝑘 ⃦ , E𝑓1 ,𝑓2 ‖𝑀𝑓1 ,𝑓2 ‖ = E𝑓1 ,𝑓2 ⃦ΠEPR (𝐼 ⊗ 𝑈 ) · √ ⃦ ⃦ 𝑁 2
𝑘
1 ∑︁ ⟨𝑣𝑖 |𝑥⟩ for 𝐷𝑓1 ,𝑓2 ,𝑘 := √ · 𝑅(𝑘, 𝑥) · |𝑖⟩⟨𝑖| , √ 𝑝𝑖 𝑁 𝑥,𝑖 √ and 𝑅(𝑘, 𝑥) := 𝑁 · (−1)𝑓1 (𝑘)+𝑓2 (𝑥) · ⟨𝑥|𝑈0 |𝑘⟩ . Conditioning on 𝑓2 , a matrix Rademacher series from 𝑓1 . For every fixed 𝑓2 , we can write 𝑀𝑅 := 𝑀𝑓1 ,𝑓2 as a matrix Rademacher series in terms of (−1)𝑓1 (𝑘) . Therefore, Theorem 3.11 implies E𝑓1 ,𝑓2 ‖𝑀𝑓1 ,𝑓2 ‖2 ≤ 𝑂(log 𝑀 ) · E𝑓2 Var𝑓1 (𝑀𝑓1 ,𝑓2 ) (︁
⃦ ⃦
⃦ ⃦
⃦ ⃦
⃦)︁ ⃦
≤ 𝑂(log 𝑀 ) · E𝑓2 ⃦E𝑓1 𝑀𝑓1 ,𝑓2 𝑀𝑓†1 ,𝑓2 ⃦ + E𝑓2 ⃦E𝑓1 𝑀𝑓†1 ,𝑓2 𝑀𝑓1 ,𝑓2 ⃦ . Note that for any 𝑥1 , 𝑥2 , 𝑓2 , if 𝑘1 ̸= 𝑘2 , E𝑓1 [𝑅(𝑘1 , 𝑥1 )𝑅(𝑘2 , 𝑥2 )] = 0, and thus ⃦ ⃦ ⃦ ⃦ ∑︁ ⃦ ⃒ ⃦ ⟨︀ ′ 1 ⃦ † † † ⃒ ′ ‖E𝑓1 𝑀𝑓1 ,𝑓2 𝑀𝑓1 ,𝑓2 ‖ = 2 ⃦E𝑓1 𝐷𝑓1 ,𝑓2 ,𝑘 𝑈 |𝑘⟩ 𝑘 𝑈 𝐷𝑓1 ,𝑓2 ,𝑘 ⃦ ⃦ 𝑁 ⃦ ⃦ 𝑘,𝑘′
61
⃦
⃦
⃦ ⃦ ⃦ ∑︁ † 1 1 ⃦ ⃦ ⃦ ⃦ ⃦ 𝐷𝑓1 ,𝑓2 ,𝑘 𝐷𝑓1 ,𝑓2 ,𝑘 ⃦ ≤ ≤ 2 ⃦E𝑓1 max 𝑛 ⃦E𝑓1 𝐷𝑓†1 ,𝑓2 ,𝑘 𝐷𝑓1 ,𝑓2 ,𝑘 ⃦ ⃦ ⃦ 𝑁 𝑁 𝑘∈{0,1} 𝑘 ⃦ ⃦ ⎞ ⎛ ⃦ ⃦ ∑︁ ⃦ ⃒ ⃦ ⟨︀ 1 ⃦ † † ′⃒ ⃦ ⎠ ⎝ ⊗ 𝐷 𝐷 (𝐼 ⊗ 𝑈 )Π E Π (𝐼 ⊗ 𝑈 ) |𝑘⟩ 𝑘 ‖E𝑓1 𝑀𝑓1 ,𝑓2 𝑀𝑓†1 ,𝑓2 ‖ = EPR ⃦ 𝑓1 ,𝑓2 ,𝑘 𝑓1 ,𝑓2 ,𝑘′ 𝑓1 EPR ⃦ 𝑁⃦ ⃦ ′ 𝑘,𝑘 ⃦ ⃦ ⃦ ⃦ ⃦ ∑︁ 1 ⃦ 1 ⃦ ⃦ ⃦ ⃦ ≤ |𝑘⟩⟨𝑘| ⊗ 𝐷𝑓1 ,𝑓2 ,𝑘 𝐷𝑓†1 ,𝑓2 ,𝑘 ⃦ = max 𝑛 ⃦E𝑓1 𝐷𝑓1 ,𝑓2 ,𝑘 𝐷𝑓†1 ,𝑓2 ,𝑘 ⃦ . ⃦E𝑓1 ⃦ ⃦ 𝑁 𝑁 𝑘∈{0,1} 𝑘
For diagonal matrix 𝐷𝑓1 ,𝑓2 ,𝑘 , 𝐷𝑓1 ,𝑓2 ,𝑘 𝐷𝑓†1 ,𝑓2 ,𝑘 is independent of 𝑓1 : 𝐷𝑓1 ,𝑓2 ,𝑘 𝐷𝑓†1 ,𝑓2 ,𝑘 = 𝐷𝑓†1 ,𝑓2 ,𝑘 𝐷𝑓1 ,𝑓2 ,𝑘 =
∑︁ ∑︁ ⟨𝑣𝑖 |𝑥⟩ ⟨𝑥′ |𝑣𝑖 ⟩
𝑝𝑖
𝑖 𝑥,𝑥′
′
|𝑖⟩⟨𝑖| · (−1)𝑓2 (𝑥)+𝑓2 (𝑥 ) · ⟨𝑥|𝑈0 |𝑘⟩ · ⟨𝑘| 𝑈0† |𝑥′ ⟩
⃒ ⃒2 ⃦ ⃒∑︁ ⃦ ⃒ ⟨𝑣 |𝑥⟩ · ⟨𝑥|𝑈 |𝑘⟩ 𝑖 0 ⃦ ⃒ ⃦ ⃒ † ⃦𝐷𝑓1 ,𝑓2 ,𝑘 𝐷𝑓1 ,𝑓2 ,𝑘 ⃦ = max ⃒ (−1)𝑓2 (𝑥) ⃒ . √ ⃒ ⃒ 𝑝𝑖 𝑖∈[𝑀 ]
(25)
𝑥
Another Rademacher series from 𝑓2 . From (25), inside max it can be viewed as a Rademacher series from 𝑓2 , and therefore Theorem 3.11 implies ⎞ ⎛ ⃒ [︃⃒ (︃ ]︃ )︃ ⃒∑︁ ⃒ 2 2 ⟨𝑣𝑖 |𝑥⟩ ⃒ 𝑡 𝑡 ⃒ 𝑓2 (𝑥) Pr ⃒ (−1) · ⟨𝑥|𝑈0 |𝑘⟩ · √ ⃒ > 𝑡 ≤ 2 · exp ⎝− ∑︀ |⟨𝑣 |𝑥⟩|2 |⟨𝑥|𝑈 |𝑘⟩|2 ⎠ ≤ 2 · exp − . 0 𝑖 𝑓2 ⃒ 𝑝𝑖 ⃒ 𝑁 · max𝑘,𝑥 |⟨𝑥|𝑈0 |𝑘⟩|2 𝑥 𝑥
𝑝𝑖
Now the right hand side is independent of 𝑘. By union bound over all 𝑖 ∈ [𝑀 ] and 𝑘 ∈ {0, 1}𝑛 , [︃
⃦ ⃦ 𝑡2 ⃦ ⃦ Pr ⃦E𝑓1 𝑀𝑓†1 ,𝑓2 𝑀𝑓1 ,𝑓2 ⃦ >
𝑁
𝑓2
[︃
⃦ ⃦ 𝑡2 ⃦ ⃦ Pr ⃦E𝑓1 𝑀𝑓1 ,𝑓2 𝑀𝑓†1 ,𝑓2 ⃦ > 𝑓2
Denote 𝑏 :=
√
]︃
]︃
𝑁
(︃
𝑡2 ≤ 2𝑀 𝑁 · exp − 𝑁 · max𝑘,𝑥 |⟨𝑥|𝑈0 |𝑘⟩|2 (︃
𝑡2 ≤ 2𝑀 𝑁 · exp − 𝑁 · max𝑘,𝑥 |⟨𝑥|𝑈0 |𝑘⟩|2
)︃
,
(26)
.
(27)
)︃
𝑁 · max𝑘,𝑥 |⟨𝑥|𝑈0 |𝑘⟩|. This will give (︃ 2
E𝑓1 ,𝑓2 ‖𝑀𝑓1 ,𝑓2 ‖ = 𝑂
𝑏2 · log 𝑀 · log 𝑀 𝑁 𝑁
)︃
and proves Theorem C.2. √ Specifically, for 𝑈0 = 𝐻, max𝑘,𝑥 |⟨𝑥|𝑈0 |𝑘⟩| = 1/ 𝑁 and thus 𝑏 = 1, and this proves Corollary C.3. Extending to game with classical advice. The tail bound in Theorem 3.11 also implies a classical-advice lower bound. For a fixed advice string, the spectral reduction from Lemma C.4 suggests that constant winning probability would require ‖𝑀𝑅 ‖2 = Ω(1). For fixed 𝑓2 , by setting 𝑡 = 𝑐 for some constant 𝑐 = Ω(1), Theorem 3.11 implies (︃
)︃
𝑐2 Pr[‖𝑀𝑅 ‖ ≥ 𝑐] ≤ 2𝑀 · exp − . 𝑓1 2 · Var𝑓1 (𝑀𝑅 ) 62
Therefore, for parameter 𝑐′ to be defined later, Pr [‖𝑀𝑅 ‖ ≥ 𝑐] ≤ Pr Var𝑓1 (𝑀𝑅 ) ≥ 𝑐′ + Pr Var𝑓1 (𝑀𝑅 ) < 𝑐′ ∧ ‖𝑀𝑅 ‖ ≥ 𝑐 [︀
𝑓1 ,𝑓2
]︀
𝑓2
[︀
]︀
𝑓1 ,𝑓2
(︃
𝑐2 ≤ Pr Var𝑓1 (𝑀𝑅 ) ≥ 𝑐 + 2𝑀 · exp − 𝑓2 2 · 𝑐′
)︃
′ ]︀
[︀
.
From the definition of Var(𝑀𝑅 ) and (26), (27), [︁⃦ ⃦
⃦ ⃦
⃦ ⃦
⃦ ⃦
[︂⃦ ⃦
⃦ ⃦
⃦ ⃦ 𝑐′ 𝑐′ ⃦ ⃦ + Pr ⃦E𝑓1 𝑀𝑓†1 ,𝑓2 𝑀𝑓1 ,𝑓2 ⃦ ≥ 𝑓2 2 2
Pr[Var𝑓1 (𝑀𝑅 ) ≥ 𝑐′ ] ≤ Pr ⃦E𝑓1 𝑀𝑓1 ,𝑓2 𝑀𝑓†1 ,𝑓2 ⃦ + ⃦E𝑓1 𝑀𝑓†1 ,𝑓2 𝑀𝑓1 ,𝑓2 ⃦ ≥ 𝑐′ 𝑓2
]︁
𝑓2
≤ Pr ⃦E𝑓1 𝑀𝑓1 ,𝑓2 𝑀𝑓†1 ,𝑓2 ⃦ ≥ 𝑓2
]︂
[︂
]︂
)︃
(︃
𝑐′ 𝑁 . ≤ 4𝑀 𝑁 · exp − 2𝑁 · max𝑘,𝑥 |⟨𝑥|𝑈0 |𝑘⟩|2 √ Therefore, by setting 𝑐′ = 1/ 𝑁 , we can bound the probability for 𝑐 = Ω(1) by the following: (︃
)︃
𝑐2 Pr [‖𝑀𝑅 ‖ ≥ 𝑐] ≤ Pr Var𝑓1 (𝑀𝑅 ) ≥ 𝑐 + 𝑀 · exp − 𝑓1 ,𝑓2 𝑓2 2 · 𝑐′ )︃ (︃ (︃ √ )︃ √ 𝑁 𝑐2 𝑁 + 2𝑀 · exp − ≤ 4𝑀 𝑁 · exp − 2 2𝑁 · max𝑘,𝑥 |⟨𝑥|𝑈0 |𝑘⟩|2 √ For 𝑏 := 𝑁 · max𝑘,𝑥 |⟨𝑥|𝑈0 |𝑘⟩| ≥ 1, a union bound over all 2𝑆 advice strings will yield a lower bound √ 𝑆 + log 𝑀 𝑁 = Ω( 𝑁 /𝑏2 ) [︀
′ ]︀
in order to achieve constant win probability.
63