Factoring semi-primes with (quantum) SAT-solvers.

The computational difficulty of factoring large integers forms the basis of security for RSA public-key cryptography. The best-known factoring algorithms for classical computers run in sub-exponential time. The integer factorization problem can be reduced to the Boolean Satisfiability problem (SAT). While this reduction has proved to be useful for studying SAT solvers, large integers have not been factored via such a reduction. Shor's quantum factoring algorithm factors integers in expected polynomial time. Large-scale fault-tolerant quantum computers capable of implementing Shor's algorithm are not yet available, preventing relevant benchmarking experiments. Recently, several authors have attempted quantum factorizations via reductions to SAT or similar NP-hard problems. While this approach may shed light on algorithmic approaches for quantum solutions to NP-hard problems, in this paper we study and question its practicality. We find no evidence that this is a viable path toward factoring large numbers, even for scalable fault-tolerant quantum computers, as well as for various quantum annealing or other special purpose quantum hardware.

On speeding up factoring with quantum SAT solvers.

There have been several efforts to apply quantum SAT solving methods to factor large integers. While these methods may provide insight into quantum SAT solving, to date they have not led to a convincing path to integer factorization that is competitive with the best known classical method, the Number Field Sieve. Many of the techniques tried involved directly encoding multiplication to SAT or an equivalent NP-hard problem and looking for satisfying assignments of the variables representing the prime factors. The main challenge in these cases is that, to compete with the Number Field Sieve, the quantum SAT solver would need to be superpolynomially faster than classical SAT solvers. In this paper the use of SAT solvers is restricted to a smaller task related to factoring: finding smooth numbers, which is an essential step of the Number Field Sieve. We present a SAT circuit that can be given to quantum SAT solvers such as annealers in order to perform this step of factoring. If quantum SAT solvers achieve any asymptotic speedup over classical brute-force search for smooth numbers, then our factoring algorithm is faster than the classical NFS.

Novel Technique for Robust Optimal Algorithmic Cooling.

Heat-bath algorithmic cooling provides algorithmic ways to improve the purity of quantum states. These techniques are complex iterative processes that change from each iteration to the next and this poses a significant challenge to implementing these algorithms. Here, we introduce a new technique that on a fundamental level, shows that it is possible to do algorithmic cooling and even reach the cooling limit without any knowledge of the state and using only a single fixed operation, and on a practical level, presents a more feasible and robust alternative for implementing heat-bath algorithmic cooling. We also show that our new technique converges to the asymptotic state of heat-bath algorithmic cooling and that the cooling algorithm can be efficiently implemented; however, the saturation could require exponentially many iterations and remains impractical. This brings heat-bath algorithmic cooling to the realm of feasibility and makes it a viable option for realistic application in quantum technologies.

Differences in work injury risk between immigrants and natives: changes since the economic recession in Italy.

BACKGROUND: It is known that occupational injury rates are higher for immigrant than for native workers, however the effects of the economic cycles on these differences has not been assessed to date. The aim of the paper is to test if the crisis has the same mechanism of selection in the two groups by comparing injury rates in 2005 (before the crisis) and in 2010 (after the crisis). METHODS: The Work History Italian Panel-Salute integrated database was interrogated to identify employment contracts in the metalworking and construction industries for the years 2005 and 2010 and the occupational injuries. A definition based on the type of injury, less likely to be biased by underreporting, was used to select serious events. Immigrants and natives were matched using the propensity score method and injury rates were calculated in the two years. Analyses were stratified by industry. RESULTS: In the metalworking industry injury rates slightly increased over time for both groups, and were higher among immigrant than native workers in both 2005 and 2010. In the construction industry the 2005 injury rate was the same in the two groups, and there was a negative trend over time in both groups. However the decline in the 2010 injury rate for Italian workers was much larger, which led to a considerable increase of the incidence rate ratio of immigrants with respect to native (IRR 3.83, 95% CI 2.52-5.75). CONCLUSIONS: The economic recession had an impact on the risk of workplace injury. Though the main observed factors (18 variables) usually reported in literature to explain the higher injury rates of the immigrant workers were controlled through the matching, there were still differences between immigrants and natives. The main reason is that immigrants continue to be assigned to the more dangerous jobs and the more dangerous tasks within these job. Furthermore, also differences in the perception of workplace injury risks, linguistic barriers, and cultural factors may have a role in explaining this gap.

Asymptotic bound for heat-bath algorithmic cooling.

The purity of quantum states is a key requirement for many quantum applications. Improving the purity is limited by fundamental laws of thermodynamics. Here, we are probing the fundamental limits for a natural approach to this problem, namely, heat-bath algorithmic cooling (HBAC). The existence of the cooling limit for HBAC techniques was proved by Schulman, Mor, and Weinstein. A bound for this value was found by Elias et al. and numerical testing supported the hypothesis that their bound may be the actual limit. A proof or disproof of whether their bound was the actual limit remained open for the past decade. Here, for the first time, we prove this limit. In the context of quantum thermodynamics, this corresponds to the maximum extractable work from the quantum system. We also establish, in the case of higher dimensional reset systems, how the performance of HBAC depends on the energy spectrum of the reset system.

Finding shortest lattice vectors faster using quantum search.

By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time 2 1.799 n + o ( n ) , improving upon the classical time complexities of 2 2.465 n + o ( n ) of Pujol and Stehlé and the 2 2 n + o ( n ) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 2 0.268 n + o ( n ) , improving upon the classical time complexity of 2 0.298 n + o ( n ) of Laarhoven and De Weger. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem.

Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits.

Decomposing unitaries into a sequence of elementary operations is at the core of quantum computing. Information theoretic arguments show that approximating a random unitary with precision ε requires Ω(log(1/ε)) gates. Prior to our work, the state of the art in approximating a single qubit unitary included the Solovay-Kitaev algorithm that requires O(log(3+δ)(1/ε)) gates and does not use ancillae and the phase kickback approach that requires O(log(2)(1/ε)loglog(1/ε)) gates but uses O(log(2)(1/ε)) ancillae. Both algorithms feature upper bounds that are far from the information theoretic lower bound. In this Letter, we report an algorithm that saturates the lower bound, and as such it guarantees asymptotic optimality. In particular, we present an algorithm for building a circuit that approximates single qubit unitaries with precision ε using O(log(1/ε)) Clifford and T gates and employing up to two ancillary qubits. We connect the unitary approximation problem to the problem of constructing solutions corresponding to Lagrange's four-square theorem, and thereby develop an algorithm for computing an approximating circuit using an average of O(log(2)(1/ε)loglog(1/ε)) operations with integers.

Interacting boson problems can be QMA hard.

Computing the ground-state energy of interacting electron problems has recently been shown to be hard for quantum Merlin Arthur (QMA), a quantum analogue of the complexity class NP. Fermionic problems are usually hard, a phenomenon widely attributed to the so-called sign problem. The corresponding bosonic problems are, according to conventional wisdom, tractable. Here, we demonstrate that the complexity of interacting boson problems is also QMA hard. Moreover, the bosonic version of N-representability problem is QMA complete. Consequently, these problems are unlikely to have efficient quantum algorithms.

Simulating quantum systems using real Hilbert spaces.

We develop a means of simulating the evolution and measurement of a multipartite quantum state under discrete or continuous evolution using another quantum system with states and operators lying in a real Hilbert space. This extends previous results which were unable to simulate local evolution and measurements with local operators and was limited to discrete evolution. We also detail applications to Bell inequalities and self-testing of the quantum apparatus.

Optimal quantum circuits for general phase estimation.

We address the problem of estimating the phase phi given N copies of the phase-rotation gate uphi. We consider, for the first time, the optimization of the general case where the circuit consists of an arbitrary input state, followed by any arrangement of the N phase rotations interspersed with arbitrary quantum operations, and ending with a general measurement. Using the polynomial method, we show that, in all cases where the measure of quality of the estimate phi for phi depends only on the difference phi-phi, the optimal scheme has a very simple fixed form. This implies that an optimal general phase estimation procedure can be found by just optimizing the amplitudes of the initial state.

Single spin measurement using cellular automata techniques.

We analyze a conceptual approach to single-spin measurement. The method uses techniques from the theory of quantum cellular automata to correlate a large number of ancillary spins to the one to be measured. It has the distinct advantage of being efficient: under ideal conditions, it requires the application of only O((3)square root N)) steps (each requiring a constant number of rf pulses) to create a system of N correlated spins. Numerical simulations suggest that it is also, to a certain extent, robust against pulse errors, and imperfect initial polarization of the ancilla spin system.

Approximate quantum cloning with nuclear magnetic resonance.

Here we describe a nuclear magnetic resonance (NMR) experiment that uses a three qubit NMR device to implement the one-to-two approximate quantum cloning network of Buzek et al. [Phys. Rev. A 56, 3446 (1997)]. As expected the experimental results indicate that the network clones all input states with similar fidelities, but as a result of decoherence and incoherent evolution arising from B(1) inhomogeneity the total fidelity achieved does not exceed the measurement bound.