# Tag Info

Accepted

### Oracle Construction for Grover's Algorithm

The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to. For example, suppose you have a 3-sat problem: ...
• 1,498
Accepted

### Entropy and computational complexity

Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there ...
• 36.9k

### Generating "infinite" randomness from a constant number of sources

This is a great question, Suresh! Our randomness expansion result does not imply any complexity theoretic result. Here's one way to understand the result: we believe that quantum mechanics governs ...
• 3,748
Accepted

### Where can I find examples of error correcting codes of the following types?

If you just need any code $E : \{0,1\}^n \to \{0,1\}^m$ where $m=O(n)$ and where the distance is linear in $m$, then what you are looking for is called an "asymptotically good code". There are many ...
• 5,350
Accepted

### theorems for universal set of quantum gates for SU(d)

I'm not aware of any proof that the Clifford group + any non-Clifford element gives a universal set of quantum gates. The closest related result that I know is that the Clifford group + any non-...
• 743
Accepted

### Quantum Money where not even the Bank can counterfeit

There are proposals for quantum money where it appears that not even the bank can produce two copies of a quantum money state with the same serial number. See Farhi et al's paper Quantum Money from ...
• 24.3k
Accepted

### Is it possible to encrypt quantum states under reasonable assumptions?

One can encrypt an n-qubit state using a 2n-bit classical secret key. The idea is to use the key to select a random Pauli operator, and apply that operator to the secret as an encryption. (The inverse ...
• 878

### States and Probability distributions that the 5-qubits IBM computer can produce

I just ran the first state you suggest (i.e. the GHZ state with negative phase in the Hadamard basis). Basically what I did was to write a circuit which creates that state, apply one of 5 stabilizer ...
• 13.6k
Accepted

### Fast classical simulation of quantum algorithms

Your question was inspired by the recent quantum-inspired classical advance in recommendation algorithm. Note that it is not the firs time such a thing happens. In 2015, similar developments happened ...
Accepted

### Why is it impossible to work with polylog length encoding schemes for quantum circuits?

Clearly you can work with abstract compressed representations of circuits. You can reason about them and manipulate them and turn them into concrete lists of gates. We do it all the time. But in ...
• 1,498

### When is a non-unitary quantum system only theoretical?

Look at John Preskill's Lecture Notes; particularly Section 3.2. As you noted, you can do a NAND gate by using a Toffoli gate and throwing away some of the output qubits. This results in decoherence, ...
• 24.3k
Accepted

### Simulating quantum measurements by unitaries

The basic idea here is that any operation that uses measurement can be replaced by an operation that instead CNOTs qubits onto ancillae. Any circuit with an intermediate measurement can be converted ...
• 1,498

• 960
### Computing 'Robustness of Magic' of $n$-bit W states
Here is a proof that $R(W_n) \in \Omega(\sqrt[4]{n})$. Given a $W_n$ state, it is possible to create $\lg n$ T states with Clifford operations and a single additional T gate. Basically: Xor together ...