Search

Quantum search algorithms offer a remarkable advantage of quadratic reduction in query complexity using quantum superposition principle. However, how an actual architecture may access and handle the database in a quantum superposed state has been largely unexplored so far; the quantum state of data was simply assumed to be prepared and accessed by a black-box operation -- so-called oracle, even though this process, if not appropriately designed, may adversely diminish the quantum query advantage. Here, we introduce an efficient quantum data-access process, dubbed as quantum data-access machine (QDAM), and present a general architecture for quantum search algorithm. We analyze the runtime of our algorithm in view of the fault-tolerant quantum computation (FTQC) consisting of logical qubits within an effective quantum error correction code. Specifically, we introduce a measure involving two computational complexities, i.e. quantum query and $T$-depth complexities, which can be critical to assess performance since the logical non-Clifford gates, such as the $T$ (i.e., $\pi/8$ rotation) gate, are known to be costliest to implement in FTQC. Our analysis shows that for $N$ searching data, a QDAM model exhibiting a logarithmic, i.e., $O(\log{N})$, growth of the $T$-depth complexity can be constructed. Further analysis reveals that our QDAM-embedded quantum search requires $O(\sqrt{N} \times \log{N})$ runtime cost. Our study thus demonstrates that the quantum data search algorithm can truly speed up over classical approaches with the logarithmic $T$-depth QDAM as a key component., Comment: 16 pages, 8 figures / Published version

The noisy binary linear problem (NBLP) is known as a computationally hard problem, and therefore, it offers primitives for post-quantum cryptography. An efficient quantum NBLP algorithm that exhibits a polynomial quantum sample and time complexities has recently been proposed. However, the algorithm requires a large number of samples to be loaded in a highly entangled state and it is unclear whether such a precondition on the quantum speedup can be obtained efficiently. Here, we present a complete analysis of the quantum solvability of the NBLP by considering the entire algorithm process, namely from the preparation of the quantum sample to the main computation. By assuming that the algorithm runs on "fault-tolerant" quantum circuitry, we introduce a reasonable measure of the computational time cost. The measure is defined in terms of the overall number of T gate layers, referred to as T-depth complexity. We show that the cost of solving the NBLP can be polynomial in the problem size, at the expense of an exponentially increasing logical qubits., Comment: 15 pages, 4 figures; Comment welcome

We study an arbitrary non-equilibrium dynamics of a quantum bipartite system coupled to a reservoir. For its characterization, we present a fluctuation theorem (FT) that explicitly addresses the quantum correlation of subsystems during the thermodynamic evolution. To our aim, we designate the local and the global states altogether in the time-forward and the time-reversed transition probabilities. In view of the two-point measurement scheme, only the global states are subject to measurements whereas the local states are used only as an augmented information on the composite system. We specifically derive a FT in such a form that relates the entropy production of local systems in the time-forward transition to the change of quantum correlation in the time-reversed transition. This also leads to a useful thermodynamic inequality and we illustrate its advantage by an example of an isothermal process on Werner states., Comment: 9 pages, 2 figures

We present a fluctuation theorem for quantum bipartite systems in which the subsystems exchange information with each other. Our information fluctuation theorem includes correlations by introducing a quantum mechanical mutual information content and a statistical probability distribution which allows one to consider statistical averages when computing the thermodynamic and informational quantities. The fundamental limit of heat transferred from a heat reservoir for quantum bipartite systems involving the quantum mutual information is then derived. We illustrate the use of our thermodynamic inequality in quantum computing and discuss our results in terms of Landauer's principle., Comment: 4 pages

The key question of this paper is whether work can be extracted from a heat engine by using purely quantum mechanical information. If the answer is yes, what is its mathematical formula? First, by using a bipartite memory we show that the work extractable from a heat engine is bounded not only by the free energy change and the sum of the entropy change of an individual memory but also by the change of quantum mutual information contained inside the memory. We then find that the engine can be driven by purely quantum information, expressed as the so-called quantum discord, forming a part of the quantum mutual information. To confirm it, as a physical example we present the Szilard engine containing a diatomic molecule with a semi-permeable wall., Comment: 5 pages, 2 figures