In this thesis, we give new protocols that offer a quantum advantage for problems in ML, Physics, and Finance.
Quantum mechanics gives predictions that are inconsistent with local realism.
The experiment proving this fact (Bell, 1964) gives a quantum protocol that is impossible to replicate using classical resources.
Such a situation, where quantum techniques outperform classical methods, is known as a quantum advantage.

Firstly, we consider the problem of adversarial robustness from ML.
Modern machine learning models have been shown to be vulnerable to small, adversarially chosen perturbations of the input.
In the standard setting, one allows perturbations that are small in the $\ell_p$ norm.
We introduce two new models and give a defense against adversarial examples in each of them.
In the first, fully classical model, we consider an adversary which is not limited by the type of perturbations he can apply but when presented with a classifier can repetitively generate random adversarial examples.
We design a protocol in which interaction with such an adversary leads to a provable defense.
Our second model is influenced by the quantum PAC-learning setting introduced in Bshouty and Jackson, 1995.
We assume that the adversary is quantum, computationally bounded but unrestricted in other aspects.
In this model, we give an interactive protocol between the learner and the adversary that guarantees robustness.
Moreover, we show that it offers a quantum advantage as it beats a classical lower bound from Goldwasser et al., 2020.

Secondly, we consider the problem of Entanglement vs Nonlocality from Physics.
Axioms of quantum theory lead to a natural division of states into entangled and separable.
This dichotomy relies purely on a mathematical formalism.
The question of Entanglement = Nonlocality asks if it is true that for every entangled state $\rho_{AB}$ there exists an experiment between Alice and Bob and a verifier that distinguishes between two cases: (i) Alice and Bob share $\rho_{AB}$ versus (ii) Alice and Bob share only a separable state.
It was shown (Barrett, 2002) that in the standard Bell scenario the answer is no.
We introduce a new model in which the parties are computationally bounded.
In this model, we show that if the Learning with Errors problem is quantumly hard then Entanglement = Nonlocality.
We also show a complementary result, i.e. we prove that Entanglement = Nonlocality implies $\mathtt{BQP} \neq \mathtt{\PP}$.
These two results connect this foundational problem in quantum mechanics to computational complexity.
As an implication of this connection, we show the impossibility of some protocols for the delegation of quantum computation.

Thirdly, we consider the problem of arbitrage from Finance.
We consider a situation where two parties trade securities in distant locations.
We give a quantum protocol that improves the risk-return tradeoff compared to what is possible for classical strategies.
The protocol is based on the experiment from Bell, 1964 and requires only two entangled qubits.
Due to its simplicity, this scheme might be realizable in practice in the near future.