Skip to main content
Share Your Experience: Take the 2024 Developer Survey
30 votes
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: ...
Craig Gidney's user avatar
  • 1,518
20 votes
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 ...
Joshua Grochow's user avatar
9 votes
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 ...
Or Meir's user avatar
  • 5,615
8 votes
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 ...
Frédéric Grosshans's user avatar
8 votes
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-...
Adam Bouland's user avatar
8 votes
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 ...
Peter Shor 's user avatar
7 votes
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 ...
Adam Smith's user avatar
7 votes

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 ...
Joe Fitzsimons's user avatar
6 votes
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 ...
Craig Gidney's user avatar
  • 1,518
6 votes

How can I get $\sum_n e^{i a_n} |n\rangle$ from $\sum_n a_n |n\rangle$?

It's not unitary, so it's impossible because all quantum transformations have to be unitary. Consider the states $$ \frac{3}{5} |0\rangle + \frac{4}{5} |1\rangle \quad \mathrm{and} \quad \frac{3}{5} |...
Peter Shor 's user avatar
6 votes

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, ...
Peter Shor 's user avatar
6 votes
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 ...
Craig Gidney's user avatar
  • 1,518
5 votes
Accepted

When is a non-unitary quantum system only theoretical?

I complete here Peter’s answer with a characterization of physical maps as CPTP maps. As you know, if the system is isolated, the only operations you can implement are the unitary operations. But, ...
Frédéric Grosshans's user avatar
5 votes
Accepted

Is it possible to MAC a quantum state with a classical key under reasonable assumption?

Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith, Alain Tapp. "Authentication of Quantum Messages", FOCS 2002. http://www.cse.psu.edu/~ads22/pubs/PS-CSAIL/BCGST02-focs-final.pdf As with ...
Adam Smith's user avatar
5 votes

Is it proved that error rate of quantum computation is bounded by constant rather than a function dependent on time and environment by quantum theory

As far as I know, nobody has come up with a convincing physics reason that fault-tolerant quantum computing is fundamentally impossible. However, it is a formidable engineering task, which is why we ...
Peter Shor 's user avatar
4 votes

Is there any connection between the diamond norm and the distance of the associated states?

Following up on the line of thinking presented by Alex Monras, there is actually a quite generic argument for this kind of bound that goes beyond diamond norm and applies to many other channel ...
Mark M. Wilde's user avatar
4 votes
Accepted

From CHSH inequality to CHSH game

I think your history is entirely right. Computer scientists are used to thinking about protocols as games, while physicists are not, and this is probably why these results weren't formulated as games ...
Peter Shor 's user avatar
4 votes
Accepted

Noisy channel coding theorem in quantum information

You have two questions here. Why can't Shannon's Noisy Coding Theorem be used for a quantum channel? What gaps are there to proving a quantum noisy channel coding theorem? I will concentrate on the ...
Peter Shor 's user avatar
3 votes
Accepted

Quantum circuit simulation divergence in results

Peter Shor nailed the reason. This is because OpenQASM and Quirk have different conventions for how the order of wires maps into the order of bits shown in the kets. The simplest way to check this is ...
Craig Gidney's user avatar
  • 1,518
3 votes
Accepted

Is there any hidden subgroup of a symmetric group which can be efficiently determined?

From what I understand, it is partially because we don't have any techniques currently that take advantage of structure of the hidden subgroup itself. Weak Fourier sampling solves the problem whenever ...
Joshua Grochow's user avatar
2 votes

Is there any connection between the diamond norm and the distance of the associated states?

If it should prove useful, this is a derivation of the inequality $$ \frac{1}{n} \| \Phi_0 - \Phi_1 \|_{\Diamond} \leq \| J(\Phi_0) - J(\Phi_1) \|_1 $$ in John Watrous' answer. We will make use of ...
helloworld's user avatar
2 votes
Accepted

How are new probabilities computed when simulating measurement on a set of qubits?

Let $$P(0) = |a|^2 + |c|^2 + |e|^3 + |g|^2.$$ This is the probability of observing $0$. Then \begin{eqnarray*} w &=& a \big/ \sqrt{P(0)}, \\ x &=& c \big/ \sqrt{P(0)}, \\ y &=&...
Peter Shor 's user avatar
2 votes

What are the general classes of measured systems

I don't think there will be any result of the form you want. There's no single "most general system" that has this property. (Instead, it'd be better to choose some specific pair of classes of ...
D.W.'s user avatar
  • 12.1k
2 votes
Accepted

Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?

I think your focus on the rigid case of GI limits you too much. Instead phrase (non-rigid) GI as an HSP in the same way, but now the goal is to determine the size of the hidden subgroup, or a ...
Joshua Grochow's user avatar
2 votes

How can I get $\sum_n e^{i a_n} |n\rangle$ from $\sum_n a_n |n\rangle$?

I wouldn't think so. I'm assuming your $a_n$'s are normalized, i.e. that $||\sum_n a_n |n\rangle|| =1$. But then your wish output is not normalized since $$||\sum_n e^{ia_n} |n\rangle|| = \sqrt{\sum_n ...
lamontap's user avatar
  • 990
2 votes
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 ...
Craig Gidney's user avatar
  • 1,518
2 votes

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: ...
Bassem Khoury's user avatar
2 votes

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.
raycosine's user avatar
  • 203
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. ...
Stephen Diadamo's user avatar
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 ...
Daniel Hauck's user avatar

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