 a quantum advice with a maximally mixed state), we obtain the following.
Theorem 4.4. Given a decision security game. Assume that 0 = 1/ (, ) is a nonnegligible lower bound on the advantage for an adversary with 0 queries and 0 qubits of advice, and assume that multi-instance game ⊗ is (, )-secure in the QROM. For any (, ) adversaries in QAI-QROM, the best advantage against is ′, which satisfies wherẽabsorbs (log, log, log ) factors.

One-Way Function
In this section, we show the security of OWF in the AI-QROM and QAI-QROM. Let us start with reformalizing the security of OWF in QROM in our language of security games.
To fill in the rest of the details from Definition 3.3, the security game defined here is that given a random oracle, the challenger samples a uniformly random element ∈ [ ] and computes = ( ) as the challenge. The adversary is allowed to make oracle queries to and it wins if and only if it finds any pre-image of. This is exactly the security of OWF in QROM. This is also exactly the problem of inverting a random image.
In the rest of the section, we are going to prove the following lemma.
Combining this lemma with Theorem 4.1 (or Theorem 4.3), we can show the security of in the AI-QROM (or QAI-QROM, respectively).
Proof. In Theorem 4.1, 0 is at least 1/ because there is at least one pre-image of, so random guess has winning probability at least 1/. Plugging in 0 ≥ 1/, and ⊗ is (︁ )︂ -secure in the QAI-QROM, wherẽabsorbs (log, log, log ) factors.
Proof. It is a publicly-verifiable game. For, we can verify that = 2 and 0 is again In the following two subsections, we will first show multi-instance security for a slightly different game with (, ) = ( + 2 ). Then in the second subsection, we show that these two games are almost indistinguishable even for a quantum adversary, and conclude that the multi-instance security for ⊗ is (, ) = (︁

Multi-Instance Security for Inverting Random Image
Consider the following OWF game variant, where the main difference is that instead of uniformly sampling ∈ [ ] and telling the adversary ( ), we are directly sampling a uniformly random ∈ [ ] and telling the adversary. In other words, given a random oracle, the challenger samples a random output as the challenge. The adversary is allowed to make oracle queries to and it wins if and only if it finds a pre-image of.
In OWF problem, a challenge may not have a valid answer. For example, when ≪, a random element in [ ] is not the image of any inputs with high probability. is the auxiliary register whose size is unbounded.
• | ⟩ serves as the challenge as input to,1.
•, +1 prepares the final output for -th game in register | ⟩, clears the register | ⟩, and receives the measured answer also back in the register | ⟩ and the next challenge in the register | ⟩.
Proposition 5.7. For all ∈ [ ], let 1, 2,..., −1 be the random variable of the first ( − 1) challenges and 1,..., be the random variable for the decision bits. For any (, ) algorithm in the QROM, 1, 2,..., −1 and 1, 2,...,, we have, Proof. We start by observing that these conditioning correspond to the pure state | ′,0 ⟩ that we have described above. The state is well defined as these classical outcomes occur with non-zero probability as we have assumed. Since the total number of queries up to this point is at most ( − 1)( + 2), by Lemma 2.6, there exists some complex numbers * such that Let ( ) be the probability that after queries to, measuring the database register gives a database containing, or formally, Since | ′,0 ⟩ only has non-zero amplitude over with size at most ( − 1)( + 2), for each, pair, |, | 2 contributes to at most ( −1)( +2) different's. We observe that the same conclusion also holds for |,0 ⟩, as the only difference between these two states is that is initialized to some element in [ ], and register is unchanged. In other words, We then have the following lemma that bounds ( ) for all > 0, which is the same as [Zha19, Theorem 1] and similar to [LZ19a, Lemma 8 and Lemma 9].
We can equivalently write the second term as The inequality (*) comes from the fact that ∪ (, ) already contains, therefore will either remove the entry for or not change the database at all.
Using an induction on the lemma, we have Definẽas the probability that = 1 conditioned on the challenge is. In other words,ĩ s the probability that the final state, when measured gives = ( ) =. By Lemma 2.7, we have √︀̃≤ √︁ ( +1) + 1/ √. Combining this with (2), (3), and Cauchy-Schwarz inequality, We complete the proof by observing that the left hand side is exactly the probability in the statement.
Combine Proposition 5.7 and Lemma 3.14, we have proven the lemma.

Multi-Instance Indistinguishability of Sampling Image
The analysis for multi-instance security of ⊗ is not enough for ⊗. This is because in the standard one-way function game, is sampled in the way that it is correlated with the random oracle. Therefore, we can not use Lemma 2.7, since the challenge image is almost always in the database. In this subsection, we will instead show that the advantage of indistinguishing whether is sampled uniformly at random or from ( ) for a uniformly random is at most (( + 2 )/ ).
First, we need the following lemma, which says for any quantum algorithm making at most queries to a random oracle before getting a challenge, and at most ′ queries after, it can not distinguish if it gets a random image ( ) or a random element in the range. Furthermore, the statement is true even after conditioning on arbitrary intermediate measurements.
Lemma 5.9. Let be a quantum algorithm that makes at most + ′ queries to a random oracle.
Let [ ] = 1, 2,..., be the random variable of the outcomes of arbitrary intermediate measurements, all of which occur before the -th query. After making queries, it is given a challenge, which we crudely denote as ( ). It then makes another ′ queries and simply outputs a bit. For any list of outcomes [ ] = 1,...,, Proof. We will first present two slightly different oracles or experiments, and argue that each of them perfectly simulates ( ) and ( ( )) respectively.
Case 1. The challenge is a uniformly random. We implement the following changes to the oracle: 1. We replace the random oracle with a phase oracle. By Lemma 2.2, this change perfectly preserves the probability that outputs 1 as he only interacts with | ⟩ using the phase oracle.
3. We additionally prepare a random ∈ [ ] at a new register but we do not use it. This change is clearly only conceptual.
Conditioned on [ ] =, after has made queries to the phase oracle and before generating the challenge, by Lemma 2.3, we know that the overall state of and the oracle internal state can be written as 7 Here we write | ⟩ for simplicity, but to see correctness, you could really think of |, ⟩ so we have two computational-basis "copies" of the same uniform superposition 1/ √ ∑︀ | ⟩. As we will never touch the second copy, the first copy behaves exactly like a classical random string to the rest of the algorithm.
where and ′ have not been used and thus is completely un-entangled with. After generating the challenge, the overall state becomes Case 2. The challenge is the image for a uniformly random pre-image. We implement the following changes to the oracle: 1. We again replace the random oracle with a phase oracle using Lemma 2.2.
2. We again augment to bẽ: [ + 1] ↦ → [ ] for a new random element ′ ∈ [ ], and prepare a new random ∈ [ ]. For now, this is only a conceptual change (we only added two new independent registers).

Define a new classical oracle
Instead of giving phase oracle to, we are giving phase oracle to ′, where is pulled from the new register | ⟩ that we just add. For any fixed, this change is perfectly consistent with the original oracle distribution; and as | ⟩ is just a classical random string, the overall change is also perfectly consistent.
4. Instead of sampling a new pre-image for generating the challenge, we instead use as the pre-image, that is, we "compute" ′ ( ) = ′ and send ′ as the challenge for. It is easy to see that cannot obtain any information on for the first queries, thus this change still perfectly preserves's functionality.
Therefore, conditioned on [ ] =, before giving the challenge, the overall state of and the