Hardwiring the output in quantum black box separation

In this paper, while using a diagonalization argument in Section $ 5$ , the authors write:

Fix some enumeration over all $ poly(n)$ -size quantum verifiers $ M_{1}, M_{2},…$ which we can do because the number of such machines is countably infinite (by the Solovay-Kitaev theorem [15]). Some of these verifiers may try to decide a language by trivially “hardwiring” its outputs; for example, by returning 1 independent of the input. We start by fixing a unary language $ L$ such that no machine $ M_{i}$ hardwires the language. We can always do this because there are more languages than $ poly(n)$ -sized machines.

Maybe I am missing something very basic, but:

  1. Why do we care if some of the verifiers have the output hardwired?
  2. How can we find an $ L$ , like in the description? Why will this $ L$ even be decidable? I know there are more languages than there are Turing machines; but those extra languages aren’t decidable.

Quantum Cryptography Algorithms Implementations

The Post Quantum Cryptography is a type of cryptography that lies on physics properties instead of mathematics , it has many algorithms and implementations like NTRU , McEliece , SIDH … etc

But there is a difference between Post Quantum Cryptography and Quantum Cryptography , i’d like to know some algorithms of that and also if they have implementations for example on Github or any thing like that

Thank you

What is the origin of the term ‘quantum ogre’?

As I understand it, a ‘quantum ogre’ is a piece of game content that the party will be unable to avoid encountering. It’s a way of saving on prep time for the game master but that subtly removes player agency.

For example: when the party comes to a fork in the road, will they go left or right? This provides the players with the illusion that there is a meaningful choice to be made. However, the reality is that, whichever direction the party chooses the game master will decide that the ogre is (and has effectively always been) lying in wait on that path.

How long has the term ‘quantum ogre’ been in use and from where did it originate?

Data structures for quantum computers

In classical computers we have List,Queue,Tree etc data structures, since classical computers using 1’s & 0’s on those data structures. Then what happens when it comes to quantum computers, Do they(scientists) need to create new data structures ? Or use existing data structures with some sort of optimization ? Thanks in advance.

Can quantum computers really compute a vast number of possible solutions simultaneously?

This link says

They are not constrained to stepwise calculations but, rather, can compute a vast number of possible solutions simultaneously—and at a speed that is far beyond anything we can imagine.

Is this really true? AFAIU quantum computers cannot compute a vast number of possible solutions simultaneously. A quantum computer is not a parallel computer. It is true that the wave function will exist in a superposition of states before measurement, but when we make a measurement it will collapse to a definite state. And measurements is all we can do.

From scott aaronson’s blog (https://www.scottaaronson.com/blog/)

If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.

curious to know what experts think

Quantum Computing: understanding the state vector

I have just started to learn QC. It is said that

The quantum state of N qubits can be expressed as a vector in a space of dimension 2^N

If there is 1 qubit then we have two possible state vectors |0> and |1> or (0,1) and (1,0) respectively. Getting to 2 qubits we have 4 possible state vectors (1,0,0,0), (0,1,0,0), (0,0,1,0) and (0,0,0,1). Note that in each case, all entries are zero except 1. The point I am trying to get to is that:

  1. 2^N seems like a big space but given a vector in this space – all components will be zero except 1. So there are only 2^N possible values the state vector can take. Is this not correct? If not, why?

    1. Why don’t we say the space is N dimensional. A N-bit string has 2^N possible values.

NDFA has maximum states as 2^n the same for qubits in quantum computation.How they can be distinguished in means of computation? [duplicate]

This question already has an answer here:

  • What is the difference between quantum TM and nondetermistic TM? 2 answers

I am a Computer Engineer. I studied basics of Quantum Computation. In dealing with multiple states, I feel NDFA does similar to Quantum Computation but we preferred to convert NDFA to DFA and solved problems. But in era of Quantum we prefer this multiple state quantum property to deal with major NP problems. Why? Where they both looks similar and where they differ in terms of Computation