Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
<jats:p>We explore the power of the unbounded Fan-Out gate and the Global Tunable gates generated by Ising-type Hamiltonians in constructing constant-depth quantum circuits, with particular attention to quantum memory devices. We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. These gates include the Fan-In gates defined by <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mi>x</mml:mi><mml:mo fence="false" stretchy="false">⟩</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mi>b</mml:mi><mml:mo fence="false" stretchy="false">⟩</mml:mo><mml:mo stretchy="false">↦</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mi>x</mml:mi><mml:mo fence="false" stretchy="false">⟩</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mi>b</mml:mi><mml:mo>⊕</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo fence="false" stretchy="false">⟩</mml:mo></mml:math> for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>x</mml:mi><mml:mo>∈</mml:mo><mml:mo fence="false" stretchy="false">{</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:msup><mml:mo fence="false" stretchy="false">}</mml:mo><mml:mi>n</mml:mi></mml:msup></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>b</mml:mi><mml:mo>∈</mml:mo><mml:mo fence="false" stretchy="false">{</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo fence="false" stretchy="false">}</mml:mo></mml:math>, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>f</mml:mi></mml:math> is a Boolean function. The first of our constructions is based on computing the one-hot encoding of the control register <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mi>x</mml:mi><mml:mo fence="false" stretchy="false">⟩</mml:mo></mml:math>, while the second is based on Boolean analysis and exploits different representations of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>f</mml:mi></mml:math> such as its Fourier expansion. Via these constructions, we obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices – Quantum Random Access Memory (QRAM) and Quantum Random Access Gate (QRAG) – of memory size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math>. The implementation based on one-hot encoding requires either <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:msup><mml:mi>log</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">(</mml:mo><mml:mi>d</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msup><mml:mo></mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>n</mml:mi></mml:mrow><mml:msup><mml:mi>log</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">(</mml:mo><mml:mi>d</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msup><mml:mo></mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>n</mml:mi></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:math> ancillae and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:msup><mml:mi>log</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">(</mml:mo><mml:mi>d</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msup><mml:mo></mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>n</mml:mi></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:math> Fan-Out gates or <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:msup><mml:mi>log</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">(</mml:mo><mml:mi>d</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msup><mml:mo></mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>n</mml:mi></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:math> ancillae and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>16</mml:mn><mml:mi>d</mml:mi><mml:mo>−</mml:mo><mml:mn>10</mml:mn></mml:math> Global Tunable gates, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>d</mml:mi></mml:math> is any positive integer and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>log</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">(</mml:mo><mml:mi>d</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msup><mml:mo></mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>n</mml:mi></mml:mrow><mml:mo>=</mml:mo><mml:mi>log</mml:mi><mml:mo></mml:mo><mml:mo>⋯</mml:mo><mml:mi>log</mml:mi><mml:mo></mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>n</mml:mi></mml:mrow></mml:math> is the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>d</mml:mi></mml:math>-times iterated logarithm. On the other hand, the implementation based on Boolean analysis requires <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>8</mml:mn><mml:mi>d</mml:mi><mml:mo>−</mml:mo><mml:mn>6</mml:mn></mml:math> Global Tunable gates at the expense of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>−</mml:mo><mml:mi>d</mml:mi></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> ancillae.</jats:p>