5

This is a purely hypothetical answer - I don't know if anybody has ever studied it, and have not attempted to find out - but think about public key cryptography. Current public key systems are based on the idea that some problems in the complexity class NP are probably hard to solve directly, but there exists a "proof" that lets you verify the solution ...


5

Alice receives a quantum state $|\psi\rangle$, which is an element of some basis $\mathcal{B}$, though she does not know what $\mathcal B$ is. She then teleports this to Bob, who is told by someone else what $\mathcal B$ is. Furthermore, it seems that specifically either $\mathcal{B} = \{ \lvert 0 \rangle, \lvert 1 \rangle \}$ or $\mathcal{B} = \{ \lvert + \...


5

In principle it is possible to generate code for oracles such as the DES encryption (under fixed plaintext/ciphertext pairs, so that the search space becomes the set of all possible encryption keys). One (simple) way to do so is to apply the Bennett method to a classical, irreversible circuit and then to count the gates manually. There are better ways known ...


4

I think your answer is right, the original article Searching a Quantum Phone Book said that Grover's algorithm would solve the problem after quantum-DES enciphering the known clear text a mere 185 million times. Although it is different from the results you calculated, but it looks much better than 185.


3

There is one main key point in the description of your question: Is $s$ meant to be a classical secret or a quantum secret? If $s$ is meant to be a classical secret, then the answer is yes, but there is not really much quantum in the positive answer. If $s_A$, $s_B$, and $s_C$ are all $d$-state digits, then there is a simple construction that works in ...


2

Aaronson and Christiano proved the security of their scheme in an oracle model, where they assume the verifier has access to a membership oracle to some subspace $A$. In order to turn this into actual quantum money, it is "sufficient" to implement "such an oracle". How would one do that? And what is "such an oracle"? Well, the simplest question is to ...


2

Absolutely! BB84 can be implemented over LiFi. There are however certain constraints and inefficiencies involved, which will have to be taken into account for implementation - possibly leading to the usage of BB84 variants like Decoy State, with higher efficiencies than pure BB84. A four non-orthogonal polarization basis encoded single photon would be very ...


2

Yes, it does exist. Here's something that you could do (I'm sure there are better things): Consider the symmetric state $$ |\psi\rangle=\frac{1}{\sqrt{\binom{5}{2}}}\sum_{x\in\{0,1\}^5:\ x\cdot x=2}|x\rangle. $$ The benefit of selecting the symmetric state is that it is entirely irrelevant which pair of qubit is assigned to Alice, and which pair is assigned ...


2

I think there are two meanings of "reversible" at work. These may be causing confusion. Initially, even in the classical world, when we say that a function $f(x)$ is irreversible without any other qualifications, we mean that, given $y$, it is computationally difficult to find an $x$ such that $y=f(x)$ In other contexts, when talking about quantum circuits,...


1

These are two separate questions, so I will (try to) answer them separately as well. Concerning the (reduction of) privacy in remote or cloud computing. Without any alterations, the instructions for a quantum computation that is to be run on a remote computer can be seen by that remote computer. That is to say, if you want to conceal the computations that ...


1

If you implement an oracle for Grover's algorithm that sometimes gives unhelpful answers, you can, as you suggest, rerun and remeasure. In your example, there are only two incorrect answers $x=0$ and $x=m$. With the way you defined $f(x)$, these would indeed be negated and diffused. Because there are only two bad answers, the impact may be small. However ...


1

In this survey article they discuss Grover's algorithm. In my opinion, the most important part: Grover’s speed-up from $N$ to $\sqrt{N}$ is not as devastating as Shor’s speed-up. Furthermore, each of Grover’s $\sqrt{N}$ quantum evaluations must wait for the previous evaluation to finish. To quantify this issue, define T as the number of serial ...


1

I think there's some confusion here, so I'll try to explain the principle of QKD (Quantum Key Distribution) instead. Say Alice and Bob want to communicate in a secure fashion using symmetric encryption. To do so, they require a shared secret, a key. One of them generates it and he must somehow get it to the other person without an eavesdropper, say Eve, ...


1

I think that there are many interesting answers to your question, but I would like to point out what I personally find the most mesmerizing consequence of quantum theory to cryptography. One of the most fascinating quantum phenomena that has no classical counterpart is no cloning. This essentially means that if you don't have enough information about some ...


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