# 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,518
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 ...
• 37.8k
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,645
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.9k
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 ...

### 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.9k
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,518
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,518

• 1,010
Accepted

### 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 ...
• 1,518

### QPIP minimal client quantum capabilities

According to this paper: https://arxiv.org/pdf/1509.09180.pdf The client only needs the ability to prepare random single-qubit pure states. You may also look at this paper for more information: ...

### Survey on Quantum error correction

Try these: Quantum Error Correction by Todd Brun Quantum Error Correction: An Introductory Guide by Joschka Roffe For surface codes, Dan Browne's lecture notes might help.
• 203
1 vote
Accepted

### Impact HHL caveat relaxation on quantum advantage

Your link 404's, but certainly HHL, like most quantum (and classical!) algorithms include a number of caveats for their applicability. The runtime of HHL depends on a number of factors in addition to ...
• 1,145
1 vote

### Can a collection of quantum circuits be calculated in superposition state?

In short, yes. The circuit $Q$ you describe is unitary: let $|\phi\rangle=\sum_x a_x|x\rangle$ and $|\psi\rangle=\sum_x b_x|x\rangle$ be normalized states, then \langle 0|\langle \psi|Q^*Q|\phi\...
• 1,010
1 vote

### What are some "must-read" papers for someone getting into Quantum Cryptography?

What constitutes "the most important papers" is highly subjective, so I will mention some of the papers that I think are influencial and that I have enjoyed reading. I would start with this ...
• 1,010
1 vote

### What are some "must-read" papers for someone getting into Quantum Cryptography?

" I've also done a graduate-level course in (classical) cryptography. I'm interested in Quantum Cryptography and would like to know what people would consider the most important papers for me to ...
• 541
1 vote

### Complement for joint POVMs?

I've come to the conclusion that the definition of the complement as I've written doesn't make sense for POVMs. It assumes that the product of two elements is a simultaneous event which is false. ...
1 vote

### Oracle Construction for Grover's Algorithm

You can also get a solution which uses only one ancillary qubit (but relies on NOT gates with multiple controls), by getting your input to algebraic normal form (e.g. with Mathematicas ...
1 vote
Accepted

### Addition on a quantum computer

The algorithm from that paper runs inline with no extra ancilla bits. If the input number and the affected number use up $t$ bits altogether, then it runs in $t$ bits. 3n qubits are required to add ...
• 1,518
1 vote
Accepted

### Quantum GCD circuit: On reversibility and clearing ancillae

It looks like they just directly translated the algorithm into a circuit, so it's not too hard to reproduce. Write out the binary gcd algorithm as a loop: ...
• 1,518
1 vote

### Universities for Quantum Computing / Information?

MIT has three graduate classes in the field I know about. Two of them, 8.370 ( Quantum Computation) and 8.371 (Quantum Information Science ll) form a series and are theoretical classes. The other one, ...
• 11

Only top scored, non community-wiki answers of a minimum length are eligible