The iterative quantum phase estimation algorithm (IPEA) is better suited for NISQ and early fault-tolerant hardware compared to the original algorithm, which requires the inverse quantum Fourier transform. However, current error mitigation and correction implementations lead to imperfect unitaries, causing erroneous phase feedback in IPEA. To improve the reliability of phase bits is to repeat the k^th iteration for the 2^k-th power of the unitary $N_k^*$ times, followed by a majority decision. However, due to variations in their circuit complexities, different iterations incur varying resource costs ($w_k$) and different per-shot error probabilities ($q_k$). Given tight resource constraints, we ask what the optimal number $\{N_k^*: 1\le k \le L\}$ of shots per bit is: $$\arg \max_{\{N_k\}} \mathbb{P}(\text{all } L \text{ bits correct}) \text{ s.t.} \sum_{k=1}^L w_k N_k \le W$$ We obtain closed-form expressions for $N^*_k$ under the conditions: $W \gg \sum_k w_k $(enough for at least one shot per iteration), $w_k$ increases with $k$, $q_k$ are small enough and $L$ is large. We do so by analyzing tractable upper and lower surrogate problems derived via tight concentration and anti-concentration bounds and showing that their solutions converge when $q_k\ll 1$.
We observe that when $W\gg \sum_k w_k \ln\! \left(\sum_k w_k\right)$, the optimal $N_k^*$ is proportional to $\frac{\ln\! \left(\sum_k w_k\right)}{c_k}$ and does not depend on individual $w_k$, where $c_k=-\ln\left(2\sqrt{\left(1-\frac{q_k}{2} \right) \frac{q_k}{2}}\right) \propto \ln\frac{1}{q_k}$. However, when $\sum_k w_k \ll W\ll\sum_k w_k \ln\! \left(\sum_k w_k\right)$, the allocation is also (additively) influenced by $\frac{1}{c_k}\ln\frac{1}{w_k}$ for larger values of $k$, i.e., higher powers of unitary. These results lead to simple rules of thumb for resource allocation that may benefit the design of practical systems.
The iterative quantum phase estimation algorithm (IPEA) is better suited for NISQ and early fault-tolerant hardware compared to the original algorithm, which requires the inverse quantum Fourier transform. However, current error mitigation and correction implementations lead to imperfect unitaries, causing erroneous phase feedback in IPEA. To improve the reliability of phase bits is to repeat the k^th iteration for the 2^k-th power of the unitary Nk∗ times, followed by a majority decision. However, due to variations in their circuit complexities, different iterations incur varying resource costs (wk) and different per-shot error probabilities (qk). Given tight resource constraints, we ask what the optimal number {Nk∗:1≤k≤L} of shots per bit is: argmax{Nk}P(all L bits correct) s.t.∑k=1LwkNk≤W We obtain closed-form expressions for Nk∗ under the conditions: W≫∑kwk(enough for at least one shot per iteration), wk increases with k, qk are small enough and L is large. We do so by analyzing tractable upper and lower surrogate problems derived via tight concentration and anti-concentration bounds and showing that their solutions converge when qk≪1.
We observe that when W≫∑kwkln(∑kwk), the optimal Nk∗ is proportional to ckln(∑kwk) and does not depend on individual wk, where ck=−ln(2(1−2qk)2qk)∝lnqk1. However, when ∑kwk≪W≪∑kwkln(∑kwk), the allocation is also (additively) influenced by ck1lnwk1 for larger values of k, i.e., higher powers of unitary. These results lead to simple rules of thumb for resource allocation that may benefit the design of practical systems.
As fully fault-tolerant quantum computers capable of solving useful problems remain a distant goal, we anticipate an era of during which limited error correction is available. We propose a framework for designing early fault-tolerant algorithms by trading between error-correction overhead and residual logical noise, and apply it to quantum phase estimation (QPE). We develop a quantum-Fourier-transform- (QFT) based QPE technique that is robust to global depolarizing noise and outperforms the previous state of the art at low and moderate noise rates. We further introduce the explicitly unbiased maximum-likelihood estimator (EUMLE), a data-processing technique that mitigates errors in QFT-based QPE schemes. EUMLE provides consistent asymptotically normal error-mitigated estimates, addressing the open problem of extending error mitigation beyond expectation-value estimation. Applying this scheme to the ground-state problem of the two-dimensional Hubbard model and various molecular Hamiltonians, we find that we can roughly halve the number of physical qubits with a ∼ 10 times wall-clock time overhead, but that further reduction causes a steep run-time increase. This work provides an end-to-end analysis of early fault-tolerance cost reductions and space-time trade-offs, and identifies which areas can be improved in the future.
Quantum computing has made significant advancements in the last years in both hardware and software. Unfortunately, the currently available Noisy Intermediate-Scale Quantum (NISQ) hardware is still heavily affected by noise. Many optimization techniques have been developed to reduce the negative effects thereof, which, however, only works up to a certain point. Therefore, scaling quantum applications from currently considered small research examples to industrial applications requires error-correction techniques to execute quantum circuits in a fault-tolerant fashion and enter the Fault-Tolerant Quantum Computing (FTQC) era. These error-correction techniques introduce dramatic qubit overheads, leading to the requirement of tens of thousands of qubits already for toy-sized examples. Hence, quantum circuit optimization that reduces qubit overheads when shifting from the NISQ to the FTQC era is essential. This raises the question, whether we need to start from scratch, or whether current state-of-the-art optimization techniques can be used as a basis for this. To approach this question, this work investigates the effects of different optimization passes on a representative selection of quantum circuits. Since hardly any tools to automatically design and evaluate FTQC quantum circuits exist yet, we utilize resource estimation to compare the (potential) benefits gained by applying NISQ quantum circuit optimization to estimated FTQC resource requirements. The Results indicate that, indeed, the estimated resource requirements for FTQC can be improved by applying NISQ quantum circuit optimization techniques. At the same time, more detailed investigations show what techniques lead to more benefits for FTQC compared to others, providing guidelines for the transfer of NISQ optimization techniques to the FTQC era.
Given Ntot applications of a unitary operation with an unknown phase θ, a large-scale fault-tolerant quantum system can {reduce} an estimate's {error} scaling from O[1/Ntot] to O[1/Ntot]. Owing to the limited resources available to near-term quantum devices, entanglement-free protocols have been developed, which achieve a O[log(Ntot)/Ntot] {mean-absolute-error} scaling. Here, we propose a new two-step protocol for near-term phase estimation, with an improved {error} scaling. Our protocol's first step produces several low-{standard-deviation} estimates of θ, within θ's parameter range. The second step iteratively hones in on one of these estimates. Our protocol's {mean absolute error} scales as O[log(logNtot)/Ntot]. Furthermore, we demonstrate a reduction in the constant scaling factor and the required circuit depths: our protocol can outperform the asymptotically optimal quantum-phase estimation algorithm for realistic values of Ntot.
The pace of innovation in quantum information science has recently exploded due to the hope that a quantum computer will be able to solve a multitude of problems that are intractable using classical hardware. Current quantum devices are in what has been termed the ``noisy intermediate-scale quantum'', or NISQ stage. Quantum hardware available today with 50-100 physical qubits may be among the first to demonstrate a quantum advantage. However, there are many challenges to overcome, such as dealing with noise, lowering error rates, improving coherence times, and scalability. \n \nWe are at a time in the field where minimization of resources is critical so that we can run our algorithms sooner rather than later. Running quantum algorithms ``at scale'' incurs a massive amount of resources, from the number of qubits required to the circuit depth. A large amount of this is due to the need to implement operations fault-tolerantly using error-correcting codes. \n \nFor one, to run an algorithm we must be able to efficiently read in and output data. Fault-tolerantly implementing quantum memories may become an input bottleneck for quantum algorithms, including many which would otherwise yield massive improvements in algorithm complexity. We will also need efficient methods for tomography to characterize and verify our processes and outputs. Researchers will require tools to automate the design of large quantum algorithms, to compile, optimize, and verify their circuits, and to do so in a way that minimizes operations that are expensive in a fault-tolerant setting. Finally, we will also need overarching frameworks to characterize the resource requirements themselves. Such tools must be easily adaptable to new developments in the field, and allow users to explore tradeoffs between their parameters of interest. \n \nThis thesis contains three contributions to this effort: improving circuit synthesis using large-scale parallelization; designing circuits for quantum random-access memories and analyzing various time/space tradeoffs; using the mathematical structure of discrete phase space to select subsets of tomographic measurements. For each topic the theoretical work is supplemented by a software package intended to allow others researchers to easily verify, use, and expand upon the techniques herein.
When estimating the eigenvalues of a given observable, even fault-tolerant quantum computers will be subject to errors, namely algorithmic errors. These stem from approximations in the algorithms implementing the unitary passed to phase estimation to extract the eigenvalues, e.g. Trotterisation or qubitisation. These errors can be tamed by increasing the circuit complexity, which may be unfeasible in early-stage fault-tolerant devices. Rather, we propose in this work an error mitigation strategy that enables a reduction of the algorithmic errors up to any order, at the cost of evaluating the eigenvalues of a set of observables implementable with limited resources. The number of required observables is estimated and is shown to only grow polynomially with the number of terms in the Hamiltonian, and in some cases, linearly with the desired order of error mitigation. Our results show error reduction of several orders of magnitude in physically relevant cases, thus promise accurate eigenvalue estimation even in early fault-tolerant devices with limited number of qubits.
This thesis deals with the problematics of the scalability of fault-tolerant quantum computing. This question is studied under the angle of estimating the resources needed to set up such computers. What we call a resource is, in principle, very general; it could be the power, the energy, the total bandwidth allocated to the different qubits... However, we mainly focus on the energetic cost of quantum computing. In particular, we develop an inter-disciplinary approach that allows to minimize the resources required to implement algorithms on quantum computers. By asking to find the minimum amount of resources required to perform a computation under the constraint that the algorithm provides a correct answer with a targeted accuracy, it is possible to optimize the whole computer in order to minimize the resources spent, while being sure to have a correct answer with a high probability. We apply this approach to a complete model fault-tolerant quantum computer based on superconducting qubits. Our results indicate that for algorithms implemented on thousands of logical qubits, our method makes it possible to reduce the energetic cost by orders of magnitudes in regimes where, without optimizing, the power consumption could be close to the gigawatt. This work illustrates that the energetic cost of quantum computing should be a criterion in itself, allowing to evaluate the scaling potential of a given quantum computer technology. It also illustrates that optimizing the architecture of a quantum computer, via inter-disciplinary methods, including algorithms, error correction, qubit physics, engineering aspects, such as the ones that we propose, can prove to be a powerful tool, clearly improving the scaling potential of quantum computers. Finally, we provide general hints about how to make fault-tolerant quantum computers energy efficient.